最大流（网络流基础概念+三个算法）

容量网络:设G(V,E),是一个有向网络,在V中指定了一个顶点,称为源点(记为Vs),以及另一个顶点,称为汇点(记为Vt);对于每一条弧<u,v>属于E,对应有一个权值c(u,v)>0,称为弧的容量.通常吧这样的有向网络G称为容量网络.

弧的流量:通过容量网络G中每条弧<u,v>,上的实际流量(简称流量),记为f(u,v);

网络流:所有弧上流量的集合f={f(u,v)},称为该容量网络的一个网络流.

可行流:在容量网络G中满足以下条件的网络流f,称为可行流.

    a.弧流量限制条件:   0<=f(u,v)<=c(u,v);

    b:平衡条件:即流入一个点的流量要等于流出这个点的流量,(源点和汇点除外).

若网络流上每条弧上的流量都为0,则该网络流称为零流.

伪流:如果一个网络流只满足弧流量限制条件,不满足平衡条件,则这种网络流为伪流,或称为容量可行流.(预流推进算法有用)

最大流:在容量网络中,满足弧流量限制条件,且满足平衡条件并且具有最大流量的可行流,称为网络最大流,简称最大流.

弧的类型:

a.饱和弧:即f(u,v)=c(u,v);

b.非饱和弧:即f(u,v)<c(u,v);

c.零流弧:即f(u,v)=0;

d.非零流弧:即f(u,v)>0.

链:在容量网络中,称顶点序列(u1,u2,u3,u4,..,un,v)为一条链要求相邻的两个顶点之间有一条弧.

设P是G中一条从Vs到Vt的链,约定从Vs指向Vt的方向为正方向.在链中并不要求所有的弧的方向都与链的方向相同.

a.前向弧:(方向与链的正方向一致的弧),其集合记为P+,

b.后向弧:(方向与链的正方向相反的弧),其集合记为P-.

增广路:

设f是一个容量网络G中的一个可行流,P是从Vs到Vt 的一条链,若P满足以下条件:

a.P中所有前向弧都是非饱和弧,

b.P中所有后向弧都是非零弧.

则称P为关于可行流f 的一条增广路.

沿这增广路改进可行流的操作称为增广.

残留容量:给定容量网络G(V,E),及可行流f,弧<u,v>上的残留容量记为cl(u,v)=c(u,v)-f(u,v).每条弧上的残留容量表示这条弧上可以增加的流量.因为从顶点u到顶点v的流量减少,等效与从顶点v到顶点u的流量增加,所以每条弧<u,v>上还有一个反方向的残留容量cl(v,u)=-f(u,v).

残留网络:设有容量网络G(V,E)及其上的网络流f,G关于f的残留网络记为G(V',E').其中G'的顶点集V'和G中顶点集G相同,V'=V.对于G中任何一条弧<u,v>,如果f(u,v)<c(u,v),那么在G'中有一条弧<u,v>属于E',其容量为c'(u,v)=c(u,v)-f(u,v),如果f(u,v)>0,则在G'中有一条弧<v,u>属于E',其容量为c'(v,u)=f(u,v).残留网络也称为剩余网络.



下面是所有最大流算法的精华部分：引入反向边

为什么要有反向边呢？

 

我们第一次找到了1-2-3-4这条增广路，这条路上的delta值显然是1。于是我们修改后得到了下面这个流。（图中的数字是容量）

 

这时候(1,2)和(3,4)边上的流量都等于容量了，我们再也找不到其他的增广路了，当前的流量是1。

但这个答案明显不是最大流，因为我们可以同时走1-2-4和1-3-4，这样可以得到流量为2的流。

那么我们刚刚的算法问题在哪里呢？问题就在于我们没有给程序一个”后悔”的机会，应该有一个不走(2-3-4)而改走(2-4)的机制。那么如何解决这个问题呢？回溯搜索吗？那么我们的效率就上升到指数级了。

而这个算法神奇的利用了一个叫做反向边的概念来解决这个问题。即每条边(I,j)都有一条反向边(j,i)，反向边也同样有它的容量。

我们直接来看它是如何解决的：

