hdu 1827

强连通分量——tarjin算法；

这题的思路就是找出多少个出度为0的连通分量，结果就是这些连通分量的元素的最小值相加；

一道很简单的题，改了我好久，= =！~

贴代码：

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stack>

 #include<vector>

 #define maxn 1005

 using namespace std;

 int dfn[maxn],low[maxn],pen[maxn],b[maxn];

 int nncount,ans,cc[maxn],cnt,in[maxn];

 bool instack[maxn];

 vector<int>ve[maxn];

 stack<int>s;

 void tarjin(int x)

 {

     dfn[x]=low[x]=++nncount;

     instack[x]=;

     s.push(x);

     int l=ve[x].size();

     for(int i=; i<l; i++)

     {

         int v=ve[x][i];

         if(!dfn[v])

         {

             tarjin(v);

             low[x]=min(low[v],low[x]);

         }

         else if(instack[v])

             low[x]=min(low[x],dfn[v]);

     }

     if(dfn[x]==low[x])

     {

         cnt++;

         int t;

         do

         {

             t=s.top();

             s.pop();

             b[t]=cnt;

             instack[t]=;

         }

         while(t!=x);

     }

 }

 int main()

 {

     int n,m,x,y,sum;

     while(scanf("%d%d",&n,&m)!=EOF)

     {

         memset(low,,sizeof low);

         memset(b,,sizeof b);

         memset(dfn,,sizeof dfn);

         memset(in,,sizeof in);

         memset(cc,,sizeof cc);

         memset(instack,,sizeof instack);

         nncount=ans=sum=cnt=;

         for(int i=; i<=n; i++)

         {

             scanf("%d",&pen[i]);

             ve[i].clear();

         }

         while(!s.empty()) s.pop();

         for(int i=; i<m; i++)

         {

             scanf("%d%d",&x,&y);

             ve[x].push_back(y);

         }

         for(int i=; i<=n; i++)

             if(!dfn[i])

                 tarjin(i);

         for(int i=; i<=n; i++)

         {

             int l=ve[i].size();

             for(int j=; j<l; j++)

             {

                 int v=ve[i][j];

                 if(b[i]!=b[v]) in[b[v]]++;

             }

         }

         for(int i=; i<=cnt; i++)

         {

             if(in[i]==)ans++;

             cc[i]=;

         }

         for(int i=; i<=n; i++)

         {

             int v=b[i];

             if(in[v]==) cc[v]=min(cc[v],pen[i]);

         }

         for(int i=; i<=cnt; i++)

             if(cc[i]!=)

                 sum+=cc[i];

         printf("%d %d\n",ans,sum);

     }

     return ;

 }