不想写证明了，挂篇文章。

网络流问题中，给定一个有向图 $G=(V,E)$，每条边 $(u,v)$ 有一个非负容量 $c(u,v)$。指定源点 $s$ 和汇点 $t$，求从 $s$ 到 $t$ 的最大可行流量，即最大流问题。

P3381 【模板】最小费用最大流。

增广路与反向边

所有最大流算法都基于增广路定理：当前流 $f$ 是最大流当且仅当残余网络中不存在从 $s$ 到 $t$ 的增广路。残余网络包含原图所有边以及反向边，反向边允许“撤销”之前不满意的流量分配，使算法能够不断调整至最优。

Ford-Fulkerson

最朴素的思想：在残余网络中任意找一条增广路（通常用 DFS），将路径上的最小残余容量加到答案上，并更新正向边和反向边，重复直到没有增广路。

正确性：依赖于最大流最小割定理，只要算法终止，结果就是最大流。

复杂度：$O(E \cdot |f|)$，其中 $|f|$ 是最大流值。当容量为整数时有限步终止，但可能很慢（例如容量很大时）。若容量为无理数，甚至可能无限循环。

Edmonds-Karp

Ford-Fulkerson 的改进：每次用 BFS 找最短增广路（边数最少），可以保证增广次数为 $O(VE)$，总复杂度 $O(VE^2)$。

为什么选最短路径？ BFS 保证了每次找到的路径是当前残余网络中的最短路径，从而可以证明每次增广后汇点 $t$ 到源点的距离严格增加，因此增广次数有限。

Dinic 算法

Dinic 算法在 Edmonds-Karp 的基础上更进一步，通过分层图在一次 DFS 中寻找多条增广路，极大提高了效率。

BFS 建分层图：从 $s$ 开始 BFS，只经过还有容量的边，记录每个节点的层次（到 $s$ 的最短距离）。如果无法到达 $t$，算法结束。

DFS 多路增广：在分层图上从 $s$ 出发进行 DFS，只允许流向层次恰好为当前层+1的节点，找到一条增广路就立即增广，并继续从当前节点尝试其他分支（即多路增广）。利用当前弧优化避免重复遍历已经流满的边。

重复步骤1-2，直到 BFS 无法到达 $t$。

BFS 建立的分层图保证了所有从 $s$ 到 $t$ 的路径长度都是当前残余网络中的最短长度。DFS 严格按层次递增方向走，确保找到的增广路都是最短路径。这一定位使得我们可以证明一个重要引理：

每完成一个阶段（即找到阻塞流后），汇点 $t$ 的层次必然增加。

因为反向边不会在同阶段被用于正向增广（它们指向低层），所以填满某些边后，下一阶段的最短路径长度至少增加1。由于节点数有限，阶段数不超过 $|V|$。每个阶段内寻找阻塞流的复杂度为 $O(VE)$，因此总复杂度 $O(V^2E)$，远优于 Edmonds-Karp。

P1344 [USACO4.4] 追查坏牛奶 Pollutant Control

P1344 [USACO4.4] 追查坏牛奶 Pollutant Control。

求中间用的边的数量就将边权乘上一个很大的值然后加一就行了，只需要一次。

P3381 【模板】最小费用最大流

P3381 【模板】最小费用最大流。

直接贪心，选取最小代价的增广路。

建议使用 EK。

P2045 方格取数加强版

P2045 方格取数加强版。

网络流建模也很困难。

多次走只算一次的让我们想到了网络流。

我们发现这道题是有两个维度的，路径限制和数字和。

路径是最多 $k$ 条，对应到网络流上就是流量被限制为 $k$。然后费用我们需要让它大，最大费用流。

然后我们要用一个技巧：拆点，就是把一个点拆成两部分，我们拆成 $in$ 和 $out$，就可以计算中间的边权作为点权了。

超级源点向 $1$ 连边，流量 $k$，费用 $0$。

还有，这道题其实很简单，不会出现负环。

P3358 最长k可重区间集问题

