定义

网络是有向图的一种，不同于其他有向图，一个网络有两个特殊的点源点（一般记作 $s$）和汇点（一般记作 $t$），顾名思义，源点只有出边而汇点只有入边。同时，每条边有边权 $c$，表示容量，同时还映射一个值 $flow$，叫做流量。一种容易的理解方式是将边想象成不同大小的管道。值得注意的是，流量可以为负，这一般表示反向流动以及在一些算法中对先前流量分配的“撤销”。
残量网络：将容量已满的边删去，剩下的边构成的图就是残量网络。
增广路：从源点到汇点的一条路径，其中每条边都有剩余容量。

最大流问题

对于一个网络，找到最大的流量。

最小割问题

我们将网络上的一些边进行分割，使之分为两部分，一部分包含 $s$，另一部分包含 $t$，所有切割的边的容量和叫做网络的最小割。
例：现有网络

image

其最小割为

image

即 $3=2+1$。

最大流最小割定理

对于一个网络，最大流总等于最小割。这个定理看似显然，实则并不好证。证明。

接下来以最大流模板题为例讲解一些算法。

Edmonds-Karp 算法

流程：

  • 从 $s$ 出发进行 BFS 尝试走到 $t$，即寻找增广路。
  • 找到增广路后计算增广路上剩余容量的最小值 $f$，给增广路上每条边加上 $f$ 容量，并将它们的反向边退掉 $f$ 容量。
  • 在新图上重复以上操作直到增广路不存在。

时间复杂度 $O(nm^2)$。
关于反向边，有个小技巧，就是直接将正反两边的编号设为 $2n$ 和 $2n+1$，这样可以通过异或 $1$ 的操作快速完成正反边的转换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<cstdio>
#include<queue>
#include<cstring>
#define inf 1e18
using namespace std;
const int N=210,M=5010;
int head[N],tot=1;//因为要异或1所以初始化为1
int n,m,s,t;
int pre[N];//路径的前驱节点
long long flow[N];//各边剩余容量最小值
struct edge{
	int to,nxt;
	long long c;//剩余容量
}e[M*2];
int flag[N][N];
long long ans;
void add_edge(int u,int v,long long c){
	e[++tot].to=v;
	e[tot].c=c;
	e[tot].nxt=head[u];
	head[u]=tot;//正向边
	e[++tot].to=u;
	e[tot].c=0;
	e[tot].nxt=head[v];
	head[v]=tot;//反向边
	return;
}
bool bfs(){
	memset(pre,0,sizeof(pre));
	queue<int> q;
	q.push(s);
	pre[s]=s;
	flow[s]=inf;
	while(q.size()){
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].to;
			if(e[i].c==0||pre[v])
				continue;
			flow[v]=min(flow[u],e[i].c);
			pre[v]=i;
			q.push(v);
			if(v==t)
				return 1;
		}
	}
	return 0;
}
int main(){
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for(int i=1;i<=m;i++){
		int u,v;
		long long w;
		scanf("%d%d%lld",&u,&v,&w);
		if(!flag[u][v]){//去重边
			add_edge(u,v,w);
			flag[u][v]=tot;
		}
		else
			e[flag[u][v]^1].c+=w;
	}
	while(bfs()){
		for(int u=t;u!=s;u=e[pre[u]^1].to){
			e[pre[u]].c-=flow[t];
			e[pre[u]^1].c+=flow[t];
		}
		ans+=flow[t];
	}
	printf("%lld",ans);
	return 0;
}

Dinic 算法

个人认为这个更难理解一些。
流程：

  • 在残量网络中进行 BFS 构建分层图。
  • 使用 DFS，每次找到 $t$ 后直接回溯更新边权。

