最小树形图，朱刘算法 可以看一下这个： http://blog.csdn.net/wsniyufang/article/details/6747392
#include<iostream> #include<string> #include<cstdio> #include<set> #include<stack> #include<list> #include<vector> #include<queue> #include<algorithm> #include<cstring> #include<cmath> #include<fstream> using namespace std; typedef long long ll; const int maxn = 1010,maxe = 40010,INF = 0x3f3f3f3f; int n,m; int in[maxn],pre[maxn],id[maxn],vis[maxn]; struct node{ int u,v,w; bool operator < (const node &a) const{ return w < a.w; } }; node e[maxe]; int build(int n,int m,int root){ int ans = 0; while(1){ memset(in,INF,sizeof in); memset(pre,-1,sizeof pre); //1.选择入边 for(int i = 0;i < m;++i){ int u = e[i].u,v = e[i].v,w = e[i].w; if (in[v] > w && u != v){ in[v] = w; pre[v] = u; } } for(int i = 0;i < n;++i){ if (i == root) continue; if (in[i] == INF) return -1; } in[root] = 0; //2.找环缩点 memset(id,-1,sizeof id); memset(vis,-1,sizeof vis); int cnt = 0; for(int i = 0;i < n;++i){ ans += in[i]; int v = i; while(vis[v] != i && v != root && id[v] == -1){ vis[v] = i; v = pre[v]; } if(v != root && id[v] == -1){ for(int u = pre[v];u != v;u = pre[u]) id[u] = cnt; id[v] = cnt++; } } if (cnt == 0) break; for(int i = 0;i < n;++i) if (id[i] == -1) id[i] = cnt++; //3.重新建图 for(int i = 0;i < m;++i){ int u = e[i].u,v = e[i].v; e[i].u = id[u],e[i].v = id[v]; if (u != v) e[i].w -= in[v]; } n = cnt; root = id[root]; } return ans; } void init(){ cin >> n >> m; int a,b,c; memset(e,0,sizeof e); for(int i = 0;i < m;++i){ cin >> a >> b >> c; e[i] = {a,b,c}; } int t = build(n,m,0); if (t == -1) cout << "Possums!" << endl; else cout << t << endl; } int main(){ int t; cin >> t; for(int k = 0;k < t;++k){ cout << "Case #" << k+1 << ": "; init(); } }