先强调一下网络流 及最大流的通俗概念吧
(这里引用几个大佬的说法)
算了...自己戳进去看吧 懒得复制了(我不确定大佬后面写的能不能看懂 反正我是看不懂)
https://blog.csdn.net/wzw1376124061/article/details/55001639
(看一下开头对网络流 最大流的通俗概念定义)
好吧那我就假设你知道这些概念了(如果真的没搞懂 可以再去看看一两个大佬的博客开头 一下就可以懂了)
Q1:增广路径是啥玩意儿
就是一条从起点，到终点的一条每条边容量-实际流量>的路
大概有点感觉了吧?
Q2:如何增广?
(我来模拟一下这个过程你就懂了)
这是初始的样子 其中0/8代表8是这条边的容量 0是流量
根据之前说的 先找增广路径 再更新它
于是我们现在先找到一条 1-2-4
然后怎么办，把这条路上的每条边流量都加上每条边容量与流量差的最小值(这个就叫增广!)
此时有两个差 一个是8 一个是6 取其最小 即6
于是变成了这个样子
(我们都知道 一条小溪的水流量取决于最窄的地方 这就是为什么这个地方填6 可以大概理解一下)
然后继续找增广路 找到了1-2-3-4
delta=min(2,1,5) 就等于1
于是加上1
继续找增广路 1-3-4 加上3
找到这儿 已经没有增广路径了 因为没有一条1到4的路径上满足每个流量都小于容量 (比如说1-2-4,2-4的流量等于了容量)
此时的最大流就是6+4=10
--------------------------------
算了我们直接讲算法实现吧。。。
这其实是个已证明的理论 :当且仅当残量网络中不存在增广路时 此时的流是从s到t的最大流
(证明可以去看算法导论上的)
然而这只是一个错误的算法....不过离我们的正解已经很近了
为什么错误呢?因为假如出现这种情况
假如第一次找到的增广路径是1-2-3-4 加上1过后 就不存在其他的增广路径了 这样做出来最大流就是1 然而很明显 答案并不是 显然应该是2
那我们的算法哪里有问题?仔细想想，我们应该给程序一个反悔的机制，也就是相当于第一次找到的不是最优解。用回溯法吗?不太好，这样的复杂度是成指数上升的
那么Ford-Fulkerson算法神奇的利用了一个叫做反向边的概念来解决这个问题。即每条边(i,j)都有一条反向边(j,i)，反向边也同样有它的容量及流量，且初始的流量值就是为正向边的容量。
在第一次找到增广路之后，在把路上每一段的流量增加delta的同时，把反向边的流量减少delta
来看看刚刚的反例(博主太懒了 只画了部分反向边)
找到1-2-4-3这个路径后 为正向边都加上delta=1
就变成了下图
那继续找增广路径 发现1-4-2-3是一条 于是加上delta=1 此时最大流就算出来了 为2
这就是反向边的操作 至于正确性的证明 去看算导吧.....
-----------------------------------------------
这就是求最大流算法的思想 那让我们区分一下Ford-Fulkerson和Edmonds-Karp呢...
Ford-Fulkerson的伪代码在这儿
FORD_FULKERSON(G,s,t) for each edge(u,v)∈E[G] do f[u,v] <— 0 f[v,u] <— rongliang[edge(u,v)]//按照我刚刚讲的就应该这样写 //以上是初始流量 while there exists a path p from s to t in the residual network G do delta(p) <— min{ rongliang[a,b]-f[a,b]}(a,b are two points in p) for each edge(a,b) in p do f[u,v] <— f[u,v]+delta(p) //对于在增广路径上的正向的边，加上增加的流 f[v,u] <— -delta[p]Edmonds-Karp又是啥 其实FF是一种方法 我们可以看到FF的复杂度主要取决于第五行 即找增广路径的方法 而EK是具体实现 主要是通过bfs来找的
//我的EK写法。。。建议邻接矩阵 //题目：洛谷p2740 草地排水 #include<bits/stdc++.h> using namespace std; int m,n,cap[205][205],pre[205],flow[205][205]; bool vis[205]; bool bfs(int s,int t) { memset(pre,-1,sizeof(pre)); memset(vis,false,sizeof(vis)); queue<int> q; q.push(s); vis[s]=true; while(!q.empty()) { int now=q.front(); q.pop(); for(int i=1;i<=n;i++) { if(vis[i]==false&&i!=now&&cap[now][i]-flow[now][i]>0) { q.push(i); pre[i]=now; vis[i]=true; if(i==t) return true; //找到了 } } } return false; } int max_flow(int s,int t) { int ans=0; while(bfs(s,t)) { int delta=0x7fffffff; for(int i=t;i!=s;i=pre[i]) { delta=min(delta,cap[pre[i]][i]-flow[pre[i]][i]); } for(int i=t;i!=s;i=pre[i]) { flow[pre[i]][i]+=delta; flow[i][pre[i]]-=delta; } ans+=delta; //这是一个结论 记住就行 } return ans; } int main() { cin>>m>>n; for(int i=1;i<=m;i++) { int x,y,rl; cin>>x>>y>>rl; //必须是+= 超级阴人.....没有看到一处到另一处不止一条排水沟 cap[x][y]+=rl; cap[y][x]+=rl; flow[x][y]=0; flow[y][x]+=rl; } cout<<max_flow(1,n); return 0; }(我的写法也许和他们有差别 不过真的很好懂)
EK算法时间复杂度:O(nm^2)
-----------------------------------------------------
前两种最大流算法都讲完了 现在进入dinic算法
我们发现之前的算法可能会碰到这种尴尬的情况
一眼可以看出最大流是999+999 但是如果我们的程序一开始就采取了1-2-3-4这条路径...
那么就变成了下图(省去了几个反向边)
而下次增广时 选择1-3-2-4
(注意变化的数字)
这样下去就会陷在这个泥潭之中 如果999这个数字变得更大 比如1e7 那TLE简直是稳稳的
于是我们引入dinic算法
其实我认为 搞懂了EK 直接看dinic的代码是没问题的 特别是博主这种简洁的代码
dinic算法就是为整个图增加了step数组 代表每个点在bfs子树里的层数
这样的话每次从点q dfs到下一点p必须满足step[p]=step[q]+1 这样就不会出现刚刚那尴尬的情况
会有多次bfs 因为图一直在增广 在变化 来更新step数组
这样下去总会求出最大流 证明见算法导论
值得一提的是邻接表的小细节 我写在了“记录容易出错的地方”的那篇文章里 可以去看看
代码里有注释的 可以自己画图 结合代码注释理解
#include<bits/stdc++.h> using namespace std; int s,t,n,m,tot,first[10005],step[10005]; const int INF=0x7fffffff; struct Edge { int to; int next; int flow; int cap; //很多人没有加上flow这个元素 用一个cap就代替了delta 然而我不喜欢 我的写法好理解一点 }edge[400005]; void addedge(int x,int y,int flow,int cap) { edge[tot].to=y; edge[tot].flow=flow; edge[tot].cap=cap; edge[tot].next=first[x]; first[x]=tot++; //注意区分tot在前和后的区别....详见我的那篇记录易错点的博客 } bool bfs(int s,int t) { memset(step,-1,sizeof(step)); step[s]=1; queue<int> q; q.push(s); while(!q.empty()) { int now=q.front(); q.pop(); for(int u=first[now];u!=-1;u=edge[u].next) { int vis=edge[u].to; if(edge[u].cap-edge[u].flow>0&&step[vis]==-1)//这里有一个代替vis数组的感觉 { step[vis]=step[now]+1; q.push(vis); } } } return step[t]!=-1; } int dfs(int s,int t,int flow) //flow是原点到当前点的剩余流量 { if(s==t) return flow; int addflow=0; for(int i=first[s];i!=-1&&addflow<=flow;i=edge[i].next) { int vis=edge[i].to; if(step[vis]==step[s]+1&&edge[i].cap-edge[i].flow>0) { //这这条路径上流量用了，下条路径的可以流过去的就少了(一个点的几个边) 相当于是防止这个流量用完了 int delta=dfs(vis,t,min(flow-addflow,edge[i].cap-edge[i].flow)); addflow+=delta; edge[i].flow+=delta; edge[i^1].flow-=delta; //2^1=3,3^1=2 求反向边编号 } } return addflow; } int max_flow(int s,int t) { int ans=0; while(bfs(s,t)) { ans+=dfs(s,t,INF); } return ans; } int main() { cin>>n>>m>>s>>t; memset(first,-1,sizeof(first)); for(int i=1;i<=m;i++) edge[i].next=-1; for(int i=1;i<=m;i++) { int x,y,rl; cin>>x>>y>>rl; addedge(x,y,0,rl); addedge(y,x,rl,rl); } cout<<max_flow(s,t); return 0; }
转载于:https://www.cnblogs.com/Patrickpwq/articles/9382481.html
