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

题目大意：

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

算法讨论：

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

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

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

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

然后就是随意做了。

代码：

 #include <iostream>

 #include <queue>

 #include <cstring>

 #include <cstdlib>

 #include <algorithm>

 #include <cstdio>

 using namespace std;

 struct MCMF{

     static const int maxn =  + ;

     static const int maxe =  + ;

     static const int oo = 0x3f3f3f3f;

     int n, m, s, t, tot;

     int first[maxn], next[maxe];

     int u[maxe], v[maxe], cap[maxe], flow[maxe], cost[maxe];

     int dis[maxn], inque[maxn], a[maxn], pre[maxn];

     MCMF(){memset(first, -, sizeof first); tot=;}

     void Clear(){memset(first, -, sizeof first); tot=;}

     void Add(int from, int to, int cp, int flw, int ct){

         u[tot] = from; v[tot] = to; cap[tot] = cp; flow[tot] = ; cost[tot] = ct;

         next[tot] = first[u[tot]];

         first[u[tot]] = tot; ++ tot;

         u[tot] = to; v[tot] = from; cap[tot] = ; flow[tot] = ; cost[tot] = -ct;

         next[tot] = first[u[tot]];

         first[u[tot]] = tot; ++ tot;

     }

     bool bfs(int &flw, int& ct){

         for(int i = ; i <= n+; ++ i) dis[i] = oo;

         memset(inque, , sizeof inque);

         a[s] = oo; dis[s] = ; inque[s] = ; pre[s] = ;

         queue <int> q;

         q.push(s);

         while(!q.empty()){

             int now = q.front(); q.pop();

             inque[now] = ;

             for(int i = first[now]; i != -; i = next[i]){

                 if(cap[i] > flow[i] && dis[v[i]] > dis[now] + cost[i]){

                     dis[v[i]] = dis[now] + cost[i];

                     pre[v[i]] = i;

                     a[v[i]] = min(a[now], cap[i] - flow[i]);

                     if(!inque[v[i]]){

                         q.push(v[i]); inque[v[i]] = ;

                     }

                 }

             }

         }

         if(dis[t] == oo) return false;

         flw += a[t];

         ct += dis[t] * a[t];

         int now = t;

         while(now != s){

             flow[pre[now]] += a[t];

             flow[pre[now]^] -= a[t];

             now = u[pre[now]];

         }

         return true;

     }

     int MinCostMaxFlow(int s, int t){

         this->s = s; this->t = t;

         int flw = , ct = ;

         while(bfs(flw, ct));

         return ct;

     }

 }Net;

 #define ONLINE_JUDGE

 int main(){

 #ifndef ONLINE_JUDGE

     freopen("Poj2135.in", "r", stdin);

     freopen("Poj2135.out", "w", stdout);

 #endif

     int x, y, z;

     scanf("%d%d", &Net.n, &Net.m);

     Net.Clear();

     Net.Add(, , , , );

     Net.Add(Net.n, Net.n+, , , );

     for(int i = ; i <= Net.m; ++ i){

         scanf("%d%d%d", &x, &y, &z);

         Net.Add(x, y, , , z);

         Net.Add(y, x, , , z);

     }

     printf("%d\n", Net.MinCostMaxFlow(, Net.n+));

 #ifndef ONLINE_JUDGE

     fclose(stdin); fclose(stdout);

 #endif

     return ;

 }

 /*

 Poj2135.in

 10 15

 7 1 13784

 6 1 31692

 4 9 16318

 5 10 521

 10 3 16420

 5 2 11817

 6 4 29070

 8 5 13614

 2 9 17168

 8 1 19260

 1 2 6076

 2 3 1038

 3 6 12917

 2 6 17815

 10 4 26493

 Poj2135.out

 56929

 */

POJ 2135