题意：一个带权有向图，求起点到终点的两条路径权值之和最小，且两条路径没有公共点（除起点，终点）；
分析：拆点法，将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", n)
#define sfi2(n, m) scanf("%d%d", &n, &m)
#define pfi2(n, m) printf("%d %d\n", n, m)
#define pfi3(a, b, c) printf("%d %d %d\n", 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*]; int len; int p[maxn];
void init(int n) {
this->n = n;
memset(E, , sizeof(E));
len = ;
}
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], , -cst); E[b] = len ++;
}
bool spfa(int source, int sink) {
static queue<int> q;
static int d[maxn];
memset(d, , sizeof(d));
memset(p, , sizeof(p)); d[source] = ;
q.push(source);
int u, v;
while(!q.empty()) {
u = q.front();
q.pop();
for(int i = E[u]; i != -; i = buf[i].nxt) {
v = buf[i].b;
if(buf[i].cap> && 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 = ,maxFlow = ;//需要maxFlow的话,想办法返回
while(spfa(source, sink)) {
int neck = inf;
for(int t=p[sink]; t != -; t = p[ buf[t^].b ])//buf[t^1].b是父节点
neck = min(neck, buf[t].cap);
maxFlow += neck;
for(int t = p[sink]; t != -; t = p[ buf[t^].b ]) {
buf[t].cap -= neck;
buf[t^].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, , m)
{
sfi2(a, b), sfi(c);
mc.addCap((--a) + n, --b, , c);
}
repu(i, , n - ) mc.addCap(i, i + n, , );
mc.addCap(, n, , );
mc.addCap(n - , n * - , , );
pfi(mc.solve(, n - ));
}
return ;
}