在第一次找到增广路之后，在把路上每一段的容量减少delta的同时，也把每一段上的反方向的容量增加delta。即在Dec(c[x,y],delta)的同时，inc(c[y,x],delta)

我们来看刚才的例子，在找到1-2-3-4这条增广路之后，把容量修改成如下

这时再找增广路的时候，就会找到1-3-2-4这条可增广量，即delta值为1的可增广路。将这条路增广之后，得到了最大流2。

 

那么，这么做为什么会是对的呢？我来通俗的解释一下吧。

事实上，当我们第二次的增广路走3-2这条反向边的时候，就相当于把2-3这条正向边已经是用了的流量给”退”了回去，不走2-3这条路，而改走从2点出发的其他的路也就是2-4。（有人问如果这里没有2-4怎么办，这时假如没有2-4这条路的话，最终这条增广路也不会存在，因为他根本不能走到汇点）同时本来在3-4上的流量由1-3-4这条路来”接管”。而最终2-3这条路正向流量1，反向流量1，等于没有流量。

这就是这个算法的精华部分，利用反向边，使程序有了一个后悔和改正的机会


第一个隆重登场的算法是 EK（Edmond—Karp）算法

感谢http://www.cnblogs.com/zsboy/archive/2013/01/27/2878810.html 的博文，里面有很详细的我要给出的第一个代码的模板和对于该算法的深刻理解

先给出模板（也是为了方便以后自己查阅）

[cpp]  view plain  copy
  1. <strong><span style="font-size:12px;">#include <iostream>  
  2. #include <queue>  
  3. #include<string.h>  
  4. using namespace std;  
  5. #define arraysize 201  
  6. int maxData = 0x7fffffff;  
  7. int capacity[arraysize][arraysize]; //记录残留网络的容量  
  8. int flow[arraysize];                //标记从源点到当前节点实际还剩多少流量可用  
  9. int pre[arraysize];                 //标记在这条路径上当前节点的前驱,同时标记该节点是否在队列中  
  10. int n,m;  
  11. queue<int> myqueue;  
  12. int BFS(int src,int des)  
  13. {  
  14.     int i,j;  
  15.     while(!myqueue.empty())       //队列清空  
  16.         myqueue.pop();  
  17.     for(i=1;i<m+1;++i)  
  18.     {  
  19.         pre[i]=-1;  
  20.     }  
  21.     pre[src]=0;  
  22.     flow[src]= maxData;  
  23.     myqueue.push(src);  
  24.     while(!myqueue.empty())  
  25.     {  
  26.         int index = myqueue.front();  
  27.         myqueue.pop();  
  28.         if(index == des)            //找到了增广路径  
  29.             break;  
  30.         for(i=1;i<m+1;++i)  
  31.         {  
  32.             if(i!=src && capacity[index][i]>0 && pre[i]==-1)  
  33.             {  
  34.                  pre[i] = index; //记录前驱  
  35.                  flow[i] = min(capacity[index][i],flow[index]);   //关键：迭代的找到增量  
  36.                  myqueue.push(i);  
  37.             }  
  38.         }  
  39.     }  
  40.     if(pre[des]==-1)      //残留图中不再存在增广路径  
  41.         return -1;  
  42.     else  
  43.         return flow[des];  
  44. }  
  45. int maxFlow(int src,int des)  
  46. {  
  47.     int increasement= 0;  
  48.     int sumflow = 0;  
  49.     while((increasement=BFS(src,des))!=-1)  
  50.     {  
  51.          int k = des;          //利用前驱寻找路径  
  52.          while(k!=src)  
  53.          {  
  54.               int last = pre[k];  
  55.               capacity[last][k] -= increasement; //改变正向边的容量  
  56.               capacity[k][last] += increasement; //改变反向边的容量  
  57.               k = last;  
  58.          }  
  59.          sumflow += increasement;  
  60.     }  
  61.     return sumflow;  
  62. }  
  63. int main()  
  64. {  
  65.     int i,j;  
  66.     int start,end,ci;  
  67.     while(cin>>n>>m)  
  68.     {  
  69.         memset(capacity,0,sizeof(capacity));  
  70.         memset(flow,0,sizeof(flow));  
  71.         for(i=0;i<n;++i)  
  72.         {  
  73.             cin>>start>>end>>ci;  
  74.             if(start == end)               //考虑起点终点相同的情况  
  75.                continue;  
  76.             capacity[start][end] +=ci;     //此处注意可能出现多条同一起点终点的情况  
  77.         }  
  78.         cout<<maxFlow(1,m)<<endl;  
  79.     }  
  80.     return 0;  
  81. }</span></strong>  


