网络流 EK (Edmond-Karp) 算法详解 求解最大流和费用流问题

前言

问题

有 $n$ 个城市,$m$ 条单向铁路连接了这些城市。每条铁路可以售 $s_i$ 张票。现在人们要从 $S$ 城去 $T$ 城,假设他们都有足够的钱去购买车票,那么最多有多少人能到达 $T$ 城?

思路

要使 $S$ 的人到达 $T$ ,首先要找到一条从 $S$ 到 $T$ 的通路(否则就到不了 $T$ 了)。显然,这条路最多只能通过其中供票最少的路的人数。在下面我们称这个最少的人数为 $k$ 。

然后这条路上的每条铁路都要减去 $k$ ,因为这条路中的每条铁路都通过了 $k$ 人,所以要全部减去 $k$ ,最终答案加上 $k$ 。

很明显,还有别的路可以通过,我们不断地找通路,并做以上的操作就应该可以找到最大流了。

但上述思路存在一个缺陷,如果找到的通路不是最优的,有其他的通路组合比其更优,那么答案就错误了。

在后文中,我们将会使用建反边的技巧解决这个问题。

定义

权值:一条边上最多的承载量(可以卖的票的数量)

增广路:从 $S$ 到 $T$ 的一条路,通过这条路可以使到达 $T$ 的总人数(流量)增加。

约定

本文使用的邻接表

long long last[200005],to[200005],nextt[200005],s[200005],top=0;
void add(int a,int b,int c){
    nextt[++top]=last[a];
    to[top]=b;
    s[top]=c;
    last[a]=top;
}

EK 算法的实现

我们在图中不断找出增广路,然后将这条增广路上的每条边减去这条增广路上最小的权值,直到找不到增广路为止。

寻找增广路

我们可以通过 $BFS$ 来实现这一操作。在 $BFS$ 时记录一下当前增广路的路径,

long long v[200005];//点是否在队列中
struct path{//记录路径
	long long from,edge;//这个点的上一个点,这个点连着的上一条边(靠近源点的)
};
path p[200005];
bool bfs(long long S,long long T){//源点,汇点
	memset(v,0,sizeof(v));
	memset(p,-1,sizeof(p));
	queue<long long> q;
	q.push(S);//将源点插入队列
	v[S]=1;
	while (!q.empty()){
		long long now=q.front();//队首
		q.pop();
		for (int i=last[now];i;i=nextt[i]){
			int j=to[i];//枚举队首连至的每一条边
			if (v[j]||s[i]<=0){//如果下一个点已经在队列中 或 这条边权小于等于 0
				continue;//那么跳过这条边
			}
			p[j].from=now;//记录路径
			p[j].edge=i;
			if (j==T){//如果到达 T ,那么返回 True
				return 1;
			}
			q.push(j);//入队
			v[j]=1;
		}
	}
	return 0;//如果 BFS 完成后仍未到达 T ,返回 False
}

EK 核心部分(不是最终的)

然后便是 EK 的核心了。不断找增广路,将路上权值减去,直到找不到增广路为止。

long long EK(long long S,long long T){
	long long ans=0;//最大流的最终答案
	while (bfs(S,T)){//如果存在增广路
		long long minn=2147483647;
		for (int i=T;i!=S;i=p[i].from){//遍历增广路路径
			minn=min(minn,s[p[i].edge]);//找出增广路上最小权值 k
		}
		ans+=minn;//累加答案
		for (int i=T;i!=S;i=p[i].from){//增广路上每条边权值减去 k
			s[p[i].edge]-=minn;
		}
	}
	return ans;
}

建反边

为什么要建反边

就这么结束了?EK 就这么简单?当然了,前文说过,但上述作法存在一个缺陷,如果找到的增广路组合不是最优的,有其他的增广路组合比其更优,那么答案就错误了。

所以我们建反边来巧妙解决这个问题。

如何建反边

对于每条正向边,建立一条与它相反的反向边,但边权为 $0$

我们在给正向边减少权值的同时,给反向边增加相同的权值。

反向边起到了一个标记的作用,使后来更优的解可以替换之前的不是最优的解。

