很多人说，图论就是背模板。

对于算法来讲是如此，但是我们在做题的时候，遇到的最大 的问题其实是如何转化为图论模型。

经常会发出“这竟然是一道图论题！”这样的感叹（比如我 在做2021年联合省选的时候）。

所以这节课，不仅介绍一些经典算法模型，选择的例题多为 需要转化问题的题目。

最短路

P6961 [NEERC 2017] Journey from Petersburg to Moscow

P6961 [NEERC 2017] Journey from Petersburg to Moscow。

用到了图论中的经典技巧，以 $0$ 为分界点。

枚举每一条边为第 $k$ 大的情况，然后将所有边的边权减去这条边的边权，然后将负数变成 $0$。

这样的话，比 $k$ 大的就不用算了。

然后怎么证明这个的正确性呢？

如果真实的比 $k$ 小，也就是 $0$ 多了，这样的话答案一定会更大，因为减去的要加回来。

如果真实的比 $k$ 大，也就是有很多没减成 $0$ 的，这就会导致程序考虑不需要考虑的东西，答案就更大了。

P5304 [GXOI/GZOI2019] 旅行者

P5304 [GXOI/GZOI2019] 旅行者。

建立超级源点和超级汇点。

然后需要找到超级源点到超级汇点的路径。

不能分治，因为分治太慢了，节点需要全部用满。

然后我们想到了二进制分组，就是进行 $\log$ 次，然后每一位相同的分在一起。这样不重不漏。

怎么更快？

换一个思路，枚举中间的点，然后看到他最近和他能到的最近的点凑成的路径。

两次 dij 可以完成。

P6880 [JOI 2020 Final] 奥运公交 / Olympic Bus

P6880 [JOI 2020 Final] 奥运公交 / Olympic Bus。

好好读题，是一开始就反转。

好像不是分层图，因为这次翻转对下次有影响。

暴力就是枚举每条边翻转，然后 dij。

我们发现没有必要，因为如果这条边不是最短路上必经的边直接做对答案没有任何影响。

枚举每一条边，如果不是 $1\to n$ 或者 $n\to 1$ 的必经边，就可以直接贡献答案。

如果是的话，需要反转了再 dij。

这样复杂度是正确的，dij 用 $n^2$ 的。

P2371 [国家集训队] 墨墨的等式

P2371 [国家集训队] 墨墨的等式。

经典的同余最短路模板题。

首先差分一下，$ask(r)-ask(l-1)$。

然后我们发现，我们可以先找出最小的 $a_i$，然后每一个可行的 $b_i$，$b_i+a_i$ 也可行，所以只需要找到最小的 $\bmod~a_i$ 是每一个值的就行了。

然后有一个很阴的 Hack，最小的 $a_1$ 是 $0$，可以选择最大的。

P9140 [THUPC 2023 初赛] 背包

P9140 [THUPC 2023 初赛] 背包。

同余最短路。

选择性价比最高的物品的体积来作为同余最短路的那个模数。

对于 $V1=V2 \pmod {mod}, V1<V2$ 的，需要比较 $\frac{V2-V1}{mod}\times w+W1$ 和 $W2$，相当于比较 $W-\lfloor \frac{V}{mod} \rfloor\times w$。

然后需要结合数据范围中 $V$ 很大来说明，因为只有这样，$V$ 的实际大小才没有影响。然后数据范围保证了 $V\le mod^2$，所以是可以的。

最后答案就是 $\lfloor \frac{qv}{v} \rfloor\times w+dis_v, v=qv \mod mod$。

Trick：为了防止负权边，而且解决要求的是最大路径的，还需要处理一下，$v_i*w-c_i*m$ 就是相对于最大的扣除的贡献（其中这个式子同时乘了 $m$），这个代价需要最小。

最后的结果：$k\times w+\frac{r\times w-dis_r}{m}=\frac{v\times w-dis_r}{m}$。

AT_arc084_b [ABC077D] Small Multiple

AT_arc084_b [ABC077D] Small Multiple。

编号怎么乱了？

如果这不放在图论里，我显然不会用图论做。

$f_i$ 表示对 $k$ 取模为 $i$ 的数位和的最小值。

就是同余最短路。

$f_{i*10}=f_{i}$ 和 $f_{i+1}=f_{i}+1$ 转移，相当于模拟数位进位，然后需要找到一个 $k$ 的倍数的。

01 bfs 会更快。

P7515 [省选联考 2021 A 卷] 矩阵游戏

P7515 [省选联考 2021 A 卷] 矩阵游戏。

不是，这玩意儿如果不是在图论里我绝对想不到图论。

首先，我们先当这不是个图论题。

稍微尝试一下就会发现题目最恶心的限制是 其每个元素为大小不超过 $10^6$ 的非负整数。

因为我们可以先瞎写出第一行和第一列的，然后后面的就可以直接确定了。

然后令现在的为 $a$ 数组。

我们需要调整 $a$ 数组，可以这样：

（不想写表格，ctj 不过分吧）

我们将限制条件写出来：

这还是没法做，但是这让人想起了差分约束。