EK算法的核心
反复寻找源点s到汇点t之间的增广路径，若有，找出增广路径上每一段[容量-流量]的最小值delta，若无，则结束。
在寻找增广路径时，可以用BFS来找，并且更新残留网络的值(涉及到反向边)。
而找到delta后，则使最大流值加上delta，更新为当前的最大流值。

对于BFS找增广路：

1.         flow[1]=INF，pre[1]=0;

        源点1进队列，开始找增广路，capacity[1][2]=40>0，则flow[2]=min(flow[1],40)=40;

        capacity[1][4]=20>0,则flow[4]=min(flow[1],20)=20;

        capacity[2][3]=30>0,则flow[3]=min(folw[2]=40，30)=30；

        capacity[2][4]=30,但是pre[4]=1(已经在capacity[1][4]这遍历过4号点了)

        capacity[3][4].....

        当index=4（汇点），结束增广路的寻找

        传递回increasement（该路径的流），利用前驱pre寻找路径

路径也自然变成了这样：

2.flow[1]=INF，pre[1]=0;

 源点1进队列，开始找增广路，capacity[1][2]=40>0，则flow[2]=min(flow[1],40)=40;

        capacity[1][4]=0!>0,跳过

        capacity[2][3]=30>0,则flow[3]=min(folw[2]=40，30)=30；

        capacity[2][4]=30,pre[4]=2，则flow[2][4]=min(flow[2]=40,20)=20;

        capacity[3][4].....

        当index=4（汇点），结束增广路的寻找

        传递回increasement（该路径的流），利用前驱pre寻找路径

 图也被改成

  

接下来同理

这就是最终完成的图，最终sumflow=20+20+10=50（这个就是最大流的值）


第二个隆重登场的算法，Ford-Fulkerson算法，简单易懂，老少皆宜


基于邻接矩阵的一个模板

[cpp]  view plain  copy
  1. <strong><span style="font-size:12px;">#include <iostream>  
  2. #include <cstdio>  
  3. #include <cstring>  
  4. #include <cmath>  
  5. #include <algorithm>  
  6. using namespace std;  
  7. int map[300][300];  
  8. int used[300];  
  9. int n,m;  
  10. const int INF = 1000000000;  
  11. int dfs(int s,int t,int f)  
  12. {  
  13.     if(s == t) return f;  
  14.     for(int i = 1 ; i <= n ; i ++) {  
  15.         if(map[s][i] > 0 && !used[i]) {  
  16.             used[i] = true;  
  17.             int d = dfs(i,t,min(f,map[s][i]));  
  18.             if(d > 0) {  
  19.                 map[s][i] -= d;  
  20.                 map[i][s] += d;  
  21.                 return d;  
  22.             }  
  23.         }  
  24.     }  
  25. }  
  26. int maxflow(int s,int t)  
  27. {  
  28.     int flow = 0;  
  29.     while(true) {  
  30.         memset(used,0,sizeof(used));  
  31.         int f = dfs(s,t,INF);//不断找从s到t的增广路  
  32.         if(f == 0) return flow;//找不到了就回去  
  33.         flow += f;//找到一个流量f的路  
  34.     }  
  35. }  
  36. int main()  
  37. {  
  38.     while(scanf("%d%d",&m,&n) != EOF) {  
  39.         memset(map,0,sizeof(map));  
  40.         for(int i = 0 ; i < m ; i ++) {  
  41.             int from,to,cap;  
  42.             scanf("%d%d%d",&from,&to,&cap);  
  43.             map[from][to] += cap;  
  44.         }  
  45.         cout << maxflow(1,n) << endl;  
  46.     }  
  47.     return 0;</span>  
  48. }</strong>  

