一、什么是最大流问题 

假设现在有一个地下水管道网络，有m根管道，n个管道交叉点，现在自来水厂位于其中一个点，向网络中输水，隔壁老王在另外一个点接水，已知由于管道修建的年代不同，有的管道能承受的水流量较大，有的较小，现在求在自来水厂输入的水不限的情况下，隔壁老王能接到的水的最大值？

为解决该问题，可以将输水网络抽象成一个联通的有向图，每根管道是一条边，交叉点为一个结点，从u流向v的管道能承受的最大流量称为容量，设为cap[u][v]，而该管道实际流过的流量设为flow[u][v]，自来水厂称为源点s，隔壁老王家称为汇点t，则该问题求的是最终流入汇点的总流量flow的最大值。

 

 

 

二、思路分析

关于最大流问题的解法大致分为两类：增广路算法和预流推进算法。增广路算法的特点是代码量小，适用范围广，因此广受欢迎；而预流推进算法代码量比较大，经常达到200+行，但运行效率略高，如果腹黑的出题人要卡掉大多数人的code，那么预流推进则成为唯一的选择。。。。( ⊙ o ⊙ )

咳咳。。。先来看下增广路算法：

为了便于理解，先引入一个引理：最大流最小割定理。

在一个连通图中，如果删掉若干条边，使图不联通，则称这些边为此图的一个割集。在这些割集中流量和最小的一个称为最小割。

最大流最小割定理：一个图的最大流等于最小割。

大开脑洞一下，发现此结论显而易见，故略去证明（其实严格的证明反而不太好写，但是很容易看出结论是对的，是吧）。这便是增广路算法的理论基础。

在图上从s到t引一条路径，给路径输入流flow，如果此flow使得该路径上某条边容量饱和，则称此路径为一条增广路。增广路算法的基本思路是在图中不断找增广路并累加在flow中，直到找不到增广路为止，此时的flow即是最大流。可以看出，此算法其实就是在构造最小割。

 

增广路算法

 

 

而预流推进算法的思路比较奇葩（没找到比较好的图，只能自行脑补一下了。。= =#）：

先将s相连的边流至饱和，这种边饱和的结点称为活动点， 将这些活动点加入队列，每次从中取出一个点u,如果存在一个相邻点v是非活动点，则顺着边u->v 推流，直到u变为非活动点。重复此过程，直到队列空，则此时图中的流flow即是最大流。

 

 

三、SAP算法

最短增广路算法（shortest arguement-path algorithm），简称SAP。目前应用最广的算法，代码简短又很好理解，一般情况下效率也比较高。属于增广路算法的一种，特别之处是每次用bfs找的是最短的路径，复杂度为O(n*m^2)。

代码如下：

1 #include
      
         2   3 #include
       
          4   5 #include
        
           6   7 #include
         
            8   9 using namespace std; 10  11   12  13 const int maxn = 300; 14  15 const int INF = 1000000+10; 16  17   18  19 int cap[maxn][maxn]; //流量 20  21 int flow[maxn][maxn]; //容量 22  23 int a[maxn]; //a[i]：从起点 s 到 i 的最小容量 24  25 int p[maxn]; //p[i]: 记录点 i 的父亲 26  27   28  29 int main() 30  31 { 32  33     int n,m; 34  35     while(~scanf("%d%d", &n,&m)) 36  37     { 38  39         memset(cap, 0, sizeof(cap)); //初始化容量为 0 40  41         memset(flow, 0, sizeof(flow)); // 初始化流量为 0 42  43   44  45         int x,y,c; 46  47         for(int i = 1; i <= n; i++) 48  49         { 50  51             scanf("%d%d%d", &x,&y,&c); 52  53             cap[x][y] += c; // 因为可能会出现两个点有多条边的情况,所以需要全部加起来 54  55         } 56  57         int s = 1, t = m; // 第一个点为源点, 第 n 个点为汇点 58  59   60  61         queue
          
            q; 62  63         int f = 0; // 总流量 64  65   66  67         for( ; ; ) // BFS找增广路 68  69         { 70  71             memset(a,0,sizeof(a)); // a[i]:从起点 s 到 i 的最小残量【每次for()时 a[] 重新清 0 因此同时可做标记数组 vis】 72  73             a[s] = INF; // 起点残量无限大 74  75             q.push(s);  // 起点入队 76  77   78  79             while(!q.empty()) // 当队列非空 80  81             { 82  83                 int u = q.front(); 84  85                 q.pop(); // 取出队首并弹出 86  87                 for(int v = 1; v <= m; v++) if(!a[v] && cap[u][v] > flow[u][v]) //找到新节点 v 88  89                     { 90  91                         p[v] = u; 92  93                         q.push(v); // 记录 v 的父亲,并加入 FIFO 队列 94  95                         a[v] = min(a[u], cap[u][v]-flow[u][v]); // s-v 路径上的最小残量【从而保证了最后,每条路都满足a[t]】 96  97                     } 98  99             }100 101  102 103             if(a[t] == 0) break; // 找不到, 则当前流已经是最大流, 跳出循环104 105  106 107             for(int u = t; u != s; u = p[u]) // 从汇点往回走108 109             {110 111                 flow[p[u]][u] += a[t]; //更新正向流112 113                 flow[u][p[u]] -= a[t]; //更新反向流114 115             }116 117             f += a[t]; // 更新从 s 流出的总流量118 119  120 121         }122 123         printf("%d\n",f);124 125     }126 127  128 129     return 0;130 131 }
          
         
        
       
      

 

 

