网络流算法讲解

网络流描述：给定一幅图（n个结点，m条边），每一条边有一个容量，现在需要将一些物品从结点s（称为源点）运送到结点t（称为汇点），可以从其他结点中转。
满足以下三个性质的网络流叫做可行流：
（1）容量约束：任意一条边的流量不超过最大容量。
（2）反对称性：节点u到v的流量和节点v到u的流量互为负数。
（3）流量守恒：除了源点s和汇点t，所有节点的流入量等于流出量。
网络最大流指在满足可行流的条件下，边的实际流量最大的网络流。求最大流的基本思想为：在网络中找增广路（边的实际流量可以继续增加），沿着增广路增加流量，直到不存在增广路为止。
上下界网络流问题是指每条边的流量有一个上界和下界。

关键代码讲解

（1）使用链式前向星存图。
（2）存储的网络为混合网络，将残余网络和实流网络融为一体。混合网络的特殊之处为它的正向边有两个变量 cap（边的容量），flow（实际流量）。在增流时cap不变，flow+=d；反向边的cap = 0，flow = -flow，增流时cap不变，flow -= d。在正向边中cap-flow代表残余容量，反向边cap-flow代表实际流量。
（3）建议着重理解Dinic求最大流和无源汇上下界可行流。

最大流

EK

题目：AcWing 2171， HDU 3549， HDU 1532

算法详解：EK算法是以广度优先搜索为基础的最短路增广算法。采用队列q存放已访问 未检查的节点，数组vis[]标记节点是否被访问，pre[]数组记录增广路上节点的前驱。

算法步骤：
（1）初始化可行流flow为0，vis[]数组为false，pre[]数组为-1，最大流值maxflow=0。
（2）令vis[s]=true，将s加入队列q。
（3）若队列为空，则算法结束，当前实流网络就是最大流网络，返回最大流的值。
（4）队头元素 u出队，在残余网络中检查u的所有邻接节点 i，若未被访问，则访问它， 令 vis[i]=true,pre[i]=u，若 i==t，则说明已到达汇点，找到一条增广路，转向第5步，否则 i进入队列 q，转向第3步。
（5）从汇点开始，用前驱数组 pre[]，在残余网络中逆向找增广路上每条边的最小值d。
（6）在实流网络中增流，在残余网络中减流。maxflow+=d，转向第2步。

代码：时间复杂度O(n$m^{2}$)

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
#include<bits/stdc++.h>
using namespace std;

const int N = 1000 + 10;
const int M = 10000 + 10;
const int inf = 0x3f3f3f3f;

int n, m, s, t, tot = 1;
int vis[N], pre[N], head[M<<1];

struct Edge
{
	int to, next, cap, flow;
}e[M<<1];

void add(int a, int b, int c)
{
	e[++tot].cap = c; e[tot].flow = 0; e[tot].to = b; e[tot].next = head[a]; head[a] = tot;
	e[++tot].cap = 0; e[tot].flow = 0; e[tot].to = a; e[tot].next = head[b]; head[b] = tot; 
}

bool bfs(int s, int t)
{
	memset(pre, -1, sizeof pre);
	memset(vis, 0, sizeof vis);
	queue<int> q;
	vis[s] = 1; 
	q.push(s);
	while(!q.empty())
	{
		int u = q.front();
		q.pop();
		for(int i = head[u]; ~i; i = e[i].next)
		{
			int v = e[i].to;
			if(!vis[v] && e[i].cap > e[i].flow)
			{
				vis[v] = 1;
				pre[v] = i;
				q.push(v);
				if(v == t) return 1;
			}
		}
	}
	return 0;
}

int EK(int s, int t)
{
	int maxflow = 0;
	while(bfs(s, t))
	{
		int d = inf;
		int v = t;
		while(v != s)
		{
			int i = pre[v];
			d = min(d, e[i].cap - e[i].flow);
			v = e[i^1].to;
		}
		maxflow += d;
		v = t;
		while(v != s)
		{
			int i = pre[v];
			e[i].flow += d;
			e[i^1].flow -= d;
			v = e[i^1].to;
		}
	}
	return maxflow;
}

