#edu3030. 【教程】网络流入门

【教程】网络流入门

网络流基本概念

网络指的是一个带边权的有向图，G=(V,E)G=(V,E) 一张有向图，每条边 (x,y)∈E(x,y)\in E 都有一个边权 c(x,y)c(x,y) ，是这条边流量的上限，称为容量。

图中有两个特殊的点，入度为 00 的点 S∈VS\in V 和出度为 00 的点 T∈VT \in V，分别称为源点和汇点。

流

设 f(x,y)f(x,y) 是定义在节点二元组 (x∈V,y∈V)(x \in V,y \in V) 上的实数函数，满足：

11. 容量限制：对于每条边，流经该边的流量不得超过该边的容量，即 f(x,y)≤c(x,y)f(x,y) \le c(x,y)。

22. 斜对称性：每条边的流量与其相反边的流量之和为 00 ,即 f(x,y)=−f(x,y)f(x,y)=-f(x,y)。

33. 流守恒性：除源点和汇点外任意点，流入此点的流量和等于流出此点的流量和，也就是中间节点不会存储，即 $\forall x \ne S,x \ne T,\sum_{(u,x) \in E}f(u,x)=\sum_{(x,v)\in E}f(x,v)$。

特别地，若 (x,y)∉E(x,y)\notin E,则 f(x,y)=0f(x,y)=0

f(x,y)f(x,y) 称为网络的流函数。对于边 (x,y)∈E,f(x,y)(x,y)\in E,f(x,y) 称边的流量，c(x,y)−f(x,y)c(x,y)-f(x,y) 为边的剩余容量，很多教程里也称为残量。

在任意时刻，网络中所有节点以及剩余容量大于 00 的边构成的子图被称为“残量网络”。

∑(S,v)∈f(S,v)=∑(u,T)∈f(u,T)\sum_{(S,v)\in f(S,v)}=\sum_{(u,T)\in f(u,T)} 称为整个网络的流量，使得这个值最大，就是最大流问题，本质上最大流问题是 线性规划问题，即给定若干约束条件，使得目标函数值最大。

网络流可以形象地描述为：在不超过容量限制的前提下，“水流”从源点源源不断地产生，流经整个网络，中间节点（除源点和汇点外）不存储流，最终全部流入汇点。

求最大流

求如下图最大流？

网络流 图-1

基于贪心的错误做法

（不能保证每次都能找到最大流）

贪心：

在残量网络上，如果能从源点寻找到汇点的一条增广路（简单路径），循环执行如下操作直到增广路径不存在：

（1）寻找一条增广路；（2）找到这条路径上的瓶颈，也就是最小流量，记为 xx； （3）按 xx 流量从源点流入汇点, ans+=xans+=x ，修改路径上的边。

对于一条边后面使用 f(x,y)/c(x,y)f(x,y)/c(x,y) 进行描述，剩余量,也就是残量 c(x,y)−f(x,y)c(x,y)-f(x,y)。

第一条路径：S−>v1−>v3−>tS->v_1->v_3->t ,瓶颈是 22 ,修改路径上边的流量，此时 v1−>v3满流（阻塞）v_1->v_3 满流（阻塞），相当于这条边去掉;

第二条路径：S−>v2−>v4−>tS->v_2->v_4->t ,瓶颈是 22 ,修改路径上边的流量，此时 S−>v2S->v_2 满流（阻塞），相当于这条边去掉;

第三条路径：S−>v1−>v4−>tS->v_1->v_4->t ,整个路径剩余流量瓶颈是 11 ,给这条路径上各边 +1+1 ,如下图：

网络流 图-2

之后没有增广路径，网络流是 2+2+12+2+1,55 就是这个网络的最大流，但是这种算法并不是任何情况下都能求得最大流。同样是这张图，寻找增广路顺序不同，答案就会有差异。如果寻找增广路顺序如下,网络流是 3+13+1 ：

第一条路径：S−>v1−>v4−>tS->v_1->v_4->t ,流量是 33;

第二条路径：S−>v1−>v3−>tS->v_1->v_3->t ,流量是 11;

网络流 图-3