下面是我用vector写的Ford-Fulkerson算法的本题代码
[cpp]  view plain  copy
  1. <span style="font-size:12px;"><strong>#include <cstdio>  
  2. #include <string.h>  
  3. #include <vector>  
  4. #include <algorithm>  
  5. using namespace std;  
  6. int const inf = 0x3f3f3f3f;  
  7. int const MAX = 300;  
  8. struct Node  
  9. {  
  10.     int to;  //与这个点相连的点  
  11.     int cap; //以这个射出的边的容量  
  12.     int rev; //这个点的反向边  
  13. };  
  14. vector<Node> v[MAX];  
  15. bool used[MAX];  
  16.   
  17. void add_node(int from, int to, int cap)//重边情况不影响  
  18. {  
  19.     v[from].push_back((Node){to, cap, v[to].size()});  
  20.     v[to].push_back((Node){from, 0, v[from].size() - 1});  
  21. }  
  22. int dfs(int s, int t, int f)  
  23. {  
  24.     if(s == t)  
  25.         return f;  
  26.     used[s] = true;  
  27.     for(int i = 0; i < v[s].size(); i++){  
  28.         Node &tmp = v[s][i];  
  29.         if(used[tmp.to] == false && tmp.cap > 0){  
  30.             int d = dfs(tmp.to, t, min(f, tmp.cap));  
  31.             if(d > 0){  
  32.                 tmp.cap -= d;  
  33.                 v[tmp.to][tmp.rev].cap += d;  
  34.                 return d;  
  35.             }  
  36.         }  
  37.     }  
  38.     return 0;  
  39. }  
  40. int max_flow(int s, int t)  
  41. {  
  42.     int flow = 0;  
  43.     while(1){  
  44.         memset(used, false, sizeof(used));  
  45.         int f = dfs(s, t, inf);  
  46.         if(f == 0)  
  47.             return flow;  
  48.         flow += f;  
  49.     }  
  50.     return flow;  
  51. }  
  52. int main()  
  53. {  
  54.     int n, m;  
  55.     while(scanf("%d %d", &n, &m) != EOF){  
  56.         for(int i = 0; i <= m; i++)  
  57.             v[i].clear();  
  58.         int u1, v1, w;  
  59.         for(int i = 1; i <= n; i++){  
  60.             scanf("%d %d %d", &u1, &v1, &w);  
  61.             add_node(u1, v1, w);  
  62.         }  
  63.         printf("%d\n", max_flow(1, m));  
  64.     }  
  65.     return 0;  
  66. }</strong></span>  

第三种方法：Dinic算法，可以看作是两种方法的结合体，它进行了一定的优化，对于某些横边多的图，运行速度方面得到了大幅提升

Dinic算法的基本思路:
       根据残量网络计算层次图。

       在层次图中使用DFS进行增广直到不存在增广路

       重复以上步骤直到无法增广 

  • 层次图:分层图,以[从原点到某点的最短距离]分层的图,距离相等的为一层,(比如上图的分层为{1},{2,4},{3})
       观察前面的dfs算法，对于层次相同的边，会经过多次重复运算，很浪费时间，那么，可以考虑先对原图分好层产生新的层次图，即保存了每个点的层次，注意，很多人会把这里的边的最大容量跟以前算最短路时的那个权值混淆，其实这里每个点之间的距离都可以看作单位距离，然后对新图进行dfs，这时的dfs就非常有层次感，有筛选感了，同层次的点不可能在同一跳路径中，直接排除。那么运行速度就会快很多了。
