网络流最经典的入门题各种网络算法都能AC。

浏览数：20 / 时间：2015年06月08日

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　Drainage Ditches

题目抽象：给你m条边u,v,c。 n个定点，源点1，汇点n.求最大流。最好的入门题，各种算法都可以拿来练习

（1）：一般增广路算法 ford()

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cmath>
  5 #include <algorithm>
  6 #include <string>
  7 #include <vector>
  8 #include <set>
  9 #include <map>
 10 #include <stack>
 11 #include <queue>
 12 #include <sstream>
 13 #include <iomanip>
 14 using namespace std;
 15 typedef long long LL;
 16 const int INF = 0x4fffffff;
 17 const double EXP = 1e-5;
 18 const int MS = 10005;
 19 const int SIZE = 10005;
 20 
 21 struct edge
 22 {
 23     int c, f;
 24 }edges[MS][MS];
 25 
 26 int n, m;
 27 
 28 int flag[MS];
 29 int pre[MS];
 30 int alpha[MS];
 31 
 32 int que[SIZE];
 33 
 34 int u;
 35 int qs, qe;
 36 int i, j;
 37 
 38 void ford()
 39 {
 40     while (1)
 41     {
 42         //  label method
 43         memset(flag, 0xff, sizeof(flag));
 44         memset(pre, 0xff, sizeof(pre));
 45         memset(alpha, 0xff, sizeof(alpha));
 46         flag[1] = 0;
 47         pre[1] = 0;
 48         alpha[1] = INF;
 49         qs = qe = 0;
 50         que[qe++] = 1;
 51 
 52         while (qs < qe&&flag[n ] == -1)
 53         {
 54             u = que[qs++];
 55             for (int i = 1; i <= n; i++)
 56             {
 57                 if (flag[i] == -1)
 58                 {
 59                     if (edges[u][i].c >0&&edges[u][i].f < edges[u][i].c)
 60                     {
 61                         flag[i] = 0; pre[i] = u;
 62                         alpha[i] = min(alpha[u], edges[u][i].c - edges[u][i].f);
 63                         que[qe++] = i;
 64                     }
 65                     else if (edges[i][u].c>0&&edges[i][u].f>0)
 66                     {
 67                         flag[i] = 0; pre[i] = -u;
 68                         alpha[i] = min(alpha[u], edges[i][u].f);
 69                         que[qe++] = i;
 70                     }
 71                 }
 72             }
 73             flag[u] = 1;
 74         }    //  END OF WHILE
 75         if (flag[n ] == -1 || alpha[n ] == 0)
 76             break;       //  END OF WHILE
 77 
 78         int k1 = n , k2 = abs(pre[k1]);
 79         int a = alpha[n ];
 80         while (1)
 81         {
 82             if (edges[k2][k1].c>0)         //用f是否==INF来判断正向
 83                 edges[k2][k1].f += a;
 84             else
 85                 edges[k1][k2].f -= a;
 86             if (k2 == 1)
 87                 break;
 88             k1 = k2;
 89             k2 = abs(pre[k1]);
 90         }     //  END OF WHILE
 91     }  //  END OF WHILE
 92 
 93     int max_flow = 0;
 94     for (int i = 1; i <=n; i++)
 95     {
 96         for (int j = 1; j <=n; j++)
 97         {
 98             if (i == 1 && edges[i][j].f >0)
 99                 max_flow += edges[i][j].f;
100           //  if (edges[i][j].f > 0)
101            //     printf("%d-->%d: %d\n", i, j, edges[i][j].f);
102         }
103     }
104     printf("%d\n", max_flow);
105 }
106 
107 int main()
108 {
109     int u, v, c, f;
110     while(scanf("%d%d",&m,&n)!=EOF)
111     {
112           for (int i = 0; i <= n; i++)
113             for (int j = 0; j <= n; j++)
114                  // edges[i][j].c = edges[i][j].f = INF;
115                  edges[i][j].c=edges[i][j].f=0;
116           for (int i = 0; i < m; i++)
117           {
118               //scanf("%d%d%d%d", &u, &v, &c, &f);
119               scanf("%d%d%d",&u,&v,&c);         //   这里是零流
120               edges[u][v].c +=c;                           //  可能有重边
121              // edges[u][v].f = f;
122           }
123           ford();
124     }
125     return 0;
126 }