然后换一下元，让 $x_i = (-1)^i \times c_i$，$y_i = (-1)^{i+1}\times d_i$。

P5905 【模板】全源最短路（Johnson）

P5905 【模板】全源最短路（Johnson）。

我们想用 dij，但是发现有负权边。

所以我们需要改一下形式，边权变成 $w+d_u-d_v$。（如果是 $w-d_u+d_v$ 需要反边，有点麻烦吧）

然后 $d$ 需要保证每一个 $w+d_u-d_v$ 都大于等于 $0$，我们发现这是三角形不等式，$w+d_u\ge d_v$，使用 SPFA 预处理。

然后就可以 dij 了，最后的 dis 需要 $-d_i+d_j$。

最小生成树

常见性质：

同一权值边的数量固定

对于任意一个带权无向图，其所有可能的最小生成树中，每种权值的边的数量是固定的，即由该权值的边组成的多重集合（考虑边权）在所有最小生成树中是完全相同的。

最小生成树是瓶颈生成树的充分不必要条件

无向图 $G$ 的瓶颈生成树是这样的一个生成树，它的最大的边权值在 $G$ 的所有生成树中最小。最小生成树是瓶颈生成树的充分不必要条件。

反证法，如果最小生成树的最大的边拆掉，换成瓶颈生成树中的一条将会得到更小的生成树。

P4208 [JSOI2008] 最小生成树计数

P4208 [JSOI2008] 最小生成树计数。

性质：对于任意一个带权无向图，其所有可能的最小生成树中，每种权值的边的数量是固定的，即由该权值的边组成的多重集合（考虑边权）在所有最小生成树中是完全相同的。

证明可以用 Kruscal 的过程证明。

还需要一个性质：

在处理完所有权值小于等于某个值 $w$ 的边后，图中顶点被分成的连通块（即哪些顶点在同一个连通分量中）在所有不同的最小生成树中是完全一致的。

如果不一致，那后面加的边一定没有前面优。

有了这两点性质，我们就可以做这道题了（不用矩阵树定理也行）。

CF888G Xor-MST

CF888G Xor-MST。

这道题是用 Boruvka 算法。Boruvka 大概是对于每一个联通块，找出离他最近的块连接，循环这个操作。

P5236 【模板】静态仙人掌

P5236 【模板】静态仙人掌。

这篇 tj 讲的还是很清楚的。

2-SAT

P5332 [JSOI2019] 精准预测

P5332 [JSOI2019] 精准预测。

这道题是 2-sat。

建边什么的还是比较模板的，就是二维，点 $(x,t)$ 表示 $x$ 在时间 $t$ 活着。

如果 $(x,t)$ 死了，那么 $(x,t+1)$ 也一定死。

还有就是预言，$0$ 的话 $\neg(x,t)\to \neg (y,t+1)$，$1$ 就是 $(x,t)\to \neg (y,t+1)$。

第一个问题：建不下图，因为点太多了，所以我们可以只保存有需要的，然后就可以了。至于 $t+1$ 就是离散化后找到下一个。

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

网络流问题中，给定一个有向图 $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

网络流。

问题本质

最小割本质上是一个 $0-1$ 整数规划问题。

问题的最终目标就是最小化：

$\sum c(i\to j)(x_i \operatorname{and }\neg j)$

$c$ 表示选 $i\to j$ 的代价，$x_i$ 表示 $i$ 是否在 $S$ 这边。

最大权闭合子图

给一个有向图，每个点有可正可负点权，要求选一个点的子集，点权和最大。有一些限制 $x\to y$ 表示 $x$ 选了则 $y$ 必须选。

首先，正的选了有代价，负的不选有代价。然后限制中的有无穷代价。

常见技巧&模型

• 无穷的边强制连接。

• 把一边的变量取反。

• 拆点常见用途：

  • 限制边权。
  • 表示不同状态，方便获取。

• 对于多选一的问题，可以用一条链，限制只能割一个点。

• 绞尽脑汁定义变量，例如 $[x_i\ge v]$。

• 选了有收获有代价的问题，收获连 S，代价连后面的。

• 方格特殊性质：可以弄成二分图，然后白点的变量表示是取了，黑点的表示是没取。

• 对于抽象点的问题纸上乱画画。。。

例题

P8215 [THUPC 2022 初赛] 分组作业

P8215 [THUPC 2022 初赛] 分组作业。 这道题的变量：是否选择愿意，是否选择合作。

• 不愿意 $\to$ 不合作，无穷的边。

• A 不合作 B 且愿意 有 $a_i$ 的代价。

• A 不愿意且 B 合作 有 $b_i$ 的代价。

• 愿意和队友不愿意 有 $e_i$ 的代价。

P14832 [THUPC 2026 初赛] Unpair Ampere

P14832 [THUPC 2026 初赛] Unpair Ampere。

连边技巧：看如果怎么样，就一定会怎么样，充分条件有什么。

技巧：为了防止多割，割的代价加上一个大常数，最后再减掉。

P2774 方格取数问题

P2774 方格取数问题。

方格有一个特殊性质，可以弄成二分图。

然后白点的变量表示是取了，黑点的表示是没取。

P6054 [RC-02] 开门大吉

