题意：给出v个点，e条边的加权有向图，求1-v的两条不相交的路径，使得劝和最小。
思路：
拆点法，把2-（v-1）的每个节点拆成两个结点，中间连一条容量为1，费用为0的边，求1到v的流量为1的最小费用流即可。
#include <bits/stdc++.h> using namespace std; const int maxn=1e4; int n,m; const int inf=1e8; struct Edge { int from,to,flow,cap,cost; Edge(int f,int t,int c,int ff,int cc) { from=f; to=t; flow=ff; cap=c; cost=cc; } }; vector<int> G[maxn]; int p[maxn]; int a[maxn]; vector<Edge>edges; int d[maxn]; int inq[maxn]; void Init() { edges.clear(); for(int i=0; i<maxn; i++) G[i].clear(); } void addEdges(int from,int to,int cap,int cost) { edges.push_back(Edge(from,to,cap,0,cost)); edges.push_back(Edge(to,from,0,0,-cost)); int t=edges.size(); G[from].push_back(t-2); G[to].push_back(t-1); } bool BellmanFord(int s,int t,int &flow,long long int &cost) { for(int i=0; i<2*n+10; i++) d[i]=inf; memset(inq,0,sizeof(inq)); d[s]=0; inq[s]=1; p[s]=0; a[s]=inf; queue<int> q; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(),inq[u]=0; for(int i=0; i<G[u].size(); i++) { Edge &e=edges[G[u][i]]; if(e.cap>e.flow&&d[e.to]>d[u]+e.cost) { d[e.to]=d[u]+e.cost; p[e.to]=G[u][i]; a[e.to]=min(a[u],e.cap-e.flow); if(!inq[e.to]) { q.push(e.to); inq[e.to]=1; } } } } if(d[t]==inf) return false; cost+=(long long int)d[t]*(long long int)a[t]; for(int u=t; u!=s; u=edges[p[u]].from) { edges[p[u]].flow+=a[t]; edges[p[u]^1].flow-=a[t]; } return true; } int MincostMaxflow(int s,int t,long long int &cost) { int flow=0; cost=0; while(BellmanFord(s,t,flow,cost)); return flow; } int main() { while(cin>>n>>m) { if(m+n==0) break; Init(); for(int i=2; i<n; i++) addEdges(i,i+n,1,0); for(int i=1; i<=m; i++) { int u,v,c; cin>>u>>v>>c; if(u!=1&&u!=n) addEdges(u+n,v,1,c); else addEdges(u,v,1,c); } long long int ans; addEdges(0,1,2,0); addEdges(n,n*2+1,2,0); MincostMaxflow(0,2*n+1,ans); cout<<ans<<endl; } return 0; }