使用分层图的原因是因为分层图是 DAG，进行 DFS 时不会走回头路或环路，保证了算法的正确性和高效性。
时间复杂度 $O(n^2m)$，优于 Edmonds-Karp 算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<cstdio>
#include<queue>
#include<cstring>
#define inf 1e18
using namespace std;
const int N=210,M=5010;
int n,m,s,t,tot=1,head[N];
long long ans;
struct edge{
	int to,nxt;
	long long c;
}e[M*2];
void add_edge(int u,int v,long long c){
	e[++tot].to=v;
	e[tot].c=c;
	e[tot].nxt=head[u];
	head[u]=tot;
	e[++tot].to=u;
	e[tot].c=0;
	e[tot].nxt=head[v];
	head[v]=tot;
	return;
}
int level[N];//层级
bool bfs(){
	memset(level,-1,sizeof(level));
	queue<int> q;
	q.push(s);
	level[s]=0;
	while(q.size()){
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].to;
			if(e[i].c==0||level[v]!=-1)
				continue;
			level[v]=level[u]+1;
			q.push(v);
		}
	}
	return level[t]!=-1;
}
long long dfs(int u,long long flow){
	if(u==t)
		return flow;
	long long res=0;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(e[i].c==0||level[v]!=level[u]+1)//按层dfs
			continue;
		long long temp=dfs(v,min(flow-res,e[i].c));
		e[i].c-=temp;
		e[i^1].c+=temp;
		res+=temp;
		if(res==flow)
			break;
	}
	if(res==0)
		level[u]=-1;
	return res;
}
int main(){
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for(int i=1;i<=m;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add_edge(u,v,w);
	}
	while(bfs())
		ans+=dfs(s,inf);
	printf("%lld",ans);
	return 0;
}

优化：当前弧优化。减少 DFS 对边的重复检查。若某边剩余容量已为 $0$，则不再处理这条边。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//...
int cur[N];//当前弧优化
long long dfs(int u,long long flow){
	if(u==t)
		return flow;
	long long res=0;
	for(int i=cur[u];i;i=e[i].nxt){
		cur[u]=i;//当前弧优化
		int v=e[i].to;
		if(e[i].c==0||level[v]!=level[u]+1)//按层dfs
			continue;
		long long temp=dfs(v,min(flow-res,e[i].c));
		e[i].c-=temp;
		e[i^1].c+=temp;
		res+=temp;
		if(res==flow)
			break;
	}
	if(res==0)
		level[u]=-1;
	return res;
}
//...
while(bfs()){
	memcpy(cur,head,sizeof(head));//重置当前弧
	ans+=dfs(s,inf);
}
//...

最小费用最大流

费用流定义：对于一个网络的每条边，我们再加一个边权称为一个单位流量的费用，记作 $w(u,v)$，则这条边的费用为 $f(u,v)\times w(u,v)$。与上文中提到的反向边回退流量相同，费用也可以这样操作。
与普通最大流问题不同，最小费用最大流的求解过程不用 BFS 而用最短路算法寻找增广路，这样就保证了最小费用。
这里给出 Edmonds-Karp + SPFA 的做法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=5e3+10,M=5e4+10;
struct edge{
	int to,nxt,c,w;
}e[M*2];
int tot=1,head[N],n,m,s,t;
void add_edge(int u,int v,int c,int w){
	e[++tot].to=v;
	e[tot].nxt=head[u];
	e[tot].c=c;
	e[tot].w=w;
	head[u]=tot;
	e[++tot].to=u;
	e[tot].nxt=head[v];
	e[tot].c=0;
	e[tot].w=-w;
	head[v]=tot;
	return;
}
int min_flow[N],dis[N],pre[N],flow,cost;
queue<int> q;
bool vis[N];
bool spfa(){
	memset(dis,0x3f,sizeof(dis));
	memset(min_flow,0,sizeof(min_flow));
	memset(vis,0,sizeof(vis));
	q.push(s);
	vis[s]=1;
	dis[s]=0;
	min_flow[s]=2e9;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].to,c=e[i].c,w=e[i].w;
			if(c&&dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				pre[v]=i;
				min_flow[v]=min(min_flow[u],c);
				if(!vis[v]){
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
	return min_flow[t]>0;
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;i++){
		int u,v,c,w;
		cin>>u>>v>>c>>w;
		add_edge(u,v,c,w);
	}
	while(spfa()){
		int minf=min_flow[t];
		for(int i=t;i!=s;i=e[pre[i]^1].to){
			e[pre[i]].c-=minf;
			e[pre[i]^1].c+=minf;
		}
		flow+=minf;
		cost+=minf*dis[t];
	}
	cout<<flow<<' '<<cost;
	return 0;
}