P3358 最长k可重区间集问题。

这怎么想到网络流？

先离散化，然后 $l,r$ 就在 $n*2$ 以内了。

我们发现这道题有一个 $k$ 的限制，我们转化一下，就是有 $k$ 条路径，每一条可以选择一些互不相交的区间，然后最大化最后的费用。

建边方法：

$S$ 到 $1$ 是流量为 $k$ 费用为 $0$。

$n$ 到 $T$ 是流量为 $k$ 费用为 $0$。

$i$ 到 $i+1$ 是流量为 $k$ 费用为 $0$。

$l$ 到 $r$ 是流量为 $1$ 费用为 $r-l+1$。

最小费用最大流。

CF277E Binary Tree on Plane

CF277E Binary Tree on Plane。

我也不知道怎么想到网络流。这道题我们需要从上向下思考，然后覆盖过程有点像网络流？

反正就这样吧，从源点向所有节点连流量为 $2$ 的边，表示最多 $2$ 个儿子，从节点向汇点连流量为 $1$ 的边表示这只能从一个父亲出发。

然后点之间，就是父亲连向儿子。最后形成的路径是 $s\to fa \to x \to t$。

然后费用为距离，最小费用最大流。

但是有一个问题就是这样无法保证父子关系长度，有可能路径中间只有一个点。

于是我们有想到了拆点，也就是将一个点拆成两半，$s$ 连接左边的，$t$ 连接右边的，中间就是第一个点的左连第二个的右。

这样的话，我们就可以让每一条网络流路径都是边了。最后判断答案是否可行就看流量是否为 $n-1$。

CF863F Almost Permutation

CF863F Almost Permutation。

先简化一下问题，我们根据条件，可以求出 $a_i$ 的取值范围 $l_i\le a_i\le r_i$。

然后大概建一下模：

$S\to a_i~ (1,0)$

$a_i\to[l_i,r_i]~(1,0)$

$i\to t~(1,0)$

然后，一个不好处理的就是平方。物理运动学做多的都知道，这是一个 $1,3,5,7,9\cdots$ 这样的序列，也就是边权依次增加。

我们想办法要让最后加上这个值，可以通过流量限制。

也就是：

总结：流量还有限制和后效性作用，可以一定地记录中间的情况。

P4249 [WC2007] 剪刀石头布

P4249 [WC2007] 剪刀石头布。

反正我不知道该怎么想到网络流。

这种环的问题可以转化成度。

如果没有三元环，那一定一个入度为 $2$，一个入度和出度都为 $1$，还有一个初读为 $2$。

所以我们选一个，从入度来看。

如果入度为 $2$ 会少一个三元环，如果是 $3$ 就是 $3$ 个，找出规律，会少 $\frac {d\times(d-1)}{2}$ 个，所以最后的答案就是：

$\frac{n(n-1)(n-2)}{6} - \sum_{u \in V}\frac {deg_u\times(deg_u-1)}{2}$

然后就感觉跟上一道题很像了（好像上一道题原本也是黑，然后降了）。

然后就是如果 $d$ 增加，就会有 $\frac {d\times(d+1)}{2}-\frac {d\times(d-1)}{2}=d$ 的代价。

完了，我脑子的 cpu 烧了（其实昨天是电脑）。

我们将原来的边设为网络流中的点。

$s\to i~(1,0)$

$i\to u_i,v_i~(1,0)$（容量不够，只有一个成立）

$j\to t~(1,0)\\ j\to t~(1,1)\\ j\to t~(1,2)\\ \cdots$

最大权闭合子图

DPSK 讲解。

技巧：就是分成左右两个集合。

还有题解中的讲解，比较清晰。。

我的总结。

P2057 [SHOI2007] 善意的投票 / [JLOI2010] 冠军调查

P2057 [SHOI2007] 善意的投票 / [JLOI2010] 冠军调查。

最大权闭合子图？？？

一个技巧，这道题 S 连接赞成票的人，T 连接反对票的人，进行最小割。

