POJ 2135 Farm Tour （最小费用最大流模板）

题目大意：

给你一个n个农场，有m条道路，起点是1号农场，终点是n号农场，现在要求从1走到n，再从n走到1，要求不走重复路径，求最短路径长度。

算法讨论：

最小费用最大流。我们可以这样建模：既然要求不能走重复路，就相当于每条边的容量是1，我们只可以单向流过容量为1的流量。但是要注意，对于每一条边来说，

它可能是去路的边，也可能是回路的边，所以这个图是个无向图。在加边的时候，两个方向的边都要加。所以要加两组的边，流量为1像正常一样加边就可以了。

然后我们考虑，求这个“环”就是相当于求从1..N的两条不相交路径，所以我们建立一个源点连向1，建立一个汇点连向N，然后在这个源点和汇点之间跑MinCostMaxFlow。

这里可能会有一个问题就是，如果这样流的话，流出多条路径怎么办？答案是：凉拌。我们把加入的这两条边的流量设置为2就可以了，这样就保证了从0..N+1只能流两条路径了。

然后就是随意做了。

代码：

  1 #include <iostream>
  2 #include <queue>
  3 #include <cstring>
  4 #include <cstdlib>
  5 #include <algorithm>
  6 #include <cstdio>
  7 using namespace std;
  8 
  9 struct MCMF{
 10     static const int maxn = 3000 + 5;
 11     static const int maxe = 40000 + 5;
 12     static const int oo = 0x3f3f3f3f;
 13     
 14     int n, m, s, t, tot;
 15     int first[maxn], next[maxe];
 16     int u[maxe], v[maxe], cap[maxe], flow[maxe], cost[maxe];
 17     int dis[maxn], inque[maxn], a[maxn], pre[maxn];
 18     
 19     MCMF(){memset(first, -1, sizeof first); tot=0;}
 20     void Clear(){memset(first, -1, sizeof first); tot=0;}
 21     void Add(int from, int to, int cp, int flw, int ct){ 
 22         u[tot] = from; v[tot] = to; cap[tot] = cp; flow[tot] = 0; cost[tot] = ct;
 23         next[tot] = first[u[tot]];
 24         first[u[tot]] = tot; ++ tot;
 25         u[tot] = to; v[tot] = from; cap[tot] = 0; flow[tot] = 0; cost[tot] = -ct;
 26         next[tot] = first[u[tot]];
 27         first[u[tot]] = tot; ++ tot;
 28     }
 29     bool bfs(int &flw, int& ct){
 30         for(int i = 0; i <= n+1; ++ i) dis[i] = oo;
 31         memset(inque, 0, sizeof inque);
 32         a[s] = oo; dis[s] = 0; inque[s] = 1; pre[s] = 0;
 33         
 34         queue <int> q;
 35         q.push(s);
 36         while(!q.empty()){
 37             int now = q.front(); q.pop();
 38             inque[now] = 0;
 39             for(int i = first[now]; i != -1; i = next[i]){
 40                 if(cap[i] > flow[i] && dis[v[i]] > dis[now] + cost[i]){
 41                     dis[v[i]] = dis[now] + cost[i];
 42                     pre[v[i]] = i;
 43                     a[v[i]] = min(a[now], cap[i] - flow[i]);
 44                     if(!inque[v[i]]){
 45                         q.push(v[i]); inque[v[i]] = 1;
 46                     }
 47                 }
 48             }
 49         }
 50         if(dis[t] == oo) return false;
 51         flw += a[t];
 52         ct += dis[t] * a[t];
 53         int now = t;
 54         while(now != s){
 55             flow[pre[now]] += a[t];
 56             flow[pre[now]^1] -= a[t];
 57             now = u[pre[now]];
 58         }
 59         return true;
 60     }
 61     int MinCostMaxFlow(int s, int t){
 62         this->s = s; this->t = t;
 63         int flw = 0, ct = 0;
 64         while(bfs(flw, ct));
 65         return ct;
 66     }
 67 }Net;
 68 
 69 #define ONLINE_JUDGE
 70 int main(){
 71 #ifndef ONLINE_JUDGE
 72     freopen("Poj2135.in", "r", stdin);
 73     freopen("Poj2135.out", "w", stdout);
 74 #endif
 75 
 76     int x, y, z;
 77     scanf("%d%d", &Net.n, &Net.m);
 78     Net.Clear();
 79     Net.Add(0, 1, 2, 0, 0);
 80     Net.Add(Net.n, Net.n+1, 2, 0, 0);
 81     for(int i = 1; i <= Net.m; ++ i){
 82         scanf("%d%d%d", &x, &y, &z);
 83         Net.Add(x, y, 1, 0, z);
 84         Net.Add(y, x, 1, 0, z);
 85     }
 86     printf("%d
", Net.MinCostMaxFlow(0, Net.n+1));
 87 
 88 #ifndef ONLINE_JUDGE
 89     fclose(stdin); fclose(stdout);
 90 #endif
 91     return 0;
 92 }
 93 /*
 94 Poj2135.in
 95 10 15
 96 7 1 13784
 97 6 1 31692
 98 4 9 16318
 99 5 10 521
100 10 3 16420
101 5 2 11817
102 6 4 29070
103 8 5 13614
104 2 9 17168
105 8 1 19260
106 1 2 6076
107 2 3 1038
108 3 6 12917
109 2 6 17815
110 10 4 26493
111 
112 Poj2135.out
113 56929
114 */

POJ 2135