int main()
{
	memset(head, -1, sizeof head);
	cin>>n>>m>>s>>t;
	while(m--)
	{
		int a, b, c; cin>>a>>b>>c;
		add(a, b, c);
	}
	cout<<EK(s, t);
	return 0;
}

Dinic

题目：AcWing 2172，POJ 1149， POJ 1459

算法详解：Dinic算法每次通过广度优先搜索（BFS）分层，然后通过深度优先搜索（DFS）沿着层次增 1且 cap>flow的方向找增广路，回溯时增流。一次DFS中可以实现多次增流，这正是Dinic算法的巧妙之处。使用了弧优化提高效率。

算法步骤：
（1）在残余网络中通过广度优先搜索进行分层。
（2）在层次图中深度优先搜索，沿着层次增 1且 cap>flow的方向找增广路，回溯时增流
（3）重复以上步骤，直到找不到增广路为止，得到最大流。

时间复杂度：O($n^{2}$m)

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
#include<bits/stdc++.h>
using namespace std;

const int N = 10 + 1e4;
const int M = 10 + 1e5 + N;
const int inf = 0x3f3f3f3f;

int n, m, s, t, tot = 1;
int head[M<<1], cur[M<<1], d[N];

struct node
{
	int to, next, cap, flow;
}e[M<<1];

void add(int a, int b, int c)
{
	e[++tot].cap = c; e[tot].flow = 0; e[tot].to = b; e[tot].next = head[a]; head[a] = tot;
	e[++tot].cap = 0; e[tot].flow = 0; e[tot].to = a; e[tot].next = head[b]; head[b] = tot;
}

bool bfs()
{
	memset(d, 0, sizeof d);
	d[s] = 1;
	cur[s] = head[s];
	queue<int> q;
	q.push(s);
	while(q.size())
	{
		int u = q.front(); q.pop();
		for(int i = head[u]; ~i; i = e[i].next)
		{
			int v = e[i].to;
			if(!d[v] && e[i].cap > e[i].flow)
			{
				d[v] = d[u] + 1;
				cur[v] = head[v];
				q.push(v);
				if(v == t) return 1;
			}
		}
	}
	return 0;
}

int dfs(int u, int lim, int t)
{
	if(u == t) return lim;
	int res = lim;
	for(int i = cur[u]; ~i && res; i = e[i].next)
	{
		cur[u] = i;
		int v = e[i].to;
		if(d[v] == d[u]+1 && e[i].cap > e[i].flow)
		{
			int k = dfs(v, min(res, e[i].cap-e[i].flow), t);
			if(!k) d[v] = 0;
			e[i].flow += k;
			e[i^1].flow -= k;
			res -= k; 
		}
	}
	return lim - res;
}

int dinic()
{
	int maxflow = 0;
	while(bfs()) maxflow += dfs(s, inf, t);
	return maxflow;
}

int main()
{
	memset(head, -1, sizeof head);
	cin>>n>>m>>s>>t;
	for(int i = 0; i < m; i++)
	{
		int a, b, c; cin>>a>>b>>c;
		add(a, b, c);
	}
	cout<<dinic();
	return 0;
}

ISAP

题目：AcWing 2172

算法详解：首先是贴标签：对所有节点都标记到汇点的最短距离，称之为高度（BFS实现）。然后从源点开始，沿着高度减1且有可行邻边的方向前进。找到汇点之后增流。当前节点无法前进时，重贴标签。

