题意：
给你n 个点和m 个边，告诉你每个边的权值，要求从1~n 找出两条不想交的线路，使得他们的权值之和最小？ 输出最小权值之和？
思路：
因为是两条不想交线路，那么除了1和n 其余的点 只能走一次， 1和 n 只能走2次，因此 我们这里拆点， 1和 n 拆成 容量为2 费用为0的边。
其余的点拆成 容量为1 费用为0 的边。
并且每个边也只能走一次，因此边也是容量为1 费用为cost 的边。
直接求最小费用流就可以了。
吐槽：
inf 开的稍微大一点， 开成了1w 还wa了一次， 开成100w就好了
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <queue> using namespace std; const int maxn = 2000 + 23; const int inf = 1000000; struct Edge{ int from, to, cap, flow, cost; }; struct MCMF{ int n, m, s, t; vector<Edge> edges; vector<int> G[maxn]; int inq[maxn]; int d[maxn]; int p[maxn]; int a[maxn]; void init(int n){ this->n = n; for (int i = 0; i < n; ++i) G[i].clear(); edges.clear(); } void AddEdge(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}); m = edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } bool BellmanFord(int s,int t, int &flow,int &cost){ for (int i = 0; i < n; ++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; flow += a[t]; cost += d[t] * a[t]; int u = t; while(u != s){ edges[p[u] ].flow += a[t]; edges[p[u]^1 ].flow -= a[t]; u = edges[p[u] ].from; } return true; } int Mincost(int s,int t){ int flow = 0, cost = 0; while(BellmanFord(s,t,flow,cost)); return cost; } }mcmf; int main(){ int n,m; while(~scanf("%d %d",&n, &m)){ mcmf.init(2*n+7); for (int i = 2; i < n; ++i){ mcmf.AddEdge(i,i+n,1,0); } mcmf.AddEdge(1,n+1,2,0); mcmf.AddEdge(n,n+n,2,0); for (int i = 0; i < m; ++i){ int u,v,c; scanf("%d %d %d",&u, &v, &c); mcmf.AddEdge(u+n,v,1,c); } int ans = mcmf.Mincost(1,2*n); printf("%d\n",ans); } return 0; } /** 6 11 1 2 23 1 3 12 1 4 99 2 5 17 2 6 73 3 5 3 3 6 21 4 6 8 5 2 33 5 4 5 6 5 20 ans = 86 **/