|
找所有入度为0的点，就是最少要得到信息的点，然后这个点的权值是这个强连通分量里面所有点权值中的最小值，把他们加起来就好了。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#define N 1005
#define inf 999999999
using namespace std;
int dfn[N],low[N],head[N],sk[N],scc[N],cnt,sccnum,index,tp;
//scc[]值相同的，梭点后属于同一个点，sccnum表示缩点后有几个点
//dfn[x]表示x这个点dfs到的时间（深浅）
//low[x]此点及其后代指出去的边能返回的最浅的点的时间戳（dfn）
int incnt,outcnt;
int in[N],out[N];
struct edge{
int next,to,w;
}ed[N*2];
void add(int u,int v,int w){
ed[cnt].w = w;
ed[cnt].to = v;
ed[cnt].next = head[u];
head[u] = cnt++;
}
void tarjan(int root)//head初始值为-1时，用~i； head 初始值为0时用i
{
dfn[root]=low[root]=++index;
sk[++tp]=root;
int i;
for(i=head[root];~i;i=ed[i].next)
{
int v=ed[i].to;
if(!dfn[v])
{
tarjan(v);
low[root]=min(low[root],low[v]);
}
else if(!scc[v])
{
low[root]=min(low[root],dfn[v]);
}
}
if(low[root]==dfn[root])
{
sccnum++;
for(;;)
{
int x=sk[tp--];
scc[x]=sccnum;
if(x==root)break;
}
}
}
int p[N];
int main(){
int n,m;
while(~scanf("%d%d",&n,&m)){
for(int i=1;i<=n;i++)scanf("%d",&p[i]);
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(scc,0,sizeof(scc));
memset(head,-1,sizeof(head));
memset(in,0,sizeof(in));
memset(out,0,sizeof(out));
sccnum=0;
index=0;
tp=0;
cnt=0;
incnt=0;
outcnt=0;
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v,1);
}
for(int i=1;i<=n;i++){
if(!dfn[i])tarjan(i);
}
for(int i=1;i<=n;i++){
for(int j=head[i];j!=-1;j=ed[j].next) {
int v=ed[j].to;
if(scc[v]!=scc[i]){
in[scc[v]]++;
}
}
}
int cost=0;
for(int i=1;i<=sccnum;i++) {
if(!in[i]){
incnt++;
int c=inf;
for(int j=1;j<=n;j++){
if(scc[j]==i){
c=min(c,p[j]);
}
}
cost+=c;
}
}
printf("%d %d\n",incnt,cost);
}
return 0;
}
下面的代码来自：http://blog.csdn.net/l04205613/article/details/6651880
是重新建图的代码，而我是只找了入度为0的点
#include<cstdio>
#include<cstring>
#include<stack>
#include<climits>
using namespace std;
const int N = 1001;
struct Edge{
int s,e,next;
}edge1[2*N],edge2[2*N];
int n,m,e_num1,e_num2,vis_num,cnt;
int head[N],tim[N],low[N],instack[N],belong[N],price[N],de[N];
void AddEdge(int a,int b,Edge edge[],int &e_num){
edge[e_num].s=a; edge[e_num].e=b; edge[e_num].next=head[a]; head[a]=e_num++;
}
void getmap(){
int i,a,b;
for(i=1;i<=n;i++)
scanf("%d",&price[i]);
e_num1=0;
memset(head,-1,sizeof(head));
while(m--){
scanf("%d%d",&a,&b);
AddEdge(a,b,edge1,e_num1);
}
}
stack <int> st;
void tarjan(int x){//注意这是个递归过程
int i,j;
tim[x]=low[x]=++vis_num;//tim是时间戳,标记该点出现的时间,low是该点能到达的点中时间戳值的最小值
st.push(x);
instack[x]=1;
for(i=head[x];i!=-1;i=edge1[i].next){
int u=edge1[i].e;
if(tim[u]==-1){//时间戳为-1,也就是没有访问过
tarjan(u);
if(low[x]>low[u])low[x]=low[u];//更新low值,取能到达的最上(小)位置
}
//点u已经访问过且在栈中,时间戳比点i小,那么low值当然比点i小
//(因为tim,low都初始化为vis_num),那么low[i]可以更新
else if(instack[u] && tim[u]<low[x])
low[x]=tim[u];
}
if(tim[x]==low[x]){
cnt++;
do{//退栈,直到看到根为止
j=st.top();
st.pop();
instack[j]=0;
belong[j]=cnt;//标记该点所属分量的标号
}while(j!=x);
}
}
int fun(int x){
int i,min=INT_MAX;
for(i=1;i<=n;i++){
if(belong[i]==x && price[i]<min)
min=price[i];
}
return min;
}
void solve(){
int i;
cnt=vis_num=0;
memset(tim,-1,sizeof(tim));
memset(low,0,sizeof(low));
memset(instack,0,sizeof(instack));
for(i=1;i<=n;i++){
if(tim[i]==-1)tarjan(i);
}
e_num2=0;
memset(head,-1,sizeof(head));
memset(de,0,sizeof(de));
for(i=0;i<e_num1;i++){
int j=edge1[i].s;
int k=edge1[i].e;
if(belong[j] != belong[k]){
AddEdge(belong[j],belong[k],edge2,e_num2);
de[belong[k]]++;
}
}
int sum=0,count=0;
for(i=1;i<=cnt;i++){
if(de[i]==0){
sum+=fun(i);count++;
}
}
printf("%d %d\n",count,sum);
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
getmap();
solve();
}
return 0;
}
|
转播
