网络流算法

网络流

最大流的求法

我们对原图的每一条边再存储一条反向边，形成一个含有反向边的新图B。

起初反向边的容量为0，正向边的容量为原图中的容量。

每一次在图B上寻找一条从S->T的路径（注：该路径也就是增广路径），满足该路径上的每一条边的容量均不为0。

找到这条路径上的边的容量的最小值c，给这条路径上的所有边减去c，其反向边加上c。

直到不存在一条S->T的路径，满足该路径上的每一条边的容量均不为0。

此时每一次操作的c的和即为最大流。

正确性

从割的角度来证明最大流的正确性。

割

将原图A中的点分为S1和T1两个点集，S1中含有S点，T1含有T点。A的一种割的大小x就为存在S1和T1，使得S1与T1的并为全集、S1与T1的交为空集且S1与T1之间的所有连边的和为x。

残量网络

上述操作结束后，所有容量不为0的边（注意：是有向的）组成的图C。

根据图C可以求出一个合法的图A的割，且该割的大小就为所有操作的c的和(即流量)

证明：

首先在图C上找到与S联通的点集，即为S1，其余点为T1。

显然S1中一定不会包含T。

记S1与T1之间的边的边集为E。

引理：求最大流过程中所有S->T的路径中不可能会同时经过两条边x,y且x,y均属于E。

采用反证法：如果存在一条路径同时经过两条边x,y且x,y均属于E。

那么这一条路径上的点一定是先属于S1，再属于T1，再属于S1。

如果经过了T1->S1这条边，那么其反向边一定会出现在残量网络中，也就是T1中的某个点其实应该是属于S1的（即与S联通），就与题设不符。

所以E中所有边都会在选出的所有S->T的路径中有且仅出现一次。

所以E就是这个割的集合，且割的大小为E中所有边的大小之和，即所有操作的c的和。

根据图C求出的图A的割的大小是固定的，即为最大流

证明：

假设有两种操作方法使得最后的最大流并不相同。假设第一种操作方法求出的割为E1，第二种操作方法求出的割为E2。

不妨设第一种方法的最大流c1小于第二种c2。

由于E1的割已经限制了网络流的最大流最多为c1，所以与第二种操作方法求出的网络流流量为c2>c1相矛盾。

所以无论从S->T的路径如何选择，按照上述方法最终得到的最大流的大小一定相同，即就是该网络的最大流。

因此这种方法是正确的。

实现方式

本文采用dinic的方法进行实现。

具体方法

朴素的网络流求法的复杂度极高，其瓶颈就在于每一次只能找到一条路径。

但是我们知道很多的路径其实会有很多重复的段，所以我们可以尝试同时找到多条路径来降低复杂度。这就是dinic算法的核心所在。

首先对网络进行bfs分层，记作d数组，（即按照从S出发到每一个点的最少边数进行分类）然后仅保留相邻层之间的边（即x->y存在等价于d(y)=d(x)+1）

这样可以保证求路径的时候不在一个环上打转而陷入死循环，这样也可以让后续对路径的寻找像一棵树一样比较方便。

接着使用dfs的方式来深搜所有可能的路径。一种普遍的方式就是dfs的时候记录当前结点编号和要经过当前结点的路径的c大小之和（即流量的大小之和）。

当前弧优化：如果某个点以后已经不存在到达T的路径了，那么我们就不再去遍历这个点，这个能够保证时间复杂度的正确。

代码：

long long dfs(int x,long long flow){if (x==T) return flow;long long rest=flow;for (int i=1;i<=e_cnt[x];i++){int y=e[x][i].y;if (d[y]==d[x]+1&&v[e[x][i].bh]>0){long long cost=min(v[e[x][i].bh],rest);long long p=dfs(y,cost);if (p==0) d[y]=-1e9;v[e[x][i].bh]-=p;v[e[x][i].bh^1]+=p;rest-=p;if (rest==0) return flow;}}return flow-rest;}

dfs之后我们就再次进行bfs，如此往复，直到dfs之后不再存在从S到T的路径。