算法步骤：
（1）标高操作，从汇点开始对节点贴标签。
（2）找增广路，若源点的高度大于等于节点数，转向第5步；否则沿着高度h[u] = h[v]+1且cap>flow的方向前进。若到达汇点则转向第3步；若无法前进，转向第4步。
（3）增流操作，在混合网络中沿着增广路同向的边增流，反向边减流。
（4）重贴标签，当前节点无法前进时，若拥有当前节点高度的节点只有一个，则转向第5步，否则令当前节点的高度等于所有可行邻接点高度的最小值加1，若没有可行邻接边，则令当前节点的高度等于节点数，转向第2步。
（5）算法结束，已经找到最大流。

代码：时间复杂度：O($n^{2}$m)

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
#include<bits/stdc++.h>
using namespace std;

const int N = 10 + 1e4;
const int M = 10 + 1e5 + N;
const int inf = 0x3f3f3f3f;

int n, m, s, t, tot = 1;
int head[M<<1], d[N], h[N], g[N], pre[N];

struct node
{
	int to, next, cap, flow;
}e[M<<1];

void add(int a, int b, int c)
{
	e[++tot].cap = c; e[tot].flow = 0; e[tot].to = b; e[tot].next = head[a]; head[a] = tot;
	e[++tot].cap = 0; e[tot].flow = 0; e[tot].to = a; e[tot].next = head[b]; head[b] = tot;
}

void set_h(int t, int n)
{
	queue<int> q;
	memset(h, -1, sizeof h);
	memset(g, 0, sizeof g);
	h[t] = 0;
	q.push(t);
	while(q.size())
	{
		int u = q.front(); q.pop();
		++g[h[u]];
		for(int i = head[u]; ~i; i = e[i].next)
		{
			int v = e[i].to;
			if(h[v] == -1)
			{
				h[v] = h[u] + 1;
				q.push(v);
			}
		}
	}
}

int ISAP(int s, int t, int n)
{
	set_h(t, n);
	int ans = 0, u = s, d;
	while(h[s] < n)
	{
		int i = head[u];
		if(u == s) d = inf;
		for(; ~i; i = e[i].next)
		{
			int v = e[i].to;
			if(e[i].cap > e[i].flow && h[u] == h[v]+1)
			{
				u = v;
				pre[v] = i;
				d = min(d, e[i].cap-e[i].flow);
				if(u == t)
				{
					while(u != s)
					{
						int j = pre[u];
						e[j].flow += d;
						e[j^1].flow -= d;
						u = e[j^1].to;
					}
					ans += d;
					d = inf;
				}
				break;
			}
		}
		if(i == -1)
		{
			if(--g[h[u]] == 0) break;
			int hmin = n-1;
			for(int j = head[u]; ~j; j = e[j].next)
				if(e[j].cap > e[j].flow)
					hmin = min(hmin, h[e[j].to]);
			h[u] = hmin+1;
			++g[h[u]];
			if(u != s) u = e[pre[u]^1].to;
		}
	}
	return ans;
}

int main()
{
	memset(head, -1, sizeof head);
	cin>>n>>m>>s>>t;
	for(int i = 0; i < m; i++)
	{
		int a, b, c; cin>>a>>b>>c;
		add(a, b, c);
	}
	cout<<ISAP(s, t, n);
	return 0;
}

无源汇

无源汇上下界可行流

题目：AcWing: 2188

算法详解：可行流中每条边的流量一定大于等于下界，所以建一个每条边流量为流量下界的初始流，使用数组L存储，然后在混合网络中建正向边容量为上界减下界（d-c），反向边容量为0的网络。最终的可行流一定是在这个初始流的基础上增大了一些边的流量使得所有点满足流量守恒，将后面增加的称作附加流。
重点：如果某个点在初始流中的流入量比流出量多x,那么这个点在附加流中的流出量就应该比流入量多x。如果某个点在初始流中的流入量比流出量少x,那么这个点在附加流中的流出量就应该比流入量少x。所以使用数组delta存储每个节点在初始流中流入量减流出量的值。求这个附加流的做法是：给在附加流中所有流入量大于流出量的节点u与虚拟汇点t建一条流量为-delta[u]的边（给多的流入量找个去处也就是再流出到t），给在附加流中虚拟源点s与所有流出量大于流入量的节点v建一条流量为delta[v]的边（给多的流出量找个来处也就是从s流入）。
然后在从虚拟源点到虚拟汇点t使用Dinic跑一遍最大流算法，这时的去掉虚拟源点和虚拟汇点的网络流就是所需要的附加流。最后，每条边在可行流中的流量 = 容量下界 + 附加流中流量。

