“网络流博大精深”—sideman语
一个基本的网络流问题
感谢WHD的大力支持
最早知道网络流的内容便是最大流问题，最大流问题很好理解：
解释一定要通俗!
如右图所示,有一个管道系统,节点{1,2,3,4},有向管道{A,B,C,D,E},即有向图一张. [1]是源点,有无限的水量,[4]是汇点,管道容量如图所示.试问[4]点最大可接收的水的流量?
这便是简单的最大流问题,显然[4]点的最大流量为50
死理性派请注意:流量是单位时间内的,总可以了吧!
然而对于复杂图的最大流方法是什么呢,有EK,Dinic,SAP,etc.下面介绍Dinic算法(看代码的直接点这)
Dinic 算法
Dinic算法的基本思路:
- 根据残量网络计算层次图。
- 在层次图中使用DFS进行增广直到不存在增广路
- 重复以上步骤直到无法增广
引自NOCOW,相当简单是吧…
小贴士:
一般情况下在Dinic算法中,我们只记录某一边的剩余流量.
- 残量网络:包含反向弧的有向图,Dinic要循环的,每次修改过的图都是残量网络,
- 层次图:分层图,以[从原点到某点的最短距离]分层的图,距离相等的为一层,(比如上图的分层为{1},{2,4},{3})
- DFS:这个就不用说了吧…
- 增广 :在现有流量基础上发现新的路径,扩大发现的最大流量(注意:增加量不一定是这条路径的流量,而是新的流量与上次流量之差)
- 增广路:在现有流量基础上发现的新路径.(快来找茬,和上一条有何不同?)
- 剩余流量:当一条边被增广之后(即它是增广路的一部分,或者说增广路通过这条边),这条边还能通过的流量.
- 反向弧:我们在Dinic算法中,对于一条有向边,我们需要建立另一条反向边(弧),当正向(输入数据)边剩余流量减少I时,反向弧剩余流量增加I
Comzyh的较详细解释(流程) :
- 用BFS建立分层图 注意:分层图是以当前图为基础建立的,所以要重复建立分层图
- 用DFS的方法寻找一条由源点到汇点的路径,获得这条路径的流量I 根据这条路径修改整个图,将所经之处正向边流量减少I,反向边流量增加I,注意I是非负数
- 重复步骤2,直到DFS找不到新的路径时,重复步骤1
注意(可以无视):
- Dinic(其实其他的好多)算法中寻找到增广路后要将反向边增加I
- Dinic中DFS时只在分层图中DFS，意思是说DFS的下一个节点的Dis(距源点的距离)要比自己的Dis大1,例如在图1中第一个次DFS中,1->2->4 这条路径是不合法的,因为Dis[2]=1;Dis[4]=1;
- 步骤2中“获得这条路径的流量I “实现:DFS函数有参量low,代表从源点到现在最窄的(剩余流量最小)的边的剩余流量,当DFS到汇点是,Low便是我们要的流量I
对于反向弧(反向边)的理解:
这一段不理解也不是不可以,对于会写算法没什么帮助,如果你着急,直接无视即可.
先举一个例子(如右图):
在这幅图中我们首先要增广1->2->4->6,这时可以获得一个容量为2的流,但是如果不建立4->2反向弧的话,则无法进一步增广,最终答案为2,显然是不对的,然而如果建立了反向弧4->2,则第二次能进行1->3->4->2->5->6的增广,最大流为3.
Comzyh对反向弧的理解可以说是”偷梁换柱“,请仔细阅读:在上面的例子中,我们可以看出,最终结果是1->2->5->6和1->2->4->6和1->3->4->6.当增广完1->2->4->5(代号A)后,在增广1->3->4->2->5->6(代号B),相当于将经过节点2的A流从中截流1(总共是2)走2->5>6,而不走2->4>6了,同时B流也从节点4截流出1(总共是1)走4->6而不是4->2->5->6,相当于AB流做加法.
简单的说反向弧为今后提供反悔的机会,让前面不走这条路而走别的路.
Alwa同学非要我给他的文章加一个链接,大家可以看看他的文章: 有关网络流中的反向弧和增广路
Dinic算法的程序实现
最大流算法一直有一个入门经典题:POJ 1273 或者是UCACO 4_2_1 来自NOCOW(中文) 这两个是同一个题
给出这道题的代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
/* Program:POJ 1273 / Dinic Author:Comzyh */ #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #define min(x,y) ((x<y)?(x):(y)) using namespace std; const int MAX=0x5fffffff;// int tab[250][250];//邻接矩阵 int dis[250];//距源点距离,分层图 int q[2000],h,r;//BFS队列 ,首,尾 int N,M,ANS;//N:点数;M,边数 int BFS() { int i,j; memset(dis,0xff,sizeof(dis));//以-1填充 dis[1]=0; h=0;r=1; q[1]=1; while (h<r) { j=q[++h]; for (i=1;i<=N;i++) if (dis[i]<0 && tab[j][i]>0) { dis[i]=dis[j]+1; q[++r]=i; } } if (dis[N]>0) return 1; else return 0;//汇点的DIS小于零,表明BFS不到汇点 } //Find代表一次增广,函数返回本次增广的流量,返回0表示无法增广 int find(int x,int low)//Low是源点到现在最窄的(剩余流量最小)的边的剩余流量 { int i,a=0; if (x==N)return low;//是汇点 for (i=1;i<=N;i++) if (tab[x][i] >0 //联通 && dis[i]==dis[x]+1 //是分层图的下一层 &&(a=find(i,min(low,tab[x][i]))))//能到汇点(a <> 0) { tab[x][i]-=a; tab[i][x]+=a; return a; } return 0; } int main() { //freopen("ditch.in" ,"r",stdin ); //freopen("ditch.out","w",stdout); int i,j,f,t,flow,tans; while (scanf("%d%d",&M,&N)!=EOF){ memset(tab,0,sizeof(tab)); for (i=1;i<=M;i++) { scanf("%d%d%d",&f,&t,&flow); tab[f][t]+=flow; } // ANS=0; while (BFS())//要不停地建立分层图,如果BFS不到汇点才结束 { while(tans=find(1,0x7fffffff))ANS+=tans;//一次BFS要不停地找增广路,直到找不到为止 } printf("%d\n",ANS); } system("pause"); } |
另一道题目是 POJ 1459 使用邻接表，采用当前弧优化
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 |
#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <queue> using namespace std; int N, NP, NC, M; struct Edge { int u, v, cap; Edge() {} Edge(int u, int v, int cap): u(u), v(v), cap(cap) {} } es[150 * 150]; int R, S, T; vector<int> tab[109]; // 边集 int dis[109]; int current[109]; void addedge(int u, int v, int cap) { tab[u].push_back(R); es[R++] = Edge(u, v, cap); // 正向边 tab[v].push_back(R); es[R++] = Edge(v, u, 0); // 反向边容量为0 // 正向边下标通过异或就得到反向边下标, 2 ^ 1 == 3 ; 3 ^ 1 == 2 } int BFS() { queue<int> q; q.push(S); memset(dis, 0x3f, sizeof(dis)); dis[S] = 0; while (!q.empty()) { int h = q.front(); q.pop(); for (int i = 0; i < tab[h].size(); i++) { Edge &e = es[tab[h][i]]; if (e.cap > 0 && dis[e.v] == 0x3f3f3f3f) { dis[e.v] = dis[h] + 1; q.push(e.v); } } } return dis[T] < 0x3f3f3f3f; // 返回是否能够到达汇点 } int dinic(int x, int maxflow) { if (x == T) return maxflow; // i = current[x] 当前弧优化 for (int i = current[x]; i < tab[x].size(); i++) { current[x] = i; Edge &e = es[tab[x][i]]; if (dis[e.v] == dis[x] + 1 && e.cap > 0) { int flow = dinic(e.v, min(maxflow, e.cap)); if (flow) { e.cap -= flow; // 正向边流量降低 es[tab[x][i] ^ 1].cap += flow; // 反向边流量增加 return flow; } } } return 0; // 找不到增广路 退出 } int DINIC() { int ans = 0; while (BFS()) // 建立分层图 { int flow; memset(current, 0, sizeof(current)); // BFS后应当清空当前弧数组 while (flow = dinic(S, 0x3f3f3f3f)) // 一次BFS可以进行多次增广 ans += flow; } return ans; } int main() { while (scanf("%d%d%d%d", &N, &NP, &NC, &M) != EOF) { R = 0; S = N; T = N + 1; for (int i = 0; i <= T; i++) tab[i].clear(); for (int i = 0; i < M; i++) { int u, v, cap; scanf(" (%d,%d)%d", &u, &v, &cap); addedge(u, v, cap); } for (int i = 0; i < NP; i++) { int u, p; scanf(" (%d)%d", &u, &p); addedge(S, u, p); } for (int i = 0; i < NC; i++) { int u, c; scanf(" (%d)%d", &u, &c); addedge(u, T, c); } printf("%d\n", DINIC()); } return 0; } |
原创文章，转载请注明： 转载自Comzyh的博客
本文链接地址: 网络流入门—用于最大流的Dinic算法
果断沙发了不解释！！！！
赞！
已火，再次留名
膜拜WHD神牛
好东西，太感谢了！
好文！大神，能不能再写一点Dinic的优化，比如多路增广，前向弧优化。
当前弧优化是打算写的~
时间复杂度是多少？
O(V^2E)吧
66666666666666
这代码是真心短小精悍！赞*∞
解释棒棒哒，但是没有说清楚原理，就是缺少证明部分，不过看代码倒是思路清晰，喜欢喜欢?。
第二道例题题号是不是写错了。。。好像不是1742，是1459？
还真是
为什么我测试了一组数据出现了错误
10 4
1 2 0
2 1 1
1 3 1
3 1 0
2 3 0
3 2 1
2 4 1
4 2 0
3 4 0
4 3 1
正确的应该是2，结果显示1
是不是反向边没考虑或者反向边没起作用
我看了下没问题呀，对于第一份代码起点是1，终点是4。流量就是1呀。2->3 的流量才是2。
谢谢您的博客~帮助很大呢。
不过为什么第一题在 dfs 的时候不一次找多几条增广路，而是找到一条就 return 了呀？
可以多找几条增广路啊，这是一个改进。
很有帮助，赞!
博主你好，在偷梁换柱那一段，代号A流的序号标错了吧，应该是1246吧？