.png)
什么是网络流
网络流是一张有向图，图中的每条有向边 (x,y) 都有一个给定的权值 c(x,y)，称其为边的容量。还有两个特殊的节点 S 和 T，我们称其为源点和汇点。
设 f(x,y) 为定义在 x,y 上的一个函数，其满足：
- f(x,y) \leq c(x,y)。即函数的值不超过边的容量。
- f(x,y) = -f(y,x)。即 x,y 调换时，函数值相反。
- \forall x \neq S,x \neq T，\sum_{(u,x)}f(u,x) = \sum_{(x,v)} f(x,v)。即当 x 不是 S 或 T 时，流入 x 的流量和流出 x 的流量相等。
上面三条，阐述了这个函数的三个性质：容量限制、斜对称和流守恒性。
f 被称为网络的流函数，f(x,y) 称为边的流量，c(x,y)-f(x,y) 称为边的剩余容量。
流守恒性告诉我们网络中除了源点和汇点，其他节点不储存流。网络流模型可以描述为：在不超过容量限制的情况下，“流量”不断从源点产生，途径各个边，最后归入汇点。
最大流
给定一个网络，则合法的 f 函数有很多，其中使 \sum_{(S,v)}f(S,v) 最大的流函数称之为网络的最大流。
网络流能解决的问题有很多，比如之前文章中介绍到的二分图最大匹配。
我们设置一个源点 S 和一个汇点 T，从 S 向所有左部点连接一条容量为 1 的边，从所有右部点向 T 连接一条容量为 1 的边。这代表每个点最多连接一条边。
再从左部点向右部点连接一条容量为 1 的边，这代表两点能连一条边。
如果是二分图多重匹配呢？只需要修改连接源点、汇点的边的容量为匹配上限即可。
Dinic 算法解决网络最大流
如果一条从 S 到 T 的路径上各边的剩余容量都大于 0，则称这条路径是一条增广路。显然，可以让新的流量通过增广路，增加网络流量。
Dinic 算法的思想是，对图进行一次 BFS，如果边还有剩余容量，则继续搜索，过程中标记点的深度。
可以发现，在 BFS 的过程中，所有的增广路都会被发现，接下来要处理这些增广路。
接下来，对图进行多次 DFS，如果能到达 T，则说明找到了一条增广路，此时使用贪心的思想，将增广路上所有的剩余容量都使用掉（体现为找到剩余容量的最小值），记录这次增加的流量。
我们会发现，在寻找增广路的过程中使用了贪心的思想，但是贪心不一定对，所以，我们引入反边。
反边的初始容量为 0，随着寻找增广路的过程中正边的剩余容量减少，令反边的剩余容量增加，这样子，反边就变得“可以增广”，在后续的搜索中，就可能走过反边，进而实现“反悔贪心”的操作。
下面给出 vector 版本实现P3376 【模板】网络最大流 - 洛谷的代码。
二分图最大匹配的必须边和可行边
给定一张二分图，其最大匹配的方案不一定唯一。若任意最大匹配方案的匹配边都包括 (x,y)，则称 (x,y) 是二分图最大匹配的必须边；如果 (x,y) 属于至少一个最大匹配方案，则称 (x,y) 是二分图最大匹配的可行边。