之后没有增广路径，此时网络流总和是 3+1=43+1=4 ,不是最大流，也就是这种贪心算法不一定找到的是最大流（只是阻塞流）。

简单贪心算法，存在一个明显的缺陷，一旦找到一条路径，不能反悔，这样就会导致求到的网络流不一定是最大的，Ford-Fulkerson 算法通过添加反向边，撤销之前走的路径，保证求到最大流。

Ford-Fulkerson 算法

在残量网络上，循环执行如下操作直到增广路径不存在：

（1）寻找一条增广路；

（2）找到这条路径上的瓶颈，也就是最小流量，记为 xx；

（3）按 xx 流量从源点流入汇点, ans+=xans+=x ，修改路径上的边。

（4）在这条路径上所有边添加反向路径，流量是x。

Ford-Fulkerson方法的正确性依赖于这个定理：当残存网络中不存在一条从s到t的增广路径，那么该图已经达到最大流。

这种算法，存在一种可能，一次只能找到流量为 11 的增广路，如下图：

网络流 图-4

此时，需要循环最大流次去寻找增广路，时间复杂度就是 O(maxfow∗M)O(maxfow*M) ，算法效率较低，不过这种算法证明了通过添加反向边，撤销之前的增广路，一定可以得到最大流，后面 EK,DinicEK,Dinic 等算法都是这种算法的优化。

Edmonds-Karp算法

Ford-Fulkerson 算法时间复杂度依赖于最大流，Edmonds-Karp 证明了通过寻找最短增广路（将图看作无权图，直接BFS），时间复杂不再依赖于最大流，Ford-Fulkson 可以通过任意方法寻找增广路，可以将这种算法看着 FF 的一种特例。

一点重要细节：

2x2x 与 2x+12x+1 是成对出现的, 2x⊕1=2x+12x \oplus 1=2x+1,(2x+1)⊕1=2x(2x+1) \oplus 1=2x 。 若 ii 是边的编号，那么反向边编号就是 i⊕1i \oplus 1,不过边的编号要从 22 开始，那初始 tot=1tot=1。

参考代码如下：

long long ek(int s,int t)
{
	long long maxflow=0;
	while(bfs(s,t))         
    //bfs寻找最短增广路，如果找到返回true，同时记录每个点对应前驱的边号
	{
		int d=1e9,v=t;
		while(v!=s)
		{
			int i=pre[v];
			d=min(d,edge[i].cap-edge[i].flow);
			v=edge[i^1].to;
		}
		maxflow+=d;
		v=t;
		while(v!=s)
		{
			int i=pre[v];
			edge[i].flow+=d;
			edge[i^1].flow-=d;
			v=edge[i^1].to;
		}
	}
	return maxflow;
}

算法时间复杂度：

每轮循环需要 O(M)O(M) 时间寻找最短路，Edmonds-Karp证明了最多需要 O(N∗M)O(N*M) 轮，那么时间复杂度就是 O(NM2)O(NM^2),NN 是点数，MM 是边数。 实际应用则达不到这个上界，效率较高，一般能够处理 103−10410^3-10^4 规模的网络。

P3376【模板】网络最大流 完整参考代码：点击

Dinic算法

Edmons-Karp 每轮可能遍历遍历整个残量网络，但只能找到11 条增广路，还有进一步优化的空间。

DinicDinic 在残量网络上通过 BFSBFS 建分层图，在分层图上寻找的增广路确保是最短路的增广路，然后通过 DFSDFS 沿着层数递增 11 且还有剩余流量 (cap>flow)(cap>flow) 的方向寻找增广路，回溯时增流。一次 DFSDFS 可以实现多次增流，这是Dinic 算法巧妙之处。

在残量网络中，BFSBFS 判断从源点到汇点是否存在增广路，同时维护点的深度，搜索树边 (x,y)(d[y]=d[x]+1)(x,y)(d[y]=d[x]+1) 构成了“分层图”。

过程
DinicDinic 算法不断重复以下步骤，直到残量网络找不到增广路（S不能到T）：
a.在残量网络上，通过 BFSBFS 建分层图，如果 SS 不能到 TT,跳出循环。
b.在层次图上 DFSDFS,沿着层数增 11 且 cap>flowcap>flow 的方向找增广路，回溯时增流。出边有多条，此处多路增广，各点满足总流入大于等于总流出。若点 xx 无法流出，即流量为 00，点 x 在后续 DFS 中就不可能再次被访问，可以剪枝去掉，这就是弧优化。

