世间万物就这样与我们毫无关联地独自变化；一眨眼，一低头，景色就会立刻不一样。没有觉察到这一点的话，就感觉很可惜呢。——《此花亭奇谭》

网络流

不 明 意 义的解释

网络流的话，你可以把它想象成是一个城市水管网络，自来水厂（源点）的水通过纵横交错的水管网络和很多中转站（中间的点）到达你家（汇点），而这些水管有粗有细，能通过这些水管的水（流量）也不同，而我们要求的就是最终到达你家的最大水流。

基本概念

源点 ：整个图的起点，源点的流量是无限大的。

汇点 ：整张图的终点，流量为 。

（都到终点了还要什么流量，难道你也住在水管里？）

流量 ：，一般用 表示。

容量网络：设有向图 ，在点集 中指定源点 和汇点 ，对于每条边 有权值 。

网络流：边集 上流量集合 。

可行流：若一条边对每一起点满足总流出量与总流入量之差不大于提供能力，对每一终点满足总流入量与总流出量之差不小于接收能力，则称这个流为可行流。即 。

增广路（这个非常重要）：从源点到汇点路径中一条交替联通两个集合的路径，其边上的流量均大于零。

残留网络（这个也非常重要）：如果一张图，已经找过增广路了（并且流量已被用过），那这你就可以把它当成是残留网络，但是残留网络里还是可以走路径的（仍可以进行增广）。且每一次增广都在残留网络中进行，直到没有增广路为止。

切割（显然，这个同样很重要）： 的割是 ，即把点集划分 和 两个部分。

网络流的开始

好差不多了，我们来看张图片。

我是一个网络流的图

假设我们从 走的话，得到的结果是 ，因为边 的流量为 ，你无法再从 到达汇点 了。

我是一个残余网络

但是这样得到结果并不优， 和 得到的结果是 （流到你家的水变多了！）， 才是我们要得到的解。

基于这个想法，我们可以给每条边加上一个反向边。这样就做到了如果不是最优解，还能跑回去更新一遍最优解，相当于给了程序一个反悔的机会。

Ford-Fulkerson

这是一个很差劲的算法，是标题吸引你划下来的。

时间复杂度： 

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
int dfs (int x, int flow) // dfs求任意路径，x记当前搜索点，flow记这条边的流量 
{
    if (x == t) // 仍可以走到 
    {
        ans += flow; // 加上本次增广得到的流量  
        flag = 1; // 标记为可以找到 
        
    	return flow; // 返回流量，接下来尝试去找更优解
    }
    mark[x] = 1; // 做标记
    for (int i = f[x].head; ~i; i = f[i].next) // 链式前向星遍历，~i 等价于 i!=-1 
    {
        int x1 = f[i].to; // 记录这条边的终点 
        if (mark[x1] || f[i].b == 0) 
	    	continue; // 这条边已经走过，或者这条边的流量为0（已经被榨干了） 
        int delta = dfs (x1, min (flow, f[i].b)); // 给dfs传入这条增广路的最小流量（也就是瓶颈边）
        if (flag == true) // 首先我找到了增广路，再尝试更新一遍寻找最优解 
        {
            f[i].b -= delta; // 减去我本次得到的流量 
            f[i^1].b += delta; // 给反向路加上 
            
            return delta; // 依旧返回 
        }
    }
    
    return false; // 找不到了，此时会返回false，结束函数 
}
void FF ()//有增广路就增广
{
    memset (mark, 0, sizeof (mark));//初始化标记 
    flag = false;
    dfs (s, INF); // INF表示流量为0
    while (flag == true) // 确保还有路可以增广 
    {
        memset (mark, 0, sizeof (mark)); // 初始化标记，每次都需要 
        flag = false; // 先做false标记 
        dfs (s, INF); // 那么如果没有增广路，就会退出 
    }
    
    return ; 
}

注释里应该讲得挺清楚的了，可以去自己模拟一下，利用 一路走到底，如果可以通到汇点，那就加上流量，然后再用反向边来找一下更优解。

可是这真是太慢了。

未吸氧（不要在意我的背景）：

显然很慢