我们将朋友相连，如果他们不同，可以选择改变一个的观点，也可以不改变。在网络流中的体现就是最小割。改变就是割边变成和 $S$ 的连边加上这个点在 $S$ 这个集合的朋友。

P4313 文理分科

P4313 文理分科。

假如我们知道这是网络流的题。不是。

我们如果不知道这是网络流的题，可以把文科节点放左边，理科放右边。

$S$ 向所有点连接容量为 $art_{i,j}$ 的边，所有点向 $T$ 连接容量为 $science_{i,j}$ 的边。

然后我们发现这道题还有 $same$ 系列的，可以新建节点单独计算。

$S$ 向 $sa_{i,j}$ 连接容量为 $same\_art_{i,j}$ 的边，然后 $sa_{i,j}$ 向这五个点连接 $+\infin$ 的边（表示必须连接）。

$ss$ 同理。但是注意不要把边建反了。

总方案数减去最小割就行了。

P3227 [HNOI2013] 切糕

P3227 [HNOI2013] 切糕。

既然是 切 了，那就是将这个东西分成上下两部分，理所应当想到最小割。

我们建图，$S$ 向第一层的点，第 $R+1$ 层连接 $T$，容量为 $+\infin$（割不掉）。

然后就是中间的点，第 $k$ 层向 $k+1$ 层连接容量为 $v_{i,j,k}$ 的边。

接着我们需要处理这个相邻的间距 $\le D$ 的限制，我们直接连个割不掉的边就行了，从 $k$ 向相邻的 $k-d$ 连边。

在草稿本上模拟一下：

|    |
|.   |
| .  |
|  . |
|   .|
|    |
（中间的边方向是从左到右）
要把这两个隔断显然不能从左边的高点和右边的低点个割。

P3749 [六省联考 2017] 寿司餐厅

P3749 [六省联考 2017] 寿司餐厅。

如果我们考场上得知这是网络流的题，我们因该回去往最大权闭合子图上想。

至于怎么做？我们发现，如果选择了 $d_{i,j}$，一定会去选 $d_{i,j-1}$ 和 $d_{i+1,j}$。

然后每一个点的权值是 $d_{i,j}-a_i$。

如果大于 $0$，就 $s$ 向他连边，表示割掉的代价，否则向 $t$ 连边，表示选择的代价。

然后还有就是如果选择了 $d_{i,i}$，那一定会向 $a_i$ 连边，然后对于所有 $a_i$ 都需要向 $t$ 连接 $a_i\times a_i$ 的边。

最后的答案就是向 $s$ 连的边的总长度减去最小割。

CF903G Yet Another Maxflow Problem

CF903G Yet Another Maxflow Problem。

这道题数据范围很大。

我们可以换个问题，直接算最小割。

在 $A$ 中会可能有一个割点，$B$ 中也有可能，然后中间也有一些。

此时，答案是 $a_x+b_y+\sum_{i\ge x,j<y}c_{i,j}$。

然后还有 $A,B$ 都不割的情况，就建边权为 $0$ 的即可。

现在的问题是，怎么快速求出：

目前，这道题已经跟网络流没什么关系了考虑数据结构。

我们将 $x$ 固定，然后需要维护的是：

我们需要改变的是 $A$ 中的边的容量，所以上面的式子的值是不变的。

然后线段树。预处理和询问的两棵树可以只写一颗，区修查询全局最小值。

上下界网络流

这个图解好。

P14578 【模板】无源汇上下界可行流

P14578 【模板】无源汇上下界可行流。

直接抄 OIWIKI 的。

首先，每条边有最小限制，所以我们先让这条边先流那么多。

然后，设流入流量减初始流出流量为 $M$。

若 $M=0$，此时流量平衡，不需要附加边。

若 $M>0$，此时入流量过大，$S$ 向其连流量为 $M$ 的附加边。

若 $M<0$，此时出流量过大，需要向 $T$ 连流量为 $-M$ 的附加边。

在建图完毕之后跑 $S$ 到 $T$ 的最大流，若 $S$ 连出去的边全部满流，则存在可行流，否则不存在。