代码：

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
109
110
111
#include<bits/stdc++.h>
using namespace std;

const int N = 2000 + 10;
const int M = (100210 + N) + 10;
const int inf = 0x3f3f3f3f;

int n, m, s, t, tot = 1, tott;
int head[M<<1], d[N], L[M<<1], cur[N], delta[N];

struct Edge
{
	int to, next, cap, flow;
}e[M<<1];

void add(int a, int b, int c, int d)
{
	e[++tot].cap = d-c; e[tot].flow = 0; e[tot].to = b; e[tot].next = head[a]; head[a] = tot;
	L[tot] = c;
	e[++tot].cap = 0; e[tot].flow = 0; e[tot].to = a; e[tot].next = head[b]; head[b] = tot; 
}

bool bfs(int s, int t)
{
	memset(d, 0, sizeof d);
	queue<int> q;
	d[s] = 1;
	cur[s] = head[s];
	q.push(s);
	while(!q.empty())
	{
		int u = q.front();
		q.pop();
		for(int i = head[u]; ~i; i = e[i].next)
		{
			int v = e[i].to;
			if(!d[v] && e[i].cap > e[i].flow)
			{
				d[v] = d[u]+1;
				cur[v] = head[v];
				if(v == t) return 1;
				q.push(v);
			}
		}
	}
	return 0;
}

int dfs(int u, int flow, int t)
{
	if(u == t) return flow;
	int res = flow;
	for(int i = cur[u]; ~i && res; i = e[i].next)
	{
		cur[u] = i;
		int v = e[i].to;
		if(d[v] == d[u]+1 && e[i].cap > e[i].flow)
		{
			int k = dfs(v, min(res, e[i].cap-e[i].flow), t);
			if(!k) d[v] = 0;
			e[i].flow += k;
			e[i^1].flow -= k;
			res -= k;
		}	
	}
	return flow-res;
}

int dinic()
{
	int maxflow = 0, flow;
	while(bfs(s, t)) maxflow += dfs(s, inf, t);
	return maxflow;
}

int main()
{
	memset(head, -1, sizeof head);
	cin>>n>>m;
	s = 0;
	t = n+1;
	for(int i = 0; i < m; i++)
	{
		int a, b, c, d; cin>>a>>b>>c>>d;
		add(a, b, c, d);
		delta[a] -= c;
		delta[b] += c;
	}
	for(int i = 1; i <= n; i++)
	{
		if(delta[i] > 0)
		{
			add(s, i, 0, delta[i]);
			tott += delta[i];
		}
		else if(delta[i] < 0)
			add(i, t, 0, -delta[i]);
	}
	if(dinic() != tott)
	{
		cout<<"NO";
		return 0;
	}
	// 输出结果为可行流中每条边的流量
	cout<<"YES"<<endl;
	for(int i = 2; i < m*2+2; i += 2)
		cout<<e[i^1].cap-e[i^1].flow+L[i]<<endl;
	
	return 0;
}

有源汇

有源汇上下界可行流

算法详解：为了使源汇点满足流量守恒，所以从汇点tt向源点ss连一条下界为0上界为无穷大的边，相当于把从源点s流出的流量再流回来。在这样的图中使用无源汇上下界可行流算法求出一个可行流，拆掉从汇点tt到源点ss的边就得到一个有源汇上下界可行流。

代码：

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
109
110
#include<bits/stdc++.h>
using namespace std;

