网络流的最大流算法

发布网友 发布时间：2022-04-19 09:42

我来回答

共1个回答

好二三四 时间：2022-10-11 06:23

定义：从可行流和可增广链关系来看，就可以知道一种寻求最大流的方法：从一个可行流开始，寻求关于这个可行流的可增广链，若存在，则可以经过调整，得到一个新的可行流，其流量比原来的可行流要大，重复这个过程，直到不存在关于该流的可增广链时就得到了最大流。

算法步骤：标号的方法可分为两步：第一步是标号过程，通过标号来寻找可增广链。第二步是调整过程，沿可增广连调整f以增加流量。

热心网友 时间：2023-07-08 00:35

1、augment path，直译为“增广路径”，其思想大致如下：
原有网络为G，设有一辅助图G'，其定义为V(G') = V(G)，E(G')初始值（也就是容量）与E(G)相同。每次操作时从Source点搜索出一条到Sink点的路径，然后将该路径上所有的容量减去该路径上容量的最小值，然后对路径上每一条边<u,v>添加或扩大反方向的容量，大小就是刚才减去的容量。一直到没有路为止。此时辅助图上的正向流就是最大流。
我们很容易觉得这个算法会陷入死循环，但事实上不是这样的。我们只需要注意到每次网络中由Source到Sink的流都增加了，若容量都是整数，则这个算法必然会结束。
寻找通路的时候可以用DFS，BFS最短路等算法。就这两者来说,BFS要比DFS快得多，但是编码量也会相应上一个数量级。
增广路方法可以解决最大流问题，然而它有一个不可避免的缺陷，就是在极端情况下每次只能将流扩大1（假设容量、流为整数），这样会造成性能上的很大问题，解决这个问题有一个复杂得多的算法，就是预推进算法。
2、push label，直译为“预推进”算法。
3、压入与重标记(Push-Relabel)算法
除了用各种方法在剩余网络中不断找增广路(augmenting)的Ford-Fulkerson系的算法外，还有一种求最大流的算法被称为压入与重标记(Push-Relabel)算法。它的基本操作有：压入，作用于一条边，将边的始点的预流尽可能多的压向终点；重标记，作用于一个点，将它的高度（也就是label）设为所有邻接点的高度的最小值加一。Push-Relabel系的算法普遍要比Ford-Fulkerson系的算法快，但是缺点是相对难以理解。
Relabel-to-Front使用一个链表保存溢出顶点，用Discharge操作不断使溢出顶点不再溢出。Discharge的操作过程是：若找不到可被压入的临边，则重标记，否则对临边压入，直至点不再溢出。算法的主过程是：首先将源点出发的所有边充满，然后将除源和汇外的所有顶点保存在一个链表里，从链表头开始进行Discharge，如果完成后顶点的高度有所增加，则将这个顶点置于链表的头部，对下一个顶点开始Discharge。
Relabel-to-Front算法的时间复杂度是O(V^3)，还有一个叫Highest Label Preflow Push的算法复杂度据说是O(V^2*E^0.5)。我研究了一下HLPP，感觉它和Relabel-to-Front本质上没有区别，因为Relabel-to-Front每次前移的都是高度最高的顶点，所以也相当于每次选择最高的标号进行更新。还有一个感觉也会很好实现的算法是使用队列维护溢出顶点，每次对pop出来的顶点discharge，出现了新的溢出顶点时入队。
Push-Relabel类的算法有一个名为gap heuristic的优化，就是当存在一个整数0<k<V，没有任何顶点满足h[v]=k时，对所有h[v]>k的顶点v做更新，若它小于V+1就置为V+1。
cpp程序: #include<cstdio>#include<cstring>#include<algorithm>#include<queue>#define inf 0x7fffffffusingnamespace std;int tt,kase;int nn,m;int H[45],X[1004],P[1004],flow[1004],tot,cap[1005];int d[45];int S,T;void add(int x,int y,int z){P[++tot]=y;X[tot]=H[x];H[x]=tot;flow[tot]=z;cap[tot]=flow[tot];}queue<int> q;bool bfs(){memset(d,0,sizeof(d));d[S]=1; int x;q.push(S);while(!q.empty()){x=q.front();q.pop();for(int i=H[x];i;i=X[i]){if(flow[i]>0&&!d[P[i]]){d[P[i]]=d[x]+1;q.push(P[i]);}}}returnd[T];}int dfs(int x,int a){if(x==T||a==0)return a;int f=a,tmp;for(int i=H[x];i;i=X[i]){if(flow[i]>0&&d[P[i]]==d[x]+1){tmp=dfs(P[i],min(flow[i],a));flow[i]-=tmp;a-=tmp;flow[i^1]+=tmp;if(!a)break;}}if(f==a)d[x]=-1;return f-a;}int Dinic(){int f=0;while(bfs())f+=dfs(S,inf);return f;}int main(){/**输入过程省略**/int maxflow=Dinic();printf(%d\n,maxflow);return 0;}