网络流建模

例题

考虑拆点。将点 $(x,y)$ 拆为 $(x,y)_1$ 和 $(x,y)_2$。
对于 $0$（平坦无障碍），建 $(x,y)_1\to(x,y)_2$，容量 $inf$，费用 $0$，表示可以无限通过但无收益。同时，建 $(x,y)_2\to(x+1,y)_1$ 和 $(x,y)_2\to(x,y+1)_1$，容量与费用同上，表示向南和向东走。
对于 $1$（障碍），不建立节点。
对于 $2$（石块），先建 $0$（平坦无障碍）的 $3$ 条边，然后再建一条 $(x,y)_1\to(x,y)_2$，容量 $1$，费用 $1$，表示只能走 $1$ 次且贡献为 $1$。
然后跑最大费用最大流就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<iostream>
#include<queue>
#include<cstring>
#define inf 2e9
using namespace std;
const int N=35*35*2+10,M=1e5+10;
int p,q,nodecnt,node[N][N],tot=1,head[N],n;
struct edge{
	int to,nxt,c,w;
}e[M];
void add_edge1(int u,int v,int c,int w){
	e[++tot].to=v;
	e[tot].nxt=head[u];
	e[tot].c=c;
	e[tot].w=w;
	head[u]=tot;
	return;
}
void add_edge(int u,int v,int c,int w){
	add_edge1(u,v,c,w);
	add_edge1(v,u,0,-w);
	return;
}
int pre[N],dis[N],s,t,flow[N];
bool vis[N];
queue<int> que;
bool spfa(){
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	memset(flow,0,sizeof(flow));
	dis[s]=0;
	vis[s]=1;
	flow[s]=inf;
	que.push(s);
	while(!que.empty()){
		int u=que.front();
		que.pop();
		vis[u]=0;
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].to,c=e[i].c,w=e[i].w;
			if(c&&dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				pre[v]=i;
				flow[v]=min(flow[u],c);
				if(!vis[v]){
					vis[v]=1;
					que.push(v);
				}
			}
		}
	}
	return flow[t]>0;
}
int cnt[N][N];
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>p>>q;
	for(int i=1;i<=q;i++)
		for(int j=1;j<=p;j++)
			node[i][j]=++nodecnt;
	for(int i=1,c;i<=q;i++){
		for(int j=1;j<=p;j++){
			cin>>c;
			if(c==1)
				continue;
			add_edge(node[i][j],node[i][j]+nodecnt,inf,0);
			if(c==2)
				add_edge(node[i][j],node[i][j]+nodecnt,1,-1);
			if(i<q)
				add_edge(node[i][j]+nodecnt,node[i+1][j],inf,0);
			if(j<p)
				add_edge(node[i][j]+nodecnt,node[i][j+1],inf,0);
		}
	}
	s=0,t=nodecnt*2+1;
	add_edge(s,node[1][1],n,0);
	add_edge(node[q][p]+nodecnt,t,n,0);
	while(spfa()){
		int minf=flow[t];
		for(int i=t,cnt=0;i!=s;i=e[pre[i]^1].to,cnt++){
			e[pre[i]].c-=minf;
			e[pre[i]^1].c+=minf;
		}
	}
	for(int i=1;i<=q;i++)
		for(int j=1;j<=p;j++)
			for(int k=head[node[i][j]];k;k=e[k].nxt){
				int v=e[k].to;
				if(v==node[i][j]+nodecnt)
					cnt[i][j]+=e[k^1].c;
			}
	for(int i=1;i<=n;i++){
		int x=1,y=1;
		while(x!=q||y!=p){
			if(cnt[x+1][y]){
				cout<<i<<" 0\n";
				cnt[x+1][y]--;
				x++;
			}
			else{
				cout<<i<<" 1\n";
				cnt[x][y+1]--;
				y++;
			}
		}
	}
	return 0;
}

其他

参考资料：

OI Wiki

题解 P3376 【【模板】网络最大流】

【题解】P3356 火星探险问题