整个代码如下：

#include#include#define N 3000001using namespace std;int tot,n,m,S,T;int pd[N],h[N],e_cnt[N],d[N];long long v[N];struct node{int y,bh;};vector<node>e[N];void insert(int x,int y,long long z){tot++;e_cnt[x]++;e[x].resize(e_cnt[x]+1);e[x][e_cnt[x]].y=y;e[x][e_cnt[x]].bh=tot;v[tot]=z;}bool bfs(){for (int i=1;i<=n;i++) d[i]=-1e9;int l=1,r=1;h[l]=S;d[S]=0;while (l<=r){int u=h[l];for (int i=1;i<=e_cnt[u];i++){int y=e[u][i].y;if (d[y]==-1e9&&v[e[u][i].bh]>0){d[y]=d[u]+1;if (y==T) return true;r++;h[r]=y;}}l++;}return false;}long long dfs(int x,long long flow){if (x==T) return flow;long long rest=flow;for (int i=1;i<=e_cnt[x];i++){int y=e[x][i].y;if (d[y]==d[x]+1&&v[e[x][i].bh]>0){long long cost=min(v[e[x][i].bh],rest);long long p=dfs(y,cost);if (p==0) d[y]=-1e9;v[e[x][i].bh]-=p;v[e[x][i].bh^1]+=p;rest-=p;if (rest==0) return flow;}}return flow-rest;}int main(){freopen("maxflow.in","r",stdin);freopen("maxflow.out","w",stdout);scanf("%d%d%d%d",&n,&m,&S,&T);for (int i=1;i<=n;i++){e_cnt[i]=0;e[i].resize(2);}tot=1;for (int i=1;i<=m;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);insert(x,y,z);insert(y,x,0);}long long maxflow=0;while (bfs())maxflow+=dfs(S,1e14);printf("%lld\n",maxflow);}

时间复杂度的计算与证明

第一部分 dfs的时间复杂度

我们知道，只要一次寻找路径是有效的，即找到了至少一条路径，那么就会有至少一条边的容量变为0。

也就是说在拥有当前弧优化的条件下，dfs(k,x)被调用的次数不会超过 |V||E|。所以只要对于每一个点遍历边的时候都使得会有效调用dfs，那么一次dfs的复杂度就会是|V||E|（注：上述代码中dfs的复杂度其实并不正确，但是由于上限十分宽松，没有必要一定要将复杂度写得非常严谨）。

第二部分 bfs的次数

引理：对于所有的结点x，记d(x,y)表示第y次bfs后的层数，有d(x,y)>=d(x,y-1)

证明：对层数进行数归。假设1~t-1层的点都已经满足。

对t+1层的点进行考虑，即假设d(x,p)=t。

任取一条从S->b的路径，

当这条路径上存在a->b，这条边在第p次dfs之后并不存在：

假设a->b是离x最近的一条原先不存在的边。则在d(a,p-1)>=d(b,p-1)，且d(a,p)+1=d(b,p)

由于b->x在上一次的图中仍然存在，所以有d(b,p-1)+len(b,p)>=d(x,p-1)。

由于d(x,p)=d(a,p)+len(b,p)+1且d(a,p)>=d(a,p-1)>=d(b,p-1)，所以d(x,p)>=d(b,p-1)+len(b,p)+1，即d(x,p)>d(x,p-1)。

而当不存在a->b的时候，有d(x,p)=d(x,p-1)。

综上，有d(x,y)>=d(x,y-1)。

而每一次dfs之后保留原先存在的边之后S与T不再联通，所以从S到T的最短路径上一定存在原先并不存在的边。所以d(T,y)>d(T,y-1)。

而d(T,y)<=|V|恒成立。所以bfs的次数最多为|V|。

因此总时间复杂度为|V|^2*|E|。

但是很难将这种方法卡到复杂度的上界，所以它跑大部分的规模是10^5的图都是绰绰有余的。

来源地址：https://blog.csdn.net/sulvshuo/article/details/131491835