有源汇上下界可行流

新建一条从 $t$ 到 $s$，限制为 $[0,+\infin]$ 的边。

然后新建源点和汇点 $s',t'$，建图就行了。

P14579 【模板】有源汇上下界最大流

P14579 【模板】有源汇上下界最大流。

在可行流的基础上怎么做？

我们跑完了可行流之后，删去加的附加边。

然后在原来的基础上跑网络流。

P14580 【模板】有源汇上下界最小流

P14580 【模板】有源汇上下界最小流。

与有源汇上下界最大流类似，答案为可行流减去残量网络从 $t$ 到 $s$ 的最大流，可以理解为要退掉尽可能多的流。

P7173 【模板】有负圈的费用流

P7173 【模板】有负圈的费用流。

对于网络中的负边 $x\to y$，我们先让其直接满流。

然后加入 $y\to x$，费用为原来费用的相反数，相当于进行退流。

然后就是相当于有上下界最小费用最大流。

P4843 清理雪道

P4843 清理雪道。

这道题直接上下界费用流。

直接建出图之后保证下界为 $1$ 就行了。

CF708D Incorrect Flow

CF708D Incorrect Flow。

首先考虑在这道题怎么建边。

对于 $c\ge f$ 的边：

• $0\le f' \le f$：$(v,u,f,1)$。
• $f< f'\le c$：$(u,v,c-f,1)$。
• $f\le c< f'$：$(u,v,+\infin,2)$。

对于 $c < f$ 的边：

（在 $f > c$ 的情况下，先将基础代价 $f-c$ 加到答案 Ans 中）。

• $0 \le f' < c$：$(v,u,c,1)$。
• $c< f'\le f$：$(v,u,f-c,0)$。
• $f' < f$：$(u,v,+\infin,2)$。

建了这些边是为了满足原边的上下界网络流的限制（限制只能是那个流量），然后通过花费代价调整使其满足要求。

二分图

这个。

把讲义喂给 DeepSeek，然后...

对于一张图 $G = (V, E)$（无孤立点，否则边覆盖可能不存在），有：

• 边覆盖：一个边集 $E' \subseteq E$，使得任意顶点 $u \in V$ 都与 $E'$ 中至少一条边关联（即每个顶点都被覆盖）。

• 匹配：一个边集 $E' \subseteq E$，使得 $E'$ 中任意两条边没有公共顶点（即每个顶点至多与一条边关联）。

• 点覆盖：一个顶点集 $V' \subseteq V$，使得每条边 $e = (u,v) \in E$ 至少有一个端点属于 $V'$。

• 独立集：一个顶点集 $V' \subseteq V$，使得每条边 $e = (u,v) \in E$ 至多有一个端点属于 $V'$。

这些概念之间有着密切的数量关系，下面是两个重要的定理（证明已在PDF中给出）：

1. 最小边覆盖与最大匹配：若图不含孤立点，则

   $$\text{最小边覆盖的大小} + \text{最大匹配的大小} = |V|.$$

   证明思路：先取一个最大匹配 $M$，它覆盖了 $2|M|$ 个顶点。为了覆盖剩下的 $|V| - 2|M|$ 个顶点，至少需要添加 $|V| - 2|M|$ 条边（每条边覆盖一个新顶点），因此最小边覆盖大小为 $|M| + (|V| - 2|M|) = |V| - |M|$。

2. 最小点覆盖与最大独立集：

   $$\text{最小点覆盖的大小} + \text{最大独立集的大小} = |V|.$$

   证明思路：独立集 $V'$ 的补集 $V \setminus V'$ 是点覆盖，反之亦然，两者构成一一对应。因此最大独立集对应最小点覆盖，且大小之和为 $|V|$。

这两个关系说明，对于任意图，如果我们能求出最大匹配，就能得到最小边覆盖；如果能求出最小点覆盖，就能得到最大独立集。而在二分图中，由于有 K?nig 定理（最大匹配 = 最小点覆盖），我们可以通过最大匹配同时求出最小点覆盖和最大独立集，进而也得到最小边覆盖。这为后续网络流求解二分图相关问题奠定了基础。