[cpp]  view plain  copy
  1. <span style="font-size:12px;"><strong>#include <cstdio>  
  2. #include <string.h>  
  3. #include <queue>  
  4. using namespace std;  
  5. int const inf = 0x3f3f3f3f;  
  6. int const MAX = 205;  
  7. int n, m;  
  8. int c[MAX][MAX], dep[MAX];//dep[MAX]代表当前层数  
  9.   
  10. int bfs(int s, int t)//重新建图，按层次建图  
  11. {  
  12.     queue<int> q;  
  13.     while(!q.empty())  
  14.         q.pop();  
  15.     memset(dep, -1, sizeof(dep));  
  16.     dep[s] = 0;  
  17.     q.push(s);  
  18.     while(!q.empty()){  
  19.         int u = q.front();  
  20.         q.pop();  
  21.         for(int v = 1; v <= m; v++){  
  22.             if(c[u][v] > 0 && dep[v] == -1){//如果可以到达且还没有访问，可以到达的条件是剩余容量大于0，没有访问的条件是当前层数还未知  
  23.                 dep[v] = dep[u] + 1;  
  24.                 q.push(v);  
  25.             }  
  26.         }  
  27.     }  
  28.     return dep[t] != -1;  
  29. }  
  30.   
  31. int dfs(int u, int mi, int t)//查找路径上的最小流量  
  32. {  
  33.     if(u == t)  
  34.         return mi;  
  35.     int tmp;  
  36.     for(int v = 1; v <= m; v++){  
  37.         if(c[u][v] > 0 && dep[v] == dep[u] + 1  && (tmp = dfs(v, min(mi, c[u][v]), t))){  
  38.             c[u][v] -= tmp;  
  39.             c[v][u] += tmp;  
  40.             return tmp;  
  41.         }  
  42.     }  
  43.     return 0;  
  44. }  
  45.   
  46. int dinic()  
  47. {  
  48.     int ans = 0, tmp;  
  49.     while(bfs(1, m)){  
  50.         while(1){  
  51.             tmp = dfs(1, inf, m);  
  52.             if(tmp == 0)  
  53.                 break;  
  54.             ans += tmp;  
  55.         }  
  56.     }  
  57.     return ans;  
  58. }  
  59.   
  60. int main()  
  61. {  
  62.     while(~scanf("%d %d", &n, &m)){  
  63.         memset(c, 0, sizeof(c));  
  64.         int u, v, w;  
  65.         while(n--){  
  66.             scanf("%d %d %d", &u, &v, &w);  
  67.             c[u][v] += w;  
  68.         }  
  69.         printf("%d\n", dinic());  
  70.     }  
  71.     return 0;  
  72. }</strong></span>  

全部评论

相关推荐

11-24 10:10
华中科技大学 Java
点赞 评论 收藏
分享
11-24 16:40
合肥学院 硬件产品经理
点赞 评论 收藏
分享
11-07 13:23
Nanyang Technological University 自然语言处理
想找个大厂日常实习，半年以上
这个bg能找到吗
爱看电影的杨桃allin春招：我感觉你在炫耀
点赞 评论 收藏
分享
10-22 09:27
莆田学院 软件测试
点赞 评论 收藏
分享
11-24 11:23
门头沟学院 C++
点赞 评论 收藏
分享
1 收藏 评论
分享

全站热榜

正在热议
# 25届秋招总结 #
356622次浏览 3479人参与
# 我的实习求职记录 #
6089849次浏览 83713人参与
# 阿里云管培生offer #
42636次浏览 966人参与
# 地方国企笔面经互助 #
5329次浏览 13人参与
# 职场吐槽大会 #
90959次浏览 752人参与
# 选完offer后，你后悔学本专业吗 #
23125次浏览 165人参与
# 北方华创开奖 #
50398次浏览 451人参与
# ai智能作图 #
4320次浏览 79人参与
# 运营商笔面经互助 #
92953次浏览 1336人参与
# 实习中的菜狗时刻 #
279044次浏览 2741人参与
# 腾讯求职进展汇总 #
201031次浏览 1668人参与
# 如果有时光机，你最想去到哪个年纪？ #
25209次浏览 524人参与
# 当下环境，你会继续卷互联网，还是看其他行业机会 #
37960次浏览 345人参与
# 风评不好的公司，你会去吗？ #
20780次浏览 94人参与
# 上班苦还是上学苦呢？ #
91770次浏览 798人参与
# 大疆求职进展汇总 #
413990次浏览 2935人参与
# 国企还是互联网，你怎么选？ #
90251次浏览 704人参与
# 硬件兄弟们 甩出你的华为奖状 #
73992次浏览 609人参与
# 远程面试的尴尬瞬间 #
20629次浏览 296人参与
# 软件开发2024笔面经 #
2326547次浏览 48227人参与
# 如果中了500万，你会离职吗？ #
13817次浏览 145人参与
# 如何一边实习一边秋招 #
1000546次浏览 12701人参与
牛客网
牛客企业服务