poj 2135 Farm Tour 费用流

给一个图， N个点， m条边，每条边有权值，从1走到n，然后从n走到1，一条路不能走两次，求最短路径。
如果(u, v)之间有边，那么加边（u, v, 1, val), (v, u, 1, val)， val是路的长度，代表费用， 1是流量。
  1 #include <iostream>
  2 #include <vector>
  3 #include <cstdio>
  4 #include <cstring>
  5 #include <algorithm>
  6 #include <cmath>
  7 #include <map>
  8 #include <set>
  9 #include <string>
 10 #include <queue>
 11 using namespace std;
 12 #define pb(x) push_back(x)
 13 #define ll long long
 14 #define mk(x, y) make_pair(x, y)
 15 #define lson l, m, rt<<1
 16 #define mem(a) memset(a, 0, sizeof(a))
 17 #define rson m+1, r, rt<<1|1
 18 #define mem1(a) memset(a, -1, sizeof(a))
 19 #define mem2(a) memset(a, 0x3f, sizeof(a))
 20 #define rep(i, a, n) for(int i = a; i<n; i++)
 21 #define ull unsigned long long
 22 typedef pair<int, int> pll;
 23 const double PI = acos(-1.0);
 24 const double eps = 1e-8;
 25 const int mod = 1e9+7;
 26 const int inf = 1061109567;
 27 const int dir[][2] = { {1, 0}, {0, 1}, {0, -1}, {0, 1} };
 28 const int maxn = 4e5+5;
 29 int num, head[maxn*2], s, t, n, m, nn, dis[maxn], flow, cost, cnt, cap[maxn], q[maxn], cur[maxn], vis[maxn];
 30 struct node
 31 {
 32     int to, nextt, c, w;
 33     node(){}
 34     node(int to, int nextt, int c, int w):to(to), nextt(nextt), c(c), w(w) {}
 35 }e[maxn*2];
 36 int spfa() {
 37     int st, ed;
 38     st = ed = 0;
 39     mem2(dis);
 40     ++cnt;
 41     dis[s] = 0;
 42     cap[s] = inf;
 43     cur[s] = -1;
 44     q[ed++] = s;
 45     while(st<ed) {
 46         int u = q[st++];
 47         vis[u] = cnt-1;
 48         for(int i = head[u]; ~i; i = e[i].nextt) {
 49             int v = e[i].to, c = e[i].c, w = e[i].w;
 50             if(c && dis[v]>dis[u]+w) {
 51                 dis[v] = dis[u]+w;
 52                 cap[v] = min(c, cap[u]);
 53                 cur[v] = i;
 54                 if(vis[v] != cnt) {
 55                     vis[v] = cnt;
 56                     q[ed++] = v;
 57                 }
 58             }
 59         }
 60     }
 61     if(dis[t] == inf)
 62         return 0;
 63     cost += dis[t]*cap[t];
 64     flow += cap[t];
 65     for(int i = cur[t]; ~i; i = cur[e[i^1].to]) {
 66         e[i].c -= cap[t];
 67         e[i^1].c += cap[t];
 68     }
 69     return 1;
 70 }
 71 int mcmf() {
 72     flow = cost = 0;
 73     while(spfa())
 74         ;
 75     return cost;
 76 }
 77 void add(int u, int v, int c, int val) {
 78     e[num] = node(v, head[u], c, val); head[u] = num++;
 79     e[num] = node(u, head[v], 0, -val); head[v] = num++;
 80 }
 81 void init() {
 82     mem1(head);
 83     num = cnt = 0;
 84     mem(vis);
 85 }
 86 void input() {
 87     int x, y, w;
 88     while(m--) {
 89         scanf("%d%d%d", &x, &y, &w);
 90         add(x, y, 1, w);
 91         add(y, x, 1, w);
 92     }
 93     add(s, 1, 2, 0);
 94     add(n, t, 2, 0);
 95 }
 96 int main()
 97 {
 98     while(~scanf("%d%d", &n, &m)) {
 99         init();
100         s = 0, t = n+1;
101         input();
102         int ans = mcmf();
103         printf("%d
", ans);
104     }
105     return 0;
106 }