然后是 ：

显然这连模板题都过不了啊

就算是吸了氧，得到的结果也是大大的 ，唯一的区别可能就是内存小了点。

既然可以使用 ，为什么不可以用 + 队列试试看呢

开搞

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
bool bfs ()
{
    memset (vis, 0, sizeof (vis)); // 初始化标记数组 
    queue<int> q; // 新建一个队列 
    q.push (s); // 将源点推入队列 
    vis[s] = 1; //标记源点为已走过 
    incf[s] = inf; // 源点流量为无限 
    while (q.size ()) // 只要队列不为空就继续增广，这里同样可以写成q.empty() 
    {
        int now = q.front (); // 取出队列中的第一个元素
		q.pop (); // 并删除掉它（过河拆桥） 
        for (int i = head[now]; i; i = e[i].nxt) // 老规矩前向星遍历 
		{
            if (e[i].w == 0 || vis[e[i].v]) 
            	continue; // 如果这条边已被标记或没有流量就剪枝 
            int to = e[i].v; // 记录这条边的终点 
            incf[to] = min (incf[now], e[i].w); // 记录当前增广的路径的最小流量 
            pre[to] = i; // 记录路径边的编号（方便增广） 
            q.push (to); // 将这条边的终点推入队列准备找增广路 
            vis[to] = 1; // 记录这个点为走过
            if (to == t) 
	    		return 1; // 走到汇点就直接退出（都说了你家不是水管！） 
        }
    }
    
    return 0;
}

用 分层式的找增广路，用反向边找最优解，那这个算法应该很好吧。

其实，我还是觉得很不舒服。

看结果，加不加 没有什么区别：

最后几个点卡过去了！！

还有没有更好的算法呢？（对啊有没有更好的算法呢？）

有，这种算法还是 算法提出者提出的。

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
bool bfs () // 广搜分层 
{
	memset (d, -1, sizeof (d)); // 初始化深度（分层） 
	queue<ll> q; // 新建一个队列 
	q.push (s); // 将源点推入队列 
	d[s] = 0; // 源点的深度为0 
	cur[s] = head[s]; //  获取源点指向的第一个点（由源点扩展出去） 
	while (q.size ()) // 队列不为空 
	{
		ll u = q.front (); // 取出队头 
		q.pop (); // 删掉队头 
		for (ll i = head[u]; i; i = Next[i]) // 前向星遍历 
		{
			ll v = ver[i]; // 取出终点 
			if (d[v] == -1 && f[i]) // 如果深度未被标记，且这条路上仍有流量 
			{
				q.push (v); // 将这个终点推入队列 
				d[v] = d[u] + 1; // 这个点的深度是这条边的起点加 1 
				cur[v] = head[v]; // 遍历时取出这条边的终点 
				if (v == t) // 如果已经搜到汇点 
					return true; // 结束一次增广 
			}
		}
	}
    
	return false;
}

示意图大概是这样：

分层图我就想到分层设色地形图www

注释应该很清楚了，可以自己手动模拟一下

然后是 部分：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int dfs (int u, int limit) // u是当前搜索点，limit是这条边上的瓶颈边权（即这条路上的最小流量） 
{
	if (u == t) // 搜到汇点，递归结束 
		return limit; // 返回这条边上的最小值（瓶颈边） 
	int flow = 0; // flow是我当前走这条增广路获得的流量 
	for (int i = cur[u]; i && flow < limit; i = Next[i]) // 遍历 
	{
		cur[u] = i; // 取出起点 
		ll v = ver[i]; // 取出终点 
		if (f[i] != 0 && d[v] == d[u] + 1) // 确保这条边的流量不为零且深度是加一的 
		{
			int fl = dfs (v, min (f[i], limit - flow)); // 深搜下去 
			if (!fl) // 这条流量不为零 
				d[v] = -1; // 记录深度为不可走 
			f[i] -= fl; // 减去流量 
			f[i ^ 1] += fl; // 反向边操作 
			flow += f; // 加在这条增广路上获得的流量和上 
		}
	}
    
	return flow; // 返回这条增广路上得到的流量 
}

