HDU1827 （tarjan+缩点）

  因为可以通过其他人来通知他们认识的人，所以这幅图可以用强连通分量变成一个
  缩点的图，所有相互强连通分支变成一个缩点，求的所有缩点中入度为0的缩点即为
  所求的需要通知的最小人数。然后再枚举所有人所在的缩点是否入度为0，是的话更
  新该缩点所需的最小费用即可

View Code

  1 #include<stdio.h>
  2 #include<string.h>
  3 #include<stdlib.h>
  4 #include<stack>
  5 #include<algorithm>
  6 using namespace std;
  7 const int maxn = 1005;
  8 const int maxm = 2005;
  9 const int inf =999999;
 10 struct node{
 11     int v,u,next;
 12 }edge[ maxm ];
 13 int head[ maxn ],cnt;
 14 int vis[ maxn ],low[ maxn ],dfn[ maxn ],id; 
 15 int n,m,ans1;//ans1:缩点的个数( from 1 to ans1 )
 16 int cost[ maxn ];
 17 int belong[ maxn ],inde[ maxn ];//缩点，入度
 18 stack<int>q;
 19 void init(){
 20     cnt=0;
 21     id=0;
 22     ans1=0;
 23     memset( vis,0,sizeof( vis ));
 24     memset( dfn,-1,sizeof(dfn) );
 25     memset( low,-1,sizeof( low ));
 26     memset( head,-1,sizeof( head ));
 27 }
 28 void addedge( int a,int b ){
 29     edge[ cnt ].v=a;
 30     edge[ cnt ].u=b;
 31     edge[ cnt ].next=head[ a ];
 32     head[ a ]=cnt++;
 33 }
 34 void tarjan( int now ){
 35     dfn[ now ]=low[ now ]=id++;
 36     vis[ now ]=1;
 37     q.push( now );
 38     for( int i=head[ now ];i!=-1;i=edge[ i ].next ){
 39         int next=edge[ i ].u;
 40         if( dfn[ next ]==-1 ){
 41             tarjan( next );
 42             low[ now ]=min( low[ now ],low[ next ]);
 43         }
 44         else if( vis[ next ]==1 ){
 45             low[ now ]=min( low[ now ],dfn[ next ] );
 46         }
 47     }
 48     if( low[ now ]==dfn[ now ] ){
 49         ans1++;
 50         while( 1 ){
 51             int tmp;
 52             tmp=q.top(),q.pop();
 53             vis[ tmp ]=0;
 54             belong[ tmp ]=ans1;
 55             if( tmp==now ) break;
 56         }
 57     }
 58 }
 59 
 60 int main(){
 61     while( scanf("%d%d",&n,&m)==2 ){
 62         for( int i=1;i<=n;i++ )
 63             scanf("%d",&cost[ i ]);
 64         init();
 65         int a,b;
 66         while( m-- ){
 67             scanf("%d%d",&a,&b);
 68             addedge( a,b );
 69         }
 70         while( !q.empty() ) q.pop();
 71         for( int i=1;i<=n;i++ ){
 72             if( dfn[ i ]==-1 ){
 73                 tarjan( i );
 74             }
 75         }
 76         memset( inde,0,sizeof( inde ));
 77         for( int i=0;i<cnt;i++ ){
 78             a=edge[ i ].v,b=edge[ i ].u;
 79             if( belong[ a ]!=belong[ b ] ){
 80                 inde[ belong[ b ] ]++;
 81             }
 82         }
 83         int ANS1,ANS2;
 84         ANS1=ANS2=0;
 85         int tmp_cnt[ maxn ];
 86         for( int i=1;i<=ans1;i++ ){
 87             if( inde[ i ]==0 )
 88                 ANS1++;//统计缩点之后，入度为0的点
 89             tmp_cnt[ i ]=inf;
 90         }
 91         for( int i=1;i<=n;i++ ){
 92             int tmp=belong[ i ];
 93             if( inde[ tmp ]==0 ){
 94                 tmp_cnt[ tmp ]=min( tmp_cnt[ tmp ],cost[ i ] );
 95             }
 96         }
 97         for( int i=1;i<=ans1;i++ ){
 98             if( tmp_cnt[ i ]!=inf )
 99                 ANS2+=tmp_cnt[ i ];
100         }
101         printf("%d %d\n",ANS1,ANS2);
102     }
103     return 0;
104 }

keep moving...