二分图最大匹配
在二分图 $G=(V,E)$ 中，左部 $L$，右部 $R$，匹配是边集 $M\subseteq E$，使得任意两条边无公共顶点。最大匹配即包含边数最多的匹配。

网络流求法

• 建立源点 $S$ 和汇点 $T$。
• 从 $S$ 向左部每个点连容量为 $1$ 的边，表示每个左部点最多匹配一次。
• 从右部每个点向 $T$ 连容量为 $1$ 的边，表示每个右部点最多匹配一次。
• 对原图中的每条边 $(u,v)$（$u\in L, v\in R$），连 $u\to v$ 容量为 $1$ 的边。
• 跑最大流，最大流量即为最大匹配数，时间复杂度 $O(m\sqrt{n})$。

二分图最小点覆盖
点覆盖是顶点集 $V'\subseteq V$，使得每条边至少有一个端点属于 $V'$。最小点覆盖即包含顶点数最少的点覆盖。

Konig 定理：在二分图中，最大匹配的大小等于最小点覆盖的大小。

因为最小点覆盖大于等于最大匹配。

然后构造大小为最大匹配的点覆盖：

跑完最大流后，令 $V'$ 为残余网络上左部中源点能到达的点与右部中源点不能到达的点。则 $V'$ 是点覆盖：若一条边左端不在 $V'$ 中（即左端不可达），则右端必在 $V'$ 中（因为若右端可达，则左端可通过该边到达，矛盾）；同理，若右端不在 $V'$ 中，则左端必在 $V'$ 中。故所有边被覆盖。而 $|V'|$ 等于最小割容量，即最大流值，也就是最大匹配数。

因此最大匹配 = 最小点覆盖。

P4251 [SCOI2015] 小凸玩矩阵

P4251 [SCOI2015] 小凸玩矩阵。

这道题我们发现，一个行只能匹配一个列，一个列也只能匹配一个行。

那就 $S$ 向行连边，列向 $T$ 连边。

那个 $k$ 很烦，用一般的技巧，二分答案，问题就变成了是否有至少 $n-k+1$ 个数，使得这些数不大于当前值。

然后将矩阵中的这个值小于等于二分值的东西的 $i$ 行向 $j$ 列连边，二分图最大匹配。

这样限制了一行或者一列只能被用一次。

P2764 最小路径覆盖问题

P2764 最小路径覆盖问题。

比较妙的。

考虑转化问题，这个问题相当于给定一堆路径，然后需要进行合并，进行更多次的合并。

每一个点只能由最多一个前驱和最多一个后继。

所以考虑拆点，每一个点有前驱后继，然后前驱后继进行二分图最大匹配。

CF1592F2 Alice and Recoloring 2

CF1592F2 Alice and Recoloring 2。

也不知道这是怎么想出来的，就积累一下 Trick 吧。

首先，二三操作可以用两次一来代替，可以直接不考虑。

关于操作的题目有一个小技巧：寻找操作中的不变量。（tj 上的）

然后利用这个 Trick：关于区间操作的一些问题直接利用差分的思想，$b_{i,j}=a_{i,j}\oplus a_{i+1,j}\oplus a_{i,j+1}\oplus a_{i+1,j+1}$。

此时 $b$ 是从 $a$ 推出来的，但也可以直接推回 $a$。$b$ 的反推的过程就相当于还原差分。

然后我们发现，操作 $1$ 按照 $b$ 的定义，只有 $b_{i,j}$ 改变了。

操作 $4$ 中 $a_{n,m}$，$a_{n,j-1}$，$a_{i-1,m}$，$a_{i-1,j-1}$ 发生了改变。

然后又是一个性质了：不会同时使用 $op_4(x,y)$ 和 $op_4(x,y_2)$。同理不会同时使用 $op_4(x_1,y)$ 和 $op_4(x_2,y)$。因为这可以用四次 $1$ 来代替，所以我们不需要。

