hdu 3072

强连通分量——tarjin 算法

这道题和前面那道hdu 2767唯一不同就是，2767需要找出最小数量的边使图成为连通分量，而这个题需要一点点贪心的思想在里面，它需要求出代价最小的边使图成为连通分量；

代码：

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <stack>

 #define N 50006

 using namespace std;

 struct Edge

 {

     int u, val, next;

     Edge() {}

     Edge(int a, int b, int c)

     {

         u=a, val=b, next=c;

     }

 } edge[];

 int head[N],tot,n,m,dfn[N],low[N],T,ind,id[N],in[N];

 bool vs[N];

 stack<int> S;

 void add_edge(int st, int en, int val)

 {

     edge[tot]=Edge(en,val,head[st]);

     head[st]=tot++;

 }

 void tarjan(int u)

 {

     S.push(u), vs[u]=true;

     dfn[u]=low[u]=T++;

     for(int e=head[u]; e!=-; e=edge[e].next)

     {

         int v=edge[e].u;

         if(!dfn[v])

         {

             tarjan(v);

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

         }

         else if(vs[v] && low[u]>dfn[v]) low[u]=dfn[v];

     }

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

     {

         ind++;

         int v;

         do

         {

             v=S.top();

             S.pop();

             id[v]=ind;

             vs[v]=false;

         }while(v!=u);

     }

 }

 int main()

 {

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

     {

         memset(head, -, sizeof head);

         tot=;

         for(int i=, a, b, c; i<m; i++)

         {

             scanf("%d%d%d", &a, &b, &c);

             add_edge(a,b,c);

         }

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

         memset(vs, , sizeof vs);

         memset(dfn,, sizeof dfn);

         memset(low,,sizeof low);

         T=ind=;

         for(int i=; i<n; i++) if(!dfn[i]) tarjan(i);

         for(int i=; i<ind; i++) in[i]=;

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

         {

             int u=id[i];

             for(int e=head[i]; e!=-; e=edge[e].next)

             {

                 int v=id[edge[e].u];

                 if(u!=v) in[v]=min(in[v], edge[e].val);

             }

         }

         int ans=;

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

         {

             if(i==id[]||in[i]==) continue;

             ans+=in[i];

         }

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

     }

     return ;

 }