const int N = 2000 + 10;
const int M = (100210 + N) + 10;
const int inf = 0x3f3f3f3f;

int n, m, s, t, ss, tt, tot = 1, tott;
int head[M<<1], d[N], L[M<<1], cur[N], delta[N];

struct Edge
{
	int to, next, cap, flow;
}e[M<<1];

void add(int a, int b, int c, int d)
{
	e[++tot].cap = d-c; e[tot].flow = 0; e[tot].to = b; e[tot].next = head[a]; head[a] = tot;
	L[tot] = c;
	e[++tot].cap = 0; e[tot].flow = 0; e[tot].to = a; e[tot].next = head[b]; head[b] = tot; 
}

bool bfs(int s, int t)
{
	memset(d, 0, sizeof d);
	queue<int> q;
	d[s] = 1;
	cur[s] = head[s];
	q.push(s);
	while(!q.empty())
	{
		int u = q.front();
		q.pop();
		for(int i = head[u]; ~i; i = e[i].next)
		{
			int v = e[i].to;
			if(!d[v] && e[i].cap > e[i].flow)
			{
				d[v] = d[u]+1;
				cur[v] = head[v];
				if(v == t) return 1;
				q.push(v);
			}
		}
	}
	return 0;
}

int dfs(int u, int flow, int t)
{
	if(u == t) return flow;
	int res = flow;
	for(int i = cur[u]; ~i && res; i = e[i].next)
	{
		cur[u] = i;
		int v = e[i].to;
		if(d[v] == d[u]+1 && e[i].cap > e[i].flow)
		{
			int k = dfs(v, min(res, e[i].cap-e[i].flow), t);
			if(!k) d[v] = 0;
			e[i].flow += k;
			e[i^1].flow -= k;
			res -= k;
		}	
	}
	return flow-res;
}

int dinic()
{
	int maxflow = 0, flow;
	while(bfs(s, t)) maxflow += dfs(s, inf, t);
	return maxflow;
}

int main()
{
	memset(head, -1, sizeof head);
	cin>>n>>m>>ss>>tt;
	s = 0;
	t = n+1;
	for(int i = 0; i < m; i++)
	{
		int a, b, c, d; cin>>a>>b>>c>>d;
		add(a, b, c, d);
		delta[a] -= c;
		delta[b] += c;
	}
	for(int i = 1; i <= n; i++)
	{
		if(delta[i] > 0)
		{
			add(s, i, 0, delta[i]);
			tott += delta[i];
		}
		else if(delta[i] < 0)
			add(i, t, 0, -delta[i]);
	}
	add(tt, ss, 0, inf);
	if(dinic() != tott)
	{
		cout<<"NO";
		return 0;
	}
	cout<<"YES"<<endl;
	cout<<e[tot].cap-e[tot].flow<<endl;
	e[tot].flow = e[tot].cap;
	return 0;
}

有源汇上下界最大流

题目：AcWing 2189

算法详解：先使用有源汇上下界可行流算法算出一个可行流，再在这个残余网络上跑一遍ss到tt的最大流。最终的最大流流量 = 可行流流量(即t到s的无穷边上跑出的流量) + 新增广出的ss到tt的流量。

代码：

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
109
110
111
112
113
114
#include<bits/stdc++.h>
using namespace std;

const int N = 2000 + 10;
const int M = (100210 + N) + 10;
const int inf = 0x3f3f3f3f;

int n, m, s, t, ss, tt, tot = 1 , tott;
int head[M<<1], d[N], cur[M<<1], delta[N];

struct Edge
{
	int to, next, cap, flow;
}e[M<<1];

void add(int a, int b, int c, int d)
{
	e[++tot].cap = d-c; e[tot].flow = 0; e[tot].to = b; e[tot].next = head[a]; head[a] = tot;
	e[++tot].cap = 0; e[tot].flow = 0; e[tot].to = a; e[tot].next = head[b]; head[b] = tot; 
}

