题意：一个带权有向图，求起点到终点的两条路径权值之和最小，且两条路径没有公共点（除起点，终点）；
分析：拆点法，将u拆成u和u'，u-u'容量为1，费用为0，这样就能保证每个点只用一次，起点s-s'容量为2，终点t-t'容量为2保证最大流会求出两条路径，若输入u-v,权为c，则增加边u'-v，容量为1，费用为c.
#include <cstdio> #include <iostream> #include <sstream> #include <cmath> #include <cstring> #include <cstdlib> #include <string> #include <vector> #include <map> #include <set> #include <queue> #include <stack> #include <algorithm> using namespace std; #define ll long long #define _cle(m, a) memset(m, a, sizeof(m)) #define repu(i, a, b) for(int i = a; i < b; i++) #define repd(i, a, b) for(int i = b; i >= a; i--) #define sfi(n) scanf("%d", &n) #define pfi(n) printf("%d ", n) #define sfi2(n, m) scanf("%d%d", &n, &m) #define pfi2(n, m) printf("%d %d ", n, m) #define pfi3(a, b, c) printf("%d %d %d ", a, b, c) #define maxn 2010 #define maxm 10*maxn const int inf = 0x3f3f3f3f; struct Nod { int b, nxt; int cap, cst; void init(int b, int nxt, int cap, int cst) { this->b = b; this->nxt = nxt; this->cap = cap; this->cst = cst; } }; struct MinCost { int E[maxn]; int n; Nod buf[maxm*2]; int len; int p[maxn]; void init(int n) { this->n = n; memset(E, 255, sizeof(E)); len = 0; } void addCap(int a, int b, int cap, int cst) { buf[len].init(b, E[a], cap, cst); E[a] = len ++; buf[len].init(a, E[b], 0, -cst); E[b] = len ++; } bool spfa(int source, int sink) { static queue<int> q; static int d[maxn]; memset(d, 63, sizeof(d)); memset(p, 255, sizeof(p)); d[source] = 0; q.push(source); int u, v; while(!q.empty()) { u = q.front(); q.pop(); for(int i = E[u]; i != -1; i = buf[i].nxt) { v = buf[i].b; if(buf[i].cap>0 && d[u]+buf[i].cst<d[v]) { d[v] = d[u]+buf[i].cst; p[v] = i; q.push(v); } } } return d[sink] != inf; } int solve(int source, int sink) { int minCost = 0,maxFlow = 0;//需要maxFlow的话,想办法返回 while(spfa(source, sink)) { int neck = inf; for(int t=p[sink]; t != -1; t = p[ buf[t^1].b ])//buf[t^1].b是父节点 neck = min(neck, buf[t].cap); maxFlow += neck; for(int t = p[sink]; t != -1; t = p[ buf[t^1].b ]) { buf[t].cap -= neck; buf[t^1].cap += neck; minCost += buf[t].cst * neck; } } return minCost; } } mc; int main() { int n, m; while(~sfi2(n, m)) { mc.init(n); int a, b, c; repu(i, 0, m) { sfi2(a, b), sfi(c); mc.addCap((--a) + n, --b, 1, c); } repu(i, 1, n - 1) mc.addCap(i, i + n, 1, 0); mc.addCap(0, n, 2, 0); mc.addCap(n - 1, n * 2 - 1, 2, 0); pfi(mc.solve(0, n - 1)); } return 0; }