强连通 HDU3072

n个点m条边
m条边权值
简单点说就是求把所有强连通分量连在一起所需的最小花费不用双向
图是联通的 cost[] 维护到这里的最小花费求和
  1 #include<stdio.h>
  2 #include<string.h>
  3 #include<stack>
  4 #include<algorithm>
  5 
  6 using namespace std;
  7 
  8 #define inf   100000000
  9 #define MAXN  50010
 10 #define MAXN1 1000010
 11 int head[MAXN];
 12 
 13 struct edg
 14 {
 15     int fr,to,w,next;
 16 }x[MAXN1];
 17 int cnt,k,num;
 18 int dfn[MAXN],low[MAXN],z[MAXN],f[MAXN],cost[MAXN];
 19 bool vis[MAXN];
 20 
 21 void add(int u,int v,int w)
 22 {
 23     x[cnt].fr=u;
 24     x[cnt].next=head[u];
 25     x[cnt].to=v;
 26     x[cnt].w=w;
 27     head[u]=cnt++;
 28 }
 29 stack<int>s;
 30 
 31 void dfs(int u)
 32 {
 33     dfn[u]=low[u]=k++;
 34     vis[u]=1;
 35     s.push(u);
 36     int i;
 37     for(i=head[u];i!=-1;i=x[i].next)
 38     {
 39         if(!dfn[x[i].to])
 40         {
 41             dfs(x[i].to);
 42             low[u]=min(low[u],low[x[i].to]);
 43         }
 44         else if(vis[x[i].to])
 45             low[u]=min(low[u],dfn[x[i].to]);
 46     }
 47     if(dfn[u]==low[u])
 48     {
 49         num++;
 50         while(!s.empty())
 51         {
 52             int now=s.top();
 53             s.pop();
 54             vis[now]=0;
 55             f[now]=num;
 56             if(now==u)
 57                 break;
 58         }
 59     }
 60 }
 61 
 62 int main()
 63 {
 64     int n,m;
 65 
 66     while(scanf("%d%d",&n,&m)!=EOF)
 67     {
 68         int i;
 69         cnt=0;
 70         num=0;
 71         k=1;
 72         memset(cost,0,sizeof(cost));
 73         memset(head,-1,sizeof(head));
 74         memset(vis,0,sizeof(vis));
 75         memset(dfn,0,sizeof(dfn));
 76         memset(f,0,sizeof(f));
 77         memset(z,0,sizeof(z));
 78         for(i=1;i<=m;i++)
 79         {
 80             int a,b,w;
 81             scanf("%d%d%d",&a,&b,&w);
 82             add(a,b,w);
 83         }
 84         for(i=0;i<n;i++)
 85             cost[i]=inf;
 86         for(i=0;i<n;i++)
 87             if(!dfn[i])
 88                 dfs(i);
 89         for(i=0;i<cnt;i++)
 90         {
 91             int u,v;
 92             u=f[x[i].fr];
 93             v=f[x[i].to];
 94             if(u!=v)
 95                 cost[v]=min(cost[v],x[i].w);
 96         }
 97         int ans=0;
 98         for(i=1;i<=num;i++)
 99         {
100             if(cost[i]!=inf)
101                 ans=ans+cost[i];
102         }
103         printf("%d
",ans);
104     }
105 
106     return 0;
107 }