bool bfs(int s, int t)
{
	memset(d, 0, sizeof d);
	d[s] = 1;
	cur[s] = head[s];
	queue<int> q;
	q.push(s);
	while(!q.empty())
	{
		int u = q.front();
		q.pop();
		for(int i = head[u]; ~i; i = e[i].next)
		{
			int v = e[i].to;
			if(!d[v] && e[i].cap > e[i].flow)
			{
				d[v] = d[u]+1;
				cur[v] = head[v];
				if(v == t) return 1;
				q.push(v);
			}
		}
	}
	return 0;
}

int dfs(int u, int lim, int t)
{
	if(u == t) return lim;
	int res = lim;
	for(int i = cur[u]; ~i && res; i = e[i].next)
	{
		cur[u] = i;
		int v = e[i].to;
		if(d[v] == d[u]+1 && e[i].cap > e[i].flow)
		{
			int k = dfs(v, min(res, e[i].cap-e[i].flow), t);
			if(!k) d[v] = 0;
			e[i].flow += k;
			e[i^1].flow -= k; 
			res -= k;
		}	
	}
	return lim-res;
}

int dinic()
{
	int maxflow = 0;
	while(bfs(s, t)) maxflow += dfs(s, inf, t);
	return maxflow;
}

int main()
{
	memset(head, -1, sizeof head);
	cin>>n>>m>>ss>>tt;
	s = 0;
	t = n+1;
	for(int i = 0; i < m; i++)
	{
		int a, b, c, d; cin>>a>>b>>c>>d;
		add(a, b, c, d);
		delta[a] -= c;
		delta[b] += c;
	}
	for(int i = 1; i <= n; i++)
	{
		if(delta[i] > 0)
		{
			add(s, i, 0, delta[i]);
			tott += delta[i];
		}
		if(delta[i] < 0)
			add(i, t, 0, -delta[i]);
	}
	add(tt, ss, 0, inf);
	if(dinic() != tott)
	{
		cout<<"No Solution";
		return 0;
	}
	s = ss; t = tt;
	// 先加可行流流量
	int ans = e[tot].cap-e[tot].flow;
	e[tot].flow = 0; e[tot].cap = 0;
	e[tot-1].flow = 0; e[tot-1].cap = 0;
	// 再加新增广为最大流的e(s->t)的流量
	ans += dinic();
	cout<<ans<<endl;
	return 0;
}

有源汇上下界最小流

题目：AcWing 2190

算法详解：先使用有源汇上下界可行流算法算出一个可行流，再在这个残余网络上跑一遍tt到ss的最大流（反向边的流量增加等价于正向边的的流量减少。因此在残余网络上找出tt到ss的流就相当于减小了ss到tt的流）。最终的最小流流量 = 可行流流量 - tt到ss的最大流的流量。

代码：

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
109
110
111
112
113
#include<bits/stdc++.h>
using namespace std;

const int N = 50003 + 10;
const int M = (125003 + N) + 10;
const int inf = 0x3f3f3f3f;

int n, m, s, t, ss, tt, tot = 1 , tott;
int head[M<<1], d[N], cur[M<<1], delta[N];

struct Edge
{
	int to, next, cap, flow;
}e[M<<1];

void add(int a, int b, int c, int d)
{
	e[++tot].cap = d-c; e[tot].flow = 0; e[tot].to = b; e[tot].next = head[a]; head[a] = tot;
	e[++tot].cap = 0; e[tot].flow = 0; e[tot].to = a; e[tot].next = head[b]; head[b] = tot; 
}

bool bfs(int s, int t)
{
	memset(d, 0, sizeof d);
	d[s] = 1;
	cur[s] = head[s];
	queue<int> q;
	q.push(s);
	while(!q.empty())
	{
		int u = q.front();
		q.pop();
		for(int i = head[u]; ~i; i = e[i].next)
		{
			int v = e[i].to;
			if(!d[v] && e[i].cap > e[i].flow)
			{
				d[v] = d[u]+1;
				cur[v] = head[v];
				if(v == t) return 1;
				q.push(v);
			}
		}
	}
	return 0;
}