Dinic 算法有两个优化：

  • 多路增广：每次找到一条增广路的时候，如果残余流量没有用完怎么办呢？我们可以利用残余部分流量，再找出一条增广路。这样就可以在一次 DFS 中找出多条增广路，大大提高了算法的效率。
  • 当前弧优化：如果一条边已经被增广过，那么它就没有可能被增广第二次。那么，我们下一次进行增广的时候，就可以不必再走那些已经被增广过的边。

DinicDinic 算法时间复杂度为 O(N2M)O(N^2M) ,实际使用中达不到这个上界，是网络流中的高效算法之一，一般可以处理 104−10510^4-10^5 规模的网络。

特别地，DinicDinic 在解决二分图最大匹配的时间复杂度为 O(mn)O(m\sqrt{n}) ,实际使用效率更高。

核心代码：

bool bfs()
{
	memset(d,0,sizeof(d));
	queue<int>que;
	que.push(s),d[s]=1;
	while(que.size())
	{
		int x=que.front();que.pop();
		for(int i=head[x];i;i=edge[i].next)
		{
			int y=edge[i].to,w=edge[i].flow;  //残量大于0 
			if(d[y]==0&&w>0)
			{
				que.push(y);
				d[y]=d[x]+1;
				if(y==t)return true;
			}
		}
	} 
	return false;
}
int dfs(int x,int flow)
{
	if(x==t)return flow;
	int rest=flow;
	for(int i=head[x];i&&rest;i=edge[i].next)  //多条出边，多路增广 
	{
		int y=edge[i].to,w=edge[i].flow;
		if(d[y]==d[x]+1&&w>0)
		{
			int k=dfs(y,min(rest,w));
			if(k==0)d[y]=0;    //剪枝 去掉增广过的点
			rest-=k;
			edge[i].flow-=k;       //残量减少 
			edge[i^1].flow+=k;     //反向边残量增加			 
		}
	}
	return flow-rest; 
} 
int dinic()
{
	int maxflow=0,flow;
	while(bfs())maxflow+=dfs(s,inf);
	return maxflow;
}

完整代码：点击

弧优化：

我们在按顺序 dfs 时，先被遍历到的边肯定是已经增广过了（或者已经确定无法继续增广了），那么这条边就可以视为“废边”

那么下次我们再到达该节点时，就可以直接无视掉所有废边，只走还有用的边，也就是说，每次 dfs 结束后，下次 dfs 可以更省时间。

只需要每次 dfsdfs 之前，复制一次 headhead 到 curcur 数组，在 dfsdfs 中使用 curcur 保留没有被增广到的出边。

DinicDinic 中：

int dinic()
{
	int maxflow=0,flow;
	while(bfs())
	{
	 	memcpy(cur,head,sizeof(head)); 
		maxflow+=dfs(s,inf);
	} 
	return maxflow;
}

DfsDfs中：

int dfs(int x,int flow)
{
	if(x==t)return flow;
	int rest=flow;
	for(int i=cur[x];i&&rest;i=edge[i].next)  //多条出边，多路增广 
	{
		cur[x]=i;              //当前弧优化，增广过的边不会第二次增广 去掉增广过的边 
		int y=edge[i].to,w=edge[i].flow;
		if(d[y]==d[x]+1&&w>0)
		{
			int k=dfs(y,min(rest,w));
			if(k==0)d[y]=0;    //剪枝 去掉增广过的点 
			rest-=k;
			edge[i].flow-=k;       //残量减少 
			edge[i^1].flow+=k;     //反向边残量增加	正边和反边是成对存储的		 
		}
	}
	return flow-rest; 
}

带优化完整代码：点击

ISAP

Dinic每次寻找增广路，都要BFS重新分层，能否进一步优化？

ISAP算法与Dinic相似，先分层，然后在分层图上DFS寻找增广路，DFS的同时修改节点深度。