(其实我也没完全理解反向边,以后再更吧,想了解可以看这篇博客

何时建反向边

在建正向边的同时建反向边。

add(a,b,c);
add(b,a,0);

注意

邻接表的 $top$ 要从 $1$ 开始,方便 EK 中对反向边的操作。

最终的 EK 核心部分

因为正向边和反向边的编号只相差 $1$ ,所以我们对于一条边 $x$ ,它的反向边是 $x\hat{}1$ 。(将邻接表初始时 top 设为 1 来保证此操作正确)

在给正向边减去权值的同时,给反向边加上权值,这也是唯一要改的一个地方(高亮处)。

邻接表定义的修改

long long top=1;//top 初始为 1

核心代码

long long EK(long long S,long long T){
	long long ans=0;//最大流的最终答案
	while (bfs(S,T)){//如果存在增广路
		long long minn=2147483647;
		for (int i=T;i!=S;i=p[i].from){//遍历增广路路径
			minn=min(minn,s[p[i].edge]);//找出增广路上最小权值 k
		}
		ans+=minn;//累加答案
		for (int i=T;i!=S;i=p[i].from){
			s[p[i].edge]-=minn;//增广路上每条正向边权值减去 k
			s[p[i].edge^1]+=minn;//增广路上每条反向边权值加上 k (唯一一行增加的代码)
		}
	}
	return ans;
}

最终代码

洛谷 P3376【模板】网络最大流 为例

#include<bits/stdc++.h>
using namespace std;
long long n,m,last[200005],to[200005],nextt[200005],s[200005],top=1;
long long v[200005];
struct path{
	long long from,edge;
};
path p[200005];
void add(int a,int b,int c){
    nextt[++top]=last[a];
    to[top]=b;
    s[top]=c;
	last[a]=top;
}
bool bfs(long long S,long long T){
	memset(v,0,sizeof(v));
	memset(p,-1,sizeof(p));
	queue<long long> q;
	q.push(S);
	v[S]=1;
	while (!q.empty()){
		long long now=q.front();
		q.pop();
		for (int i=last[now];i;i=nextt[i]){
			int j=to[i];
			if (v[j]||s[i]<=0){
				continue;
			}
			p[j].from=now;
			p[j].edge=i;
			if (j==T){
				return 1;
			}
			q.push(j);
			v[j]=1;
		}
	}
	return 0;
}
long long EK(long long S,long long T){
	long long ans=0;
	while (bfs(S,T)){
		long long minn=2147483647;
		for (int i=T;i!=S;i=p[i].from){
			minn=min(minn,s[p[i].edge]);
		}
		ans+=minn;
		for (int i=T;i!=S;i=p[i].from){
			s[p[i].edge]-=minn;
			s[p[i].edge^1]+=minn;
		}
	}
	return ans;
}
int main(){
	long long S,T;
	cin>>n>>m>>S>>T;
	for (int i=1;i<=m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		add(a,b,c);
		add(b,a,0);
	}
	cout<<EK(S,T);
}

EK 算法的扩展

最小费用最大流 (费用流)

洛谷 P3381 【模板】最小费用最大流

将 $BFS$ 换成 $SPFA$ 即可。

代码不同的地方已经高亮标记。

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
long long n,m,last[200005],to[200005],nextt[200005],s[200005],t[200005],top=1,ans=0,cost=0;//t 为路的费用,ans 为最大流,cost 为最小费用 
long long d[200005];
long long v[200005];
struct path{
	long long from,edge;
};
path p[200005];
void add(int a,int b,int c,int d){
    nextt[++top]=last[a];
    to[top]=b;
    s[top]=c;
    t[top]=d;
	last[a]=top;
}
bool spfa(long long S,long long T){
	queue<long long> q;
	memset(v,0,sizeof(v));
	memset(d,63,sizeof(d));
	memset(p,-1,sizeof(p));
	q.push(S);
	v[S]=1;
	d[S]=0;
	d[T]=2147483647;
	while (!q.empty()){
		long long now=q.front();
		q.pop();
		for (int i=last[now];i;i=nextt[i]){
			long long j=to[i];
			if (s[i]<=0){
				continue;
			}
			if (d[now]+t[i]<d[j]){
				d[j]=d[now]+t[i];
				p[j].from=now;
				p[j].edge=i;
				if (!v[j]){
					q.push(j);
					v[j]=1;
				}
			}
		}
		v[now]=0;
	}
	if (d[T]<2147483647){
		return 1;
	}else{
		return 0;
	}
}
void EK(long long S,long long T){
	while (spfa(S,T)){
		long long minn=2147483647;
		for (int i=T;i!=S;i=p[i].from){
			minn=min(minn,s[p[i].edge]);
		}
		ans+=minn;
		for (int i=T;i!=S;i=p[i].from){
			s[p[i].edge]-=minn;
			s[p[i].edge^1]+=minn;
		}
		cost+=minn*d[T];
	}
}
int main(){
	long long S,T;
	cin>>n>>m>>S>>T;
	for (int i=1;i<=m;i++){
		int a,b,c,d;
		a=read();b=read();c=read();d=read();
		add(a,b,c,d);
		add(b,a,0,-d);
	}
	EK(S,T);
	cout<<ans<<" "<<cost;
}

 

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: Telegram @AmashiroNatsukiEars_NoWord Sticker
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
AmashiroNatsukiEars
小恐龙
花!
上一篇
下一篇