int dfs(int u, int lim, int t)
{
	if(u == t) return lim;
	int res = lim;
	for(int i = cur[u]; ~i && res; i = e[i].next)
	{
		cur[u] = i;
		int v = e[i].to;
		if(d[v] == d[u]+1 && e[i].cap > e[i].flow)
		{
			int k = dfs(v, min(res, e[i].cap-e[i].flow), t);
			if(!k) d[v] = 0;
			e[i].flow += k;
			e[i^1].flow -= k; 
			res -= k;
		}	
	}
	return lim-res;
}

int dinic()
{
	int maxflow = 0;
	while(bfs(s, t)) maxflow += dfs(s, inf, t);
	return maxflow;
}

int main()
{
	memset(head, -1, sizeof head);
	cin>>n>>m>>ss>>tt;
	s = 0;
	t = n+1;
	for(int i = 0; i < m; i++)
	{
		int a, b, c, d; cin>>a>>b>>c>>d;
		add(a, b, c, d);
		delta[a] -= c;
		delta[b] += c;
	}
	for(int i = 1; i <= n; i++)
	{
		if(delta[i] > 0)
		{
			add(s, i, 0, delta[i]);
			tott += delta[i];
		}
		if(delta[i] < 0)
			add(i, t, 0, -delta[i]);
	}
	add(tt, ss, 0, inf);
	if(dinic() != tott)
	{
		cout<<"No Solution";
		return 0;
	}
	int ans = e[tot].cap-e[tot].flow;
	e[tot].flow = e[tot].cap;
	e[tot-1].flow = e[tot-1].cap;
	// 重点
	s = tt; t = ss;
	ans -= dinic();
	cout<<ans<<endl;
	return 0;
}

多源汇

多源汇最大流

题目：AcWing 2234

算法详解：新建超级源点S，向所有源点连容量为inf的边，汇点同理。问题即转化为普通最大流问题。

代码：

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
#include<bits/stdc++.h>
using namespace std;

const int N = 1e4 + 10;
const int M = 2*(1e5+1e4) + 10;
const int inf = 0x3f3f3f3f;

int n, m, ss, tt, s, t, tot = 1;
int head[N], ver[M], edge[M], Next[M], level[N], cur[N];

void add(int a, int b, int c)
{
	ver[++tot] = b; edge[tot] = c; Next[tot] = head[a]; head[a] = tot;
	ver[++tot] = a; edge[tot] = 0; Next[tot] = head[b]; head[b] = tot;
}

bool bfs()
{
	memset(level, -1, sizeof level);
	queue<int> q;
	level[s] = 0;
	cur[s] = head[s];
	q.push(s);
	while(q.size())
	{
		int x = q.front(); q.pop();
		for(int i = head[x]; i; i = Next[i])
		{
			int y = ver[i];
			if(level[y] == -1 && edge[i])
			{
				level[y] = level[x] + 1;
				cur[y] = head[y];
				if(y == t) return true;
				q.push(y);
			}
		}
	}
	return false;
}

int dfs(int u, int limit)
{
	if(u == t) return limit;
	int flow = 0;
	for(int i = cur[u]; i && flow < limit; i = Next[i])
	{
		cur[u] = i;
		int v = ver[i];
		if(level[v] == level[u]+1 && edge[i])
		{
			int t = dfs(v, min(edge[i], limit-flow));
			if(!t) level[v] = -1;
			flow += t;
			edge[i] -= t;
			edge[i^1] += t;
		}
	}
	return flow;
}

int dinic()
{
	int ans = 0;
	while(bfs()) ans += dfs(s, inf);
	return ans;
}

