可以转化成最小割的求解，题目其实就是要求把点分成两个集合，增加一个超级汇点，一部分的点在根节点所在集合内，一部分节点在超级汇点所在的集合内，这两就分开了，又要求费用最小，那么就是最小割。
#include<cstdio> #include<cstring> #include<string> #include<cmath> #include<vector> #include<queue> #include<algorithm> using namespace std; const int maxn=1000+10; const int INF=0x7FFFFFFF; struct Edge { int from,to,cap,flow; }; vector<Edge>edges; vector<int>G[maxn]; vector<int>ljb[maxn]; bool vis[maxn]; int d[maxn]; int cur[maxn]; int flag[maxn]; int cost[maxn][maxn]; int n,m,s,t; //求出层次网络 bool BFS() { memset(vis,0,sizeof(vis)); queue<int>Q; Q.push(s); d[s]=0; vis[s]=1; while(!Q.empty()) { int x=Q.front(); Q.pop(); for(int i=0;i<G[x].size();i++) { Edge& e=edges[G[x][i]]; if(!vis[e.to]&&e.cap>e.flow) { vis[e.to]=1; d[e.to]=d[x]+1; Q.push(e.to); } } } return vis[t]; } //加边 void AddEdge(int from,int to,int cap) { Edge r; r.from=from;r.to=to;r.cap=cap;r.flow=0; edges.push_back(r); Edge d; d.from=to;d.to=from;d.cap=0;d.flow=0; edges.push_back(d); m=edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } //每个阶段来一次DFS增广 int DFS(int x,int a) { if(x==t||a==0) return a; int flow=0,f; for(int i=cur[x];i<G[x].size();i++) { Edge& e=edges[G[x][i]]; if(d[x]+1==d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0) { e.flow+=f; edges[G[x][i]^1].flow-=f; flow+=f; a-=f; if(a==0) break; } } return flow; } //多个阶段，多次建立层次网络。 int Maxflow(int ss,int tt) { int flow=0; while(BFS()) { memset(cur,0,sizeof(cur)); flow+=DFS(ss,INF); } return flow; } void dfs(int x,int fa) { if(fa!=-1) AddEdge(fa,x,cost[fa][x]); int FD=0; for(int i=0;i<ljb[x].size();i++) { if(!flag[ljb[x][i]]) { FD=1; flag[ljb[x][i]]=1; dfs(ljb[x][i],x); } } if(FD==0) AddEdge(x,t,INF); } int main() { while(~scanf("%d%d",&n,&s)) { if(n==0&&s==0) break; t=n+1; edges.clear(); for(int i=0;i<maxn;i++) { G[i].clear(); ljb[i].clear(); } for(int i=1;i<=n-1;i++) { int uu,vv,cc; scanf("%d%d%d",&uu,&vv,&cc); ljb[uu].push_back(vv); ljb[vv].push_back(uu); cost[uu][vv]=cc; cost[vv][uu]=cc; } memset(flag,0,sizeof(flag)); flag[s]=1; dfs(s,-1); int ans=Maxflow(s,t); if(ans==INF) printf("0 "); else printf("%d ",ans); } return 0; }