四、Dicnic算法

计算机科学家Dinitz发明的算法，属于增广路算法的一种。与SAP的不同之处有：1.用bfs预处理，按到s的距离划分层次图，记录在h数组里，每次寻找路径只连相邻距离的点；2.用dfs代替bfs找增广路，在寻找失败时便于回溯，提高效率。应用也比较广泛。

复杂度为O(m*n^2)。

所以当n>>m时应该用SAP，m>>n时用Dinic。

代码如下：

1 //n个点，m条边，源点编号1，汇点编号n  2   3 #include
      
         4   5 #include
       
          6   7 #include
        
           8   9 #define N 5005 10  11 #define M 10005 12  13 #define inf 999999999 14  15 using namespace std; 16  17   18  19 int n,m,s,t,num,adj[N],dis[N],q[N]; 20  21 struct edge 22  23 { 24  25 int v,w,pre; 26  27 }e[M]; 28  29 void insert(int u,int v,int w) 30  31 { 32  33 e[num]=(edge){v,w,adj[u]}; 34  35 adj[u]=num++; 36  37 e[num]=(edge){u,0,adj[v]}; 38  39 adj[v]=num++; 40  41 } 42  43 int bfs() 44  45 { 46  47 int i,x,v,tail=0,head=0; 48  49 memset(dis,0,sizeof(dis)); 50  51 dis[s]=1; 52  53 q[tail++]=s; 54  55 while(head
         
          0)102 103 {104 105 e[i].w-=tmp;106 107 e[i^1].w+=tmp;108 109 cost+=tmp;110 111 if(limit==cost)112 113 break;114 115 }116 117 else dis[v]=-1;118 119 }120 121 return cost;122 123 }124 125 int Dinic()126 127 {128 129 int ans=0;130 131 while(bfs())132 133 ans+=dfs(s,inf);134 135 return ans;136 137 }138 139 int main ()140 141 {142 143 while(~scanf("%d%d",&m,&n))144 145 {146 147 int u,v,w;148 149 memset(adj,-1,sizeof(adj));150 151 num=0;152 153 s=1;154 155 t=n;156 157 while(m--)158 159 {160 161 scanf("%d%d%d",&u,&v,&w);162 163 insert(u,v,w);164 165 }166 167 printf("%d\n",Dinic());168 169 }170 171 }
         
        
       
      

 

 

五、HLPP算法

    最高标号预留推进算法（highest-label preflow-push algorithm），简称HLPP。属于预流推进算法的一种，据说是目前已知的效率最高的一种，但代码量大且不好理解，所以用的很少。其思路基本和上面预流推进一致，区别是：在进入算法之前先预处理：用一个bfs以对s的距离划分层次图，记为h数组。

在活动点队列取出u时，如果存在一个相邻点v，使得h[v]=h[u]+1，才顺着边u->v 推流，如果在u变为非活动点之前，边u->v已经饱和，则u要重新标号为h[v]=min{h[u]}+1，并加入队列。复杂度仅为O(√m * n^2)。

代码如下：

