最小费用最大流入门题，
基础算法原理：- 找出一条最小费用道路， 改变这条路上的流量
- 不停增广循环这个过程
好了没了， 当然你既然来做这个题的话， 最起码的增广路算法求最大流应该是会的， 上述原理的细节实现和那个算法基本一致；
这个题难就难在建图， 因为要走两次， 容易想到要把源点和汇点的容量设为2
但对于边不能重复走过的情况， 处理很巧妙， 在存反向弧的时候要把这个反向弧的权值设成-w， 这样走过这条边的情况就只会存在走过和未走过， 因为一旦在一次最短路中u->v走过， 那么下次我们就会把它的状态置反 （u-v的流量设为0， v-u的流量设成1）， 下一次我们一定不会走v-u的w大于0这条边， 而是走v-u小于0的边， 就处理了重复问题 代码风格个人习惯#include#include #include #include #include using namespace std;const int N = 2010;const int M = 200010;const int oo = ~0U >> 1;#define next Next#define begin Begin#define C c = getchar()#define FILL(a, b) memset(a, b, sizeof(a))#define rep(i, s, t) for(int i = s; i <= t; ++i)#define erep(i, u) for(int i = begin[u]; i^(-1); i = next[i])void read(int &x) { char C; x = 0; while(c < '0' || c > '9') C; while(c >= '0' && c <= '9') x = x*10 + c-'0', C;}struct MCMF { int dis[N], fa[N], n, m, S, T, vis[N]; int e, next[M], to[M], begin[N], w[M], c[M], from[M]; void init() { S = 0, T = n+1; e = 0; FILL(begin, -1); } void add(int x, int y, int z, int f) { from[e] = x, to[e] = y; next[e] = begin[x]; begin[x] = e; w[e] = z, c[e++] = f; } void add_flow(int x, int y, int z, int f) { add(x, y, z, f), add(y, x, -z, 0); } queue q; bool SPFA() { FILL(fa, -1), FILL(vis, 0); rep(i, 0, T) dis[i] = oo; dis[S] = 0, q.push(S); while(!q.empty()) { int u = q.front(), v; q.pop(); vis[u] = false; erep(i, u) if(c[i] && w[i]+dis[u] < dis[v=to[i]]) { fa[v] = i, dis[v] = dis[u] + w[i]; if(!vis[v]) q.push(v), vis[v] = true; } } return fa[T] ^ (-1); } int solve(int res = 0) { while(SPFA()) { for(int pos = fa[T]; pos^(-1); pos = fa[from[pos]]) c[pos] --, c[pos^1] = c[pos]^1; res += dis[T]; } return res; } void output() { while(~scanf("%d%d", &n, &m)) { init(); rep(i, 1, m) { int x, y, z; read(x); read(y); read(z); add_flow(x, y, z, 1), add_flow(y, x, z, 1); } add_flow(S, 1, 0, 2), add_flow(n, T, 0, 2); cout << solve() << endl; } }}T;int main() {#ifndef ONLINE_JUDGE freopen("IP.in", "r", stdin); freopen("OP.out", "w", stdout);#endif T.output(); return 0;}