接着，除非 $(x, y)$，$(n, y)$ 和 $(x, m)$ 都为 $1$，才会使用 $op_4(x, y)$，不然可以用两次 $op_1$ 解决掉。

此时，第四个操作就会有限制了：

• 一行最多被操作一次。
• 一列最多被操作一次。
• 这个矩阵能被操作当且仅当 $(x, y)$，$(n, y)$ 和 $(x, m)$ 都为 $1$。

直接二分图最大匹配。

所以大体思路：将一个操作弄成最优，然后剩下的全用普适性操作。

每一个四操作可以节省 $1$，总数减去匹配数即可。

二分图完美匹配与 Hall 定理

Hall 定理
对于二分图 $G = (X, Y, E)$，存在一个匹配覆盖 $X$ 中所有顶点（即饱和 $X$ 的匹配）当且仅当

其中 $N(S)$ 表示 $S$ 在 $Y$ 中的邻点集合。

证明概要

• 必要性：若存在饱和 $X$ 的匹配，则 $S$ 中每个顶点在匹配中有一个不同的邻点，这些邻点都在 $N(S)$ 中，故 $|N(S)| \ge |S|$。
• 充分性（利用最大流最小割定理）：构造网络流：源点 $s$ 连每个 $x \in X$（容量 1），每个 $y \in Y$ 连汇点 $t$（容量 1），原边 $x \to y$ 容量 1。则最大匹配值等于最大流值。
  对任意 $s-t$ 割，设 $S$ 为割中未被割掉 $s \to x$ 边的 $X$ 中点集，则 $N(S)$ 必须全部割掉与 $t$ 的边，否则存在增广路。割的容量至少为 $|X| - |S| + |N(S)|$。由 Hall 条件 $|N(S)| \ge |S|$ 得该值 $\ge |X|$，故最小割 $\ge |X|$。由最大流最小割定理，最大流 $\ge |X|$，即存在饱和 $X$ 的匹配。

CF338E Optimize!

CF338E Optimize!。

给定一个长度为 $n$ 的序列 $A$ 和一个长度为 $len$ 的序列 $B$。求 $A$ 有多少长度为 $len$ 的连续区间和 $B$ 完美匹配。

两个序列完美匹配当且仅当存在一种各自打乱顺序的方案使得两个序列对应位置上的数的和都不小于 $h$。

不需要 Hall 定理？

对于在序列上难以解决的问题可以考虑在值域上解决（可以先离散化）。

$a_i+b_j \ge H$ 等价于 $a_i \ge H-b_j$。

用 $H-b_j$ 把 $b_j$ 替换。

然后我们操作变为判断一个区间能否满足存在排列 $p$ 使 $a_i \ge b_{p_i}$，单点修改序列 $a$。

建出值域线段树，序列 $a$ 上的为后缀减操作，序列 $b$ 为后缀加操作，查询是否存在有值小于 $0$。

这个过程能用 Hall 定理解释？！

CF1009G Allowed Letters

CF1009G Allowed Letters。

首先是贪心，我们从前往后考虑这个，然后判断当前是否能这样填。

也就是我们一步步确定前面的值。

然后我们发现，这是一个类似二分图的东西，有 $n$ 个位置和 $6$ 种字母的很多副本，然后需要进行匹配。

有一个比较暴力的做法就是网络流，直接暴力在判断当前是否可以的时候网络流进行匹配。

但是显然会超时，我们需要利用好性质。这是二分图，我们当然需要用二分图的性质。所以我们掏出了 Hall 定理。

根据 Hall 定理，我们可以在当前连到最优之后判断所有子集，看看是否存在匹配，也就是后续有没有解。

我们发现左边的很多，然后右边的有一个限制就是字符种类为 $6$。然后我们想一下就会发现，一个颜色的点连出的边是相同的，所以只需要 $6$ 个点，然后同时匹配，因为如果集合不完整的话集合的邻居不变。

Two-Sat