HDU 1827 Summer Holiday 图论scc

先scc缩点，变成DAG，显然ans=入度为0的scc个数，每个scc的答案就是scc内点权最小的值。
 1 #include<bits/stdc++.h>
 2 #define INF 0x7fffffff
 3 using namespace std;
 4 const int MAXN = 2010;//点数 
 5 const int MAXM = 2100;//边数 
 6 struct Edge {  
 7     int to,next; 
 8 }edge[MAXM]; 
 9 int head[MAXN],tot,a,b; 
10 int Low[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN];//Belong数组的值是1~scc 
11 int Index,top; int scc;//强连通分量的个数 
12 int in[MAXN],out[MAXN],val[MAXN],d[MAXN];
13 bool Instack[MAXN]; 
14 int num[MAXN];//各个强连通分量包含点的个数，数组编号1~scc //num数组不一定需要，结合实际情况 
15 int cnt=0,ans=0;
16 void addedge(int u,int v){  
17     edge[tot].to = v;
18     edge[tot].next = head[u];
19     head[u] = tot++; 
20 } 
21 void Tarjan(int u){
22     int v;  
23     Low[u] = DFN[u] = ++Index; 
24     Stack[top++] = u;  
25     Instack[u] = true;  
26     for(int i = head[u];i != -1;i = edge[i].next) {  
27         v = edge[i].to;   
28         if( !DFN[v] ){
29             Tarjan(v);   
30             if( Low[u] > Low[v] )
31                 Low[u] = Low[v];   
32         }   
33         else if(Instack[v] && Low[u] > DFN[v])
34             Low[u] = DFN[v];  
35         }  
36         if(Low[u] == DFN[u]){ 
37             scc++; 
38             do{    
39                 v = Stack[--top];
40                 Instack[v] = false;    
41                 Belong[v] = scc;    
42                 num[scc]++;   
43             }while( v != u);  
44         } 
45 } 
46 void find_degree(int u){
47     int v;
48     for(int i = head[u];i != -1;i = edge[i].next){
49         v = edge[i].to;
50         if(Belong[u]==Belong[v]) continue;
51         in[Belong[v]]++;
52         //out[Belong[u]]++;
53     }
54 }
55 void solve(int N){
56     memset(DFN,0,sizeof(DFN));
57     memset(Instack,false,sizeof(Instack));
58     memset(num,0,sizeof(num));  
59     Index = scc = top = 0;  
60     for(int i=1;i<=N;i++) val[i]=INF;
61     for(int i = 1;i <= N;i++)
62         if(!DFN[i])    
63         Tarjan(i); 
64     for(int i=1;i<=N;i++){
65         val[Belong[i]]=min(val[Belong[i]],d[i]);
66         find_degree(i);
67     }
68     for(int i=1;i<=scc;i++){
69         if(in[i]==0) cnt++,ans+=val[i];
70     }
71 } 
72 void init(){
73     tot = 0; 
74     cnt=0,ans=0;
75     memset(head,-1,sizeof(head)); 
76     memset(in,0,sizeof(in));
77     memset(out,0,sizeof(out));
78 } 
79 int main(){
80     int n,m,u,v,T;
81     while(scanf("%d%d",&n,&m)!=EOF){ 
82         init();
83         for(int i=1;i<=n;i++) scanf("%d",&d[i]);
84         for(int i=1;i<=m;i++){
85             scanf("%d%d",&u,&v);
86             addedge(u,v);    
87         }
88         solve(n);
89         cout<<cnt<<' '<<ans<<endl;
90     }
91     return 0;
92 }