算法过程：

  • 1.从 T 开始 BFS 计算各点深度
  • 2.类似于 dinic，从 S 开始 DFS，按照深度增加 -1 寻找增广路，进行增流。某点将之前流入的量全部跑完，意味着后续还有出边，之前的入边断开了，此时直接返回此点的所有流，否则，此点出边必有断开的，将此点深度++，对于数量--，如果出现断层，修改 S 点 d[s]=n+1。
  • 3.循环进行步骤2，直到 d[s]>n。
void bfs()
{
	memset(d,0,sizeof(d));
	queue<int>que;
	que.push(t),d[t]=1;
	num[d[t]]++; 
	while(que.size())
	{
		int x=que.front();que.pop();
		for(int i=head[x];i;i=edge[i].next)
		{
			int y=edge[i].to,w=edge[i].flow;
			if(d[y]==0)
			{
				d[y]=d[x]+1;
				num[d[y]]++;
				que.push(y);
			}
		}
	}	
}
int dfs(int x,int flow)
{
	if(x==t)return flow;
	int rest=flow;
	for(int i=cur[x];i&&rest;i=edge[i].next)
	{
		cur[x]=i;   //当前弧优化 
		int y=edge[i].to,w=edge[i].flow;
		if(d[x]==d[y]+1&&w>0)
		{
			int k=dfs(y,min(rest,w));
			
			rest-=k;
			edge[i].flow-=k;
			edge[i^1].flow+=k;
		}
		if(rest==0)return flow;
	}
	//否则 当前点x之后还有剩余，出边的边残量为0
	num[d[x]]--;
	if(num[d[x]]==0)d[s]=n+1;   //出现断层 GAP优化 
	d[x]++;
	num[d[x]]++;
	return flow-rest;	
}
int isap()
{
	int maxflow=0;
	bfs();
	while(d[s]<=n)
	{
		memcpy(cur,head,sizeof(head));
		
		maxflow+=dfs(s,inf);	
	}
	return maxflow;
}

参考代码：点击

费用流

给定一个网络 G=(V,E)G=(V,E) ,每条边 (x,y)(x,y) 除了有容量限制 c(x,y)c(x,y),还有一个给定的“单位费用” w(x,y)w(x,y)。

当 (x,y)(x,y) 的流量为 f(x,y)f(x,y),需要花费 f(x,y)×w(x,y)f(x,y)\times w(x,y).

单位费用也满足写对称性，即 w(x,y)=−w(x,y)w(x,y)=-w(x,y)。

该网络总花费最小的最大流称为“最小费用最大流”，总花费最大的最大流被称为“最大费用最大流”，合称“费用流”模型。

注意：费用流的前提是最大流，然后才考虑费用的最值。

求最大流的所有增广路算法（EK,Dinic，ISAP），都是把“用BFS 寻找最短增广路”改为“用 SPFA 寻找一条单位费用之和最小的增广路”就可以求出最小费用最大流。（将 w(x,y)w(x,y) 当做边权，在残量网络上求最短路，反边的费用应该设为 −w(x,y)-w(x,y) ）

核心代码：

int dfs(int x,int flow)
{
	if(x==t)return flow;
	vis[x]=1; 
	int rest=flow;
	for(int i=cur[x];i&&rest;i=edge[i].next)
	{
		cur[x]=i;
		int y=edge[i].to;
		if(vis[y]==0&&edge[i].flow>0&&dist[y]==dist[x]+edge[i].cost)
		{
			int k=dfs(y,min(rest,edge[i].flow));
			rest-=k;
			edge[i].flow-=k;
			edge[i^1].flow+=k;
			mincost+=edge[i].cost*k;
		}
	}
	vis[x]=0;
	return flow-rest;
}
void dinic()
{
	while(spfa())
	{
		int flow;
		memcpy(cur,head,sizeof(head));
		maxflow+=dfs(s,inf);
	}
}

完整代码：点击

学习完毕

{{ select(1) }}

  • YES
  • NO
  1. 关于
  2. 联系我们
  3. Language
  4. 兼容模式
  5. 主题
  3. Worker 0 in 190ms
  4. Powered by Hydro v5.0.0-beta.15 Modified by byx QQ465039728
  5. 陕ICP备2023000766号