注意，有一段代码很难理解，这边我讲一下（如果能自行理解就请跳过这一段，因为我被这个东西搞了一天）

1
dfs (v, min (f[i], limit - flow)

诶这段话就很有意思，传给下一次深搜的值是一个终点和一个最小值，二者分别是这条边的当前流量（容量），和当前获取流量减去最小值。

来看一张图：

卡了我两天的问题

很明显，最终得到的答案应该是 ，而不是两条增广路上的瓶颈边值 。

我们可以走 和 来得到最大流，但是整个过程是动态的，我们不应该只看当前图上的 和 （虽然现在这是两条增广路上的最小流）。但在经过上面那条增广路时， 的流量会减少 。

实际上是这样，请不要搞混淆

现在这个时候，上面那条路走不了了（因为没有流量），只能从下面走，而下面这条路此时的瓶颈边变成了 ，而最小流就只能是 ，最终得到的最大流就是 ，反则亦之。

不过还是要和容量比较的，因为可能容量是较小值，那这时候只能按容量来算了。

在程序中这样调用：

1
2
3
4
5
6
7
8
9
int dinic ()
{
	int maxflow = 0, flow = 0;
	while (bfs ()) // 找到增广路
		while (flow = dfs (s, inf)) // 开始增广
			maxflow += flow; // 加上本次增广得到的流量
    
	return maxflow;
}

重复进行一个“找增广路，往增广路走，更新最优解，增加最大流”的过程。

例题

这是一道非常经典的网络流题目，是你自己划下来看的。

草地排水

每到下雨的时候，三叶草地上就积聚了一潭水，这意味着草地被水淹没，不知所措。现在在草地下埋上水管网络，每个水管都有一定流量，问最大排水量。

这道题目和模板题几乎一模一样了吧……想法很简单，就是让我们算水管的最大流，从 点流到 点的最大流就是答案，那不也就是贴个板子的事。

完整代码：

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
#include <cstdio>
#include <queue>
#include <cstring>

using namespace std;

typedef unsigned long long ll;

const ll N = 210, M = 10010, inf = 1 << 30;
ll n, m, s, t, tot;
ll head[N], c[M], Next[M], ver[M];
ll d[N], cur[N];

void add (ll x, ll y, ll  z)
{
	c[++tot] = z, ver[tot] = y, Next[tot] = head[x], head[x] = tot;
	c[++tot] = 0, ver[tot] = x, Next[tot] = head[y], head[y] = tot;
}
bool bfs ()
{
	memset (d, -1, sizeof (d));
	queue<ll> q;
	q.push (s);
	d[s] = 0;
	cur[s] = head[s];
	while (q.size ())
	{
		ll u = q.front ();
		q.pop ();
		for (ll i = head[u]; i; i = Next[i])
		{
			ll v = ver[i];
			if (d[v] == -1 && c[i])
			{
				q.push (v);
				d[v] = d[u] + 1;
				cur[v] = head[v];
				if (v == t)
					return true;
			}
		}
	}

	return false;
}


ll dfs (ll u, ll limit)
{
	if (u == t)
		return limit;
	ll flow = 0;
	for (ll i = cur[u]; i && flow < limit; i = Next[i])
	{
		cur[u] = i;
		ll v = ver[i];
		if (c[i] != 0 && d[v] == d[u] + 1)
		{
			ll f = dfs (v, min (c[i], limit - flow));
			if (!f)
				d[v] = -1;
			c[i] -= f, c[i ^ 1] += f;
			flow += f;
		}
	}
    
	return flow;
}
ll dinic ()
{
	ll maxflow = 0, flow = 0;
	while (bfs ())
		while (flow = dfs (s, inf))
			maxflow += flow;
    
	return maxflow;
}
int main ()
{
	scanf ("%d %d", &m, &n);
	s = 1, t = n;
	tot = 1;
	while (m --)
	{
		ll u, v, c;
		scanf ("%d %d %d", &u, &v, &c);
		add (u, v, c);
	}
    
	return cout << dinic (), 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
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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <bits/stdc++.h>
#define N 1000001
#define int long long

using namespace std;

int n, p, q, S, T;
int cnt = 1, head[N], deep[N], cur[N];
int k;

struct Edge {
	int to, f, nxt;
}edge[N];

inline void add_edge (int u, int v, int w) // 建边 
{
	edge[++cnt].f = w;
	edge[cnt].to = v;
	edge[cnt].nxt = head[u];
	head[u] = cnt;
    
	return ; 
}

inline bool bfs ()
{
	memset (deep, -1, sizeof (deep));
	queue<int> q;
	q.push (S);
	deep[S] = 0;
	cur[S] = head[S];
	while (!q.empty ())
	{
		int u = q.front ();
		q.pop ();
		for (int i = head[u]; i; i = edge[i].nxt)
		{
			int v = edge[i].to;
			if (deep[v] == -1 && edge[i].f)
			{
				q.push (v);
				deep[v] = deep[u] + 1;
				cur[v] = head[v];
				if (v == T)
					return true;
			}
		}
	}
	
	return false;
}

inline int dfs (int u, int limit)
{
	if (u == T)
		return limit;
	int flow = 0;
	for (int i = cur[u]; i && flow < limit; i = edge[i].nxt)
	{
		cur[u] = i;
		int v = edge[i].to;
		if (edge[i].f != 0 && deep[v] == deep[u] + 1)
		{
			int f = dfs (v, min (edge[i].f, limit - flow));
			if (!f)
				deep[v] = -1;
			edge[i].f -= f, edge[i ^ 1].f += f;
			flow += f;
		}
	}
	
	return flow;
} 

int dinic ()
{    
	int maxflow = 0, flow = 0;
	while (bfs ())
		while (flow = dfs (S, N))
			maxflow += flow;
			
	return maxflow;
}

signed main ()
{
	scanf ("%lld %lld %lld", &n, &p, &q);
	S = 1;
	T = n * 2 + p + q + 2; // 总共的点数是 n * 2 + p + q + 2 
	for (int i = 1; i <= n; i ++) // 给 房间 --> 人本体 建边 
	{
		for (int j = 1; j <= p; j ++)
		{
			scanf ("%lld", &k);
			if (k == 1)
			{
				add_edge (j + 1, 1 + p + i, 1); // 第 i 个人 喜欢 第 j 个房间 
				add_edge (1 + p + i, j + 1, 0); // 建反向边 
			}
		}
	}
	for (int i = 1; i <= n; i ++) // 给 人分身 --> 菜 建边 
	{
		for (int j = 1; j <= q; j ++)
		{
			scanf ("%lld", &k);
			if (k)
			{
				add_edge (1 + p + n + i, 1 + p + n * 2 + j, 1); // 第 i 个人 喜欢 第 j 道菜 
				add_edge (1 + p + n * 2 + j, 1 + p + n + i, 0); // 建反向边 
			}
		}	
	}
	for (int i = 1; i <= p; i ++) // 给 源点 --> 房间 建边 
	{
		add_edge (1, 1 + i, 1);
		add_edge (1 + i, 1, 0); // 建反向边 
	}
	for (int i = 1; i <= q; i ++) // 给 菜 --> 汇点 建边 
	{
		add_edge (1 + p + n * 2 + i, 2 + n * 2 + p + q, 1);
		add_edge (2 + n * 2 + p + q, 1 + p + n * 2 + i, 0);
	}
	for (int i = 1; i <= n; i ++) // 给 人本体 --> 人分身 建边 
	{
		add_edge (1 + p + i, 1 + p + n + i, 1); // 第 i 个人 喜欢 第 i 个人（你也是屑魔女吗） 
		add_edge (1 + p + n + i, 1 + p + i, 0); // 建反向边 
	}
	
    return cout << dinic (), 0;
}

这种建边思想可以利用到别的网络流题目里去。

这边补充一个链式前向星建图的代码：

1
2
3
4
5
inline void add_edge (int u, int v, int w) // 前向星建边
{
	edge[++ cnt] = (Edge) {v, head[u], w}; 
	head[u] = cnt;
}

这是从一个大佬那边看到的，完全可以背板子，比前面的写得好。

去暴切网络流 题吧！！！