int main()
{
	cin>>n>>m>>ss>>tt;
	s = 0;
	t = n+1;
	while(ss--) 
	{
		int x; cin>>x;
		add(s, x, inf);
	}
	while(tt--) 
	{
		int x; cin>>x;
		add(x, t, inf);
	}
	while(m--)
	{
		int a, b, c; cin>>a>>b>>c;
		add(a, b, c);
	}
	cout<<dinic()<<endl;
}

费用流

最小费用最大流

题目：AcWing 2174

算法详解：从源点到汇点找以单位费用为边权的最短路，然后沿着最小费用增流，直到找不到最小费用路为止。
算法实现：
（1）求最小费用路（SPFA），从源点出发，沿着可行边（e[i].cap > e[i].flow）广度优先搜素每个邻接点，若当前距离dist[v] > dis[u]+e[i].cost，则更新dist[v] = dis[u]+e[i].cost，并更新前驱。
（2）沿最小费用路增流，从汇点逆向到源点，找可增量d = min(d, e[i].cap - e[i].flow)。然后沿着最小费用路正向边增流d，反向边减流d。产生的费用mincost += dist[t]*d。

代码：时间复杂度：O(n$m^{2}$)

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
#include<bits/stdc++.h>
using namespace std;

const int N = 10 + 5e3;
const int M = 10 + 5e4;
const int inf = 0x3f3f3f3f;

int n, m, s, t, ss, tt, tot = 1, maxflow, mincost;
int head[M<<1], d[N], pre[N], dist[N];
bool vis[N];

struct Edge
{
	int to, next, cap, flow, cost;
}e[M<<1];

void add(int a, int b, int c, int d)
{
	e[++tot].cap = c; e[tot].flow = 0; e[tot].cost = d; e[tot].to = b; e[tot].next = head[a]; head[a] = tot;
	e[++tot].cap = 0; e[tot].flow = 0; e[tot].cost = -d; e[tot].to = a; e[tot].next = head[b]; head[b] = tot; 
}

bool spfa()
{
	memset(vis, false, sizeof vis);
	memset(pre, -1, sizeof pre);
	memset(dist, 0x3f, sizeof dist);
	queue<int> q;
	vis[s] = true;
	dist[s] = 0;
	q.push(s);
	while(q.size())
	{
		int u = q.front(); q.pop();
		vis[u] = false;
		for(int i = head[u]; ~i; i = e[i].next)
		{
			int v = e[i].to;
			if(e[i].cap > e[i].flow && dist[v] > dist[u]+e[i].cost)
			{
				dist[v] = dist[u]+e[i].cost;
				pre[v] = i;
				if(!vis[v])
				{
					q.push(v);
					vis[v] = true;
				}
			}
		}
	}
	return pre[t] != -1;
}

void MCMF()
{
	maxflow = mincost = 0;
	while(spfa())
	{
		int d = inf;
		for(int i = pre[t]; ~i; i = pre[e[i^1].to]) 
			d = min(d, e[i].cap-e[i].flow);
		maxflow += d;
		for(int i = pre[t]; ~i; i = pre[e[i^1].to])
		{
			e[i].flow += d;
			e[i^1].flow -= d;
		}
		mincost += dist[t]*d;
	}
}

int main()
{
	memset(head, -1, sizeof head);
	cin>>n>>m>>s>>t;
	for(int i = 1; i <= m; i++)
	{
		int a, b, c, d; cin>>a>>b>>c>>d;
		add(a, b, c, d);
	}
	MCMF();
	cout<<maxflow<<" "<<mincost<<endl;
}

最小费用可行流

正在做题，先把前面的给出来吧

后记：
（1）推荐一篇讲解上下界网络流问题的博客：(上下界问题建议看看这位的，讲的很详细也很好，我也参考了这位的博客)
https://www.cnblogs.com/liu-runda/p/6262832.html

（2）如果有任何问题或者建议还请留言反馈，我会讲解或更改。