前言

问题

有 $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;
}