1 #include 
      
         2   3 #include 
       
          4   5 #include 
        
           6   7 #include 
         
            8   9 using namespace std; 10  11   12  13 /* 14  15 网络中求最大流HLPP高度标号预流推进算法O(V^2*E^0.5) (无GAP优化简约版) 16  17 参数含义: n代表网络中节点数,第1节点为源点, 第n节点为汇点 18  19 net[][]代表剩余网络,0表示无通路 20  21 earn[]代表各点的盈余 22  23 high[]代表各点的高度 24  25 返回值: 最大流量 26  27 */ 28  29 const int NMAX = 220; 30  31 const int INF = 0x0ffffff; 32  33   34  35 int earn[NMAX], net[NMAX][NMAX], high[NMAX]; 36  37 int n, m; 38  39 queue
          
            SQ; 40  41   42  43 void push(int u, int v) 44  45 { 46  47     int ex = min(earn[u], net[u][v]); 48  49     earn[u] -= ex; 50  51     net[u][v] -= ex; 52  53     earn[v] += ex; 54  55     net[v][u] += ex; 56  57 } 58  59   60  61 void relable(int u) 62  63 { 64  65     int i, mmin = INF; 66  67     for(i=1; i<=n; i++) 68  69     { 70  71         if(net[u][i] > 0 && high[i] >= high[u]) 72  73         { 74  75             mmin = min(mmin, high[i]); 76  77         } 78  79     } 80  81     high[u] = mmin +1; 82  83 } 84  85   86  87 void discharge(int u) 88  89 { 90  91     int i, vn; 92  93     while(earn[u] > 0) 94  95     { 96  97         vn = 0; 98  99         for(i=1; i<=n && earn[u] > 0; i++)100 101         {102 103             if(net[u][i] > 0 && high[u] == high[i]+1)104 105             {106 107                 push(u,i);108 109                 vn ++;110 111                 if(i != n) SQ.push(i);112 113             }114 115         }116 117         if(vn == 0) relable(u);118 119     }120 121 }122 123  124 125 void init_preflow()126 127 {128 129     int i;130 131     memset(high,0,sizeof(high));132 133     memset(earn,0,sizeof(earn));134 135     while(!SQ.empty()) SQ.pop();136 137     high[1] = n+1;138 139     for(i=1; i<=n; i++)140 141     {142 143         if(net[1][i] > 0)144 145         {146 147             earn[i] = net[1][i];148 149             earn[1] -= net[1][i];150 151             net[i][1] = net[1][i];152 153             net[1][i] = 0;154 155             if(i != n) SQ.push(i);156 157         }158 159     }160 161 }162 163  164 165 int high_label_preflow_push()166 167 {168 169     int i,j;170 171     init_preflow();172 173     while(!SQ.empty())174 175     {176 177         int overp = SQ.front();178 179         SQ.pop();180 181         discharge(overp);182 183     }184 185     return earn[n];186 187 }188 189  190 191 int main ()192 193 {194 195 while(~scanf("%d%d",&m,&n))196 197 {198 199 int u,v,w;200 201 memset(net, 0, sizeof net);202 203 while(m--)204 205 {206 207 scanf("%d%d%d",&u,&v,&w);208 209 net[u][v] = w;210 211 //net[v][u] = 0;212 213 }214 215 printf("%d\n",high_label_preflow_push());216 217 }218 219 }
          
         
        
       
      

 

 

六、测试数据

       输入：

       m n

       u1 v1 w1

       u2 v2 w2

       ....

       um vm wm

       输出：

       flow

       

      n -> 点数  m -> 边数  

      ui -> 第i条边的起点

      vi -> 第i条边的终点

      wi -> 第i条边的容量   

      flow -> 最大流 

 

    样例数据如下：

1 Input:  2   3 5 4  4   5 1 2 40  6   7 1 4 20  8   9 2 4 20 10  11 2 3 30 12  13 3 4 10 14  15   16  17 8 6 18  19 1 2 40 20  21 1 4 30 22  23 2 3 20 24  25 2 5 20 26  27 4 5 20 28  29 3 6 15 30  31 5 6 10 32  33 4 6 20 34  35   36  37 10 8 38  39 1 2 20 40  41 2 3 30 42  43 3 4 30 44  45 4 5 20 46  47 1 6 10 48  49 6 7 15 50  51 7 8 15 52  53 8 5 18 54  55 3 6 20 56  57 3 8 15 58  59   60  61 8 5 62  63 1 2 10 64  65 1 3 15 66  67 1 4 20 68  69 2 5 25 70  71 3 5 18 72  73 4 5 16 74  75 2 3 10 76  77 3 4 12 78  79   80  81 13 8 82  83 1 2 10 84  85 1 4 13 86  87 1 7 11 88  89 2 3 21 90  91 4 5 15 92  93 7 8 12 94  95 2 4 17 96  97 4 7 15 98  99 3 5 18100 101 5 8 20102 103 3 6 21104 105 5 6 21106 107 6 8 16108 109  110 111 Output:112 113 50114 115  116 117 45118 119  120 121 30122 123  124 125 41126 127  128 129 34