P6054 [RC-02] 开门大吉。

跟 P3227 [HNOI2013] 切糕 差不多。有一个技巧，变量这样定义：$[x_i \ge v]$。

还是这个图：

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

这道题是多选一，就一条链，限制只能割一个点。

P2762 太空飞行计划问题

P2762 太空飞行计划问题。

P5934 [清华集训 2012] 最小生成树

P5934 [清华集训 2012] 最小生成树。

如果当前边可以放在最小生成树上，去除这个边，只保留比它小的，剩下图中 $(u,v)$ 不联通。

P5039 [SHOI2010] 最小生成树

P5039 [SHOI2010] 最小生成树。

跟上一道题有点像。

P4174 [NOI2006] 最大获利

P4174 [NOI2006] 最大获利。

AT_arc176_e [ARC176E] Max Vector

AT_arc176_e [ARC176E] Max Vector。

这道题我们可以通过最后的结果限制过程。

多选一还是用链来表示。

P12824 [NERC 2021] Kingdom Partition

P12824 [NERC 2021] Kingdom Partition。

代价有两倍，所以要建两条边，拆点实现。（这么逆天？）

P11531 [THUPC 2025 初赛] 检查站

P11531 [THUPC 2025 初赛] 检查站。

拆点可以限制每一个点的流量为 $1$。# 二分图

对于一张图 $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'$。

还有：

• 交错路：由匹配边与非匹配边交错而成的路径；

• 增广路：始于未匹配点且终于未匹配点的交错路．

利用定义解题

二分图的性质：没有奇环。

还可以用模板的匹配解决一些基础一点的问题。

时间复杂度（匈牙利算法）：$O(VE)$。

CF1537F Figure Fixing

CF1684G Euclid Guess

P2764 最小路径覆盖问题

CF1728F Fishermen

这是一个性质题，需要简化题目的问题，然后结合二分图可以找到左边字典序或者和最小的匹配方式。

CF1620F Bipartite Array

CF1620F Bipartite Array。

P1963 [NOI2009] 变换序列

P1963 [NOI2009] 变换序列。

图博弈

$A,B$ 两人在图上玩游戏。初始时，点 $x$ 有一颗棋子。A 先手，两人轮流移动棋子。

棋子每一步走一条边，且不能走到已经走过的点，不能移动就输了，谁会赢？

结论：如果途中存在一个最大匹配不含 $x$，则 $A$ 必败，否则 $A$ 必胜。（这个结论并不仅限于二分图。）

结论证明

先证明包含 $A$ 就必胜。如果所有的最大匹配都包含 $x$，$A$ 第一步会走到一个 $x$ 的匹配点，然后接下来 $B$ 只能走一个非匹配边，$A$ 接着又会有匹配边，循环往复。最后一定是 $B$ 走不动了，因为最后如果是非匹配边，一定有一种匹配是选择了这条边，因为这并不影响其他地方。

然后还需要向明不包含 $A$ 必败。如果 $x$ 不在最大匹配中，所以 $x$ 所有的邻居都是匹配点，结合上面的，$B$ 必胜，即 $A$ 必败。

模板题：P4055 [JSOI2009] 游戏

Konig 定理

定理内容

在二分图中：

$最大匹配 = 最小点覆盖$

证明

证明思路：找到显然的 $\ge$ 或 $\le$，然后证明 $=$ 成立。

常见结论

关于点匹配边

这个还是用 $\le$ 和 $\ge$ 证明。

关于边匹配点

若图不含孤立点，则

同理证明方法：

Dilworth 定理

$DAG 最长反链 = 最小可重链覆盖$

最长反链：最大的子集使得互相不可达。注意，这是集合！

最小可重链覆盖是指用最少的几条可重路径把图中所有顶点都覆盖至少一次。

证明

取走一个没有入度的点。

最长反链不变。则直接把这个点接回去。

最长反链也减了 1，则把这个点作为一个单独的链加入。

反正感性理解一下。

P4298 [CTSC2008] 祭祀

P4298 [CTSC2008] 祭祀。

CF1404E Bricks

二分图完美匹配与 Hall 定理

Hall 定理
对于二分图 $G = (X, Y, E)$，存在一个完美匹配当且仅当

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

使用归纳法证明，有点意思。

AT_arc106_e [ARC106E] Medals

AT_arc106_e [ARC106E] Medals。

首先是二分图建模，这道题相当于是天匹配人，把每个人拆成 $k$ 个，进行完美匹配，我们需要找到完美匹配。

由于是可行性，所以我们想到了 Hall 定理。

我们二分答案判断是否可行，判断的时候用 Hall 定理。

具体写法中 $f_i$ 表示出勤员工集合是 $i$ 的子集的天数，然后 mid-f[m-i] 表示连的边。

DFS 树

dfs 树就是 dfs 生成的树。

性质：没有横叉边。

所有叶子构成原图的独立集，因为叶子之间没有横叉边。

同深度的点也能构成独立集，这跟上面类似。

CF1470D Strange Housing

P5811 [IOI 2019] 景点划分

主要思想：拆分化简问题。

CF51F Caterpillar