#include<stdio.h>
#include<string.h>
#include<iostream>
#include<stack>
#include<utility>
#include<algorithm>
#include<stdlib.h>
using namespace std;
const int maxn = 100005;
struct nd
{
        int from,to,next,w;
}edge[maxn*2];
int vis[maxn],head[maxn];
int dfn[maxn],low[maxn];
int ecnt,idx,belong[maxn];
int in[maxn],dis[maxn];
stack<int>st;

void add(int s,int t,int w,int ecnt)
{
        edge[ecnt].from = s;
        edge[ecnt].to = t;
        edge[ecnt].next = head[s];
        edge[ecnt].w = w;
        head[s] = ecnt;
}

void tarjan(int u)
{
        int i,v;
        dfn[u] = low[u] = ++idx;
        vis[u] = 1;
        st.push(u);
        for(i = head[u]; i != -1; i = edge[i].next)
        {
                v = edge[i].to;
                if(!dfn[v])
                {
                        tarjan(v);
                        low[u]  = min(low[v],low[u]);
                }else if(vis[v]) low[u] = min(dfn[v],low[u]);
        }
        if(low[u]==dfn[u])
        {
                do{
                        v = st.top();
                        st.pop();
                        vis[v] = 0;
                        belong[v] = u;
                }while(v!=u);
        }
}
void dfs(int pre,int cur,int sum)
{
        int i,j,v;
        if(dis[cur]>-1){
                if(dis[cur]>sum) dis[cur] = sum;
                return ;
        }
        if(dis[cur]<0) dis[cur] = sum;
        for(i = head[cur]; i != -1; i = edge[i].next){
                v = edge[i].to;
                if(v!=pre) dfs(cur,v,edge[i].w);
        }
}
int main()
{
        int i,j,k,n,m;
        int s,t,w;
        while(scanf("%d%d",&n,&m)==2)
        {
                memset(vis,0,sizeof(vis));
                memset(head,-1,sizeof(head));
                memset(dfn,0,sizeof(dfn));
                memset(in,0,sizeof(in));
                for(i = 0; i <= n; ++ i) belong[i] = i;
                ecnt = 0; idx = 0;
                for(i = 0; i < m; ++ i)
                {
                        scanf("%d %d %d",&s,&t,&w);
                        add(s,t,w,ecnt); ecnt++;
                        in[t]++;
                }
                for(i = 0; i < n; ++ i) if(!in[i]) tarjan(i);
                k = 0;
                memset(head,-1,sizeof(head));
                memset(in,0,sizeof(in));
                for(j = 0; j < ecnt; ++ j)
                {
                        s = edge[j].from;
                        t = edge[j].to;
                        w = edge[j].w;
                        if(belong[s]!=belong[t]){ in[belong[t]]++; add(belong[s],belong[t],w,k); ++ k; }
                }
                memset(dis,-1,sizeof(dis));
                memset(vis,0,sizeof(vis));
                for(i = 0; i < n; ++i ) if(!in[i]) dfs(-1,i,0);
                k = 0;
                for(i = 0; i < n; ++ i) if(dis[i]>0) k += dis[i];
                printf("%d\n",k);
        }
        return 0;
}

优质内容筛选与推荐>>
1、Java中对象与引用
2、iptables 分析(二)
3、C++命名空间
4、Commons之Commons-io
5、继承与派生：派生类对基类成员的访问控制之保护继承与私有继承（转）