基础知识

网络流

这里不赘述定义，详情查看 OI-Wiki。

最大流

这里简单记录一下求最大流的两种算法：

Edmonds–Karp (EK)：

尝试从 $s$ bfs 到 $t$ 找到新的增广路，并记录路上剩余容量的最小值 $\Delta$ 。随后让路径上的边加上 $\Delta$ 的流量，反向边退掉 $\Delta$ 的流量，直到无法找到新的增广路为止。

时间复杂度 $O(VE^2)$，这里不进行证明。

Dinic：

首先使用 bfs 对当前图进行分层，记录层数为 $l_i$，暂时去掉 $(u,v)\ (l_u+1\ne l_v)$ 的边，之后并使用 dfs 寻找极大增广流（阻塞流），并将阻塞流并入原图中，直到无法分层为止。

时间复杂度 $O(V^2E)$，这里不进行证明。

二分图

这里不赘述定义，详情查看 OI-Wiki。

二分图最大匹配

Kuhn算法：

我们枚举每一个左侧点，并尝试进行配对。枚举左侧点的所有右侧点，如果这个右侧点有匹配，则尝试让此右侧点的匹配点继续匹配，直到此右侧点空出，与枚举的左侧点匹配。若所有枚举的右侧点无法空出，则舍弃这个左侧点。

本质上，这就是在交错路上寻找增广路的过程¹。

时间复杂度 $O(VE)$。

二分图最大权匹配

匈牙利算法 (KM 算法)：

首先我们将原图中少的那一部分点补齐，使两遍的点数相等。并连接所有的边，原本不存在的赋值为 0。这样我们就将问题转换为了二分图最大权完美匹配。

我们称一个点的可行顶标 $l_i$ 为使得所有边 $(u,v)$ ，使得 $w_{u,v}\le l_u+l_v$ 。

我们称此图的相等子图为所有使得 $w_{u,v} = l_u+l_v$ 的边及所有点组成的子图。

此处给出一个定理：对于某组可行顶标，如果其相等子图存在完美匹配，那么，该匹配就是原二分图的最大权完美匹配²。

那么我们只需要通过调整顶标来找到相等子图的完美匹配即可。

算法的具体过程这里就不写了，太长了³，依旧查阅 OI-Wiki 。

费用流⁴：

设置虚拟源汇点 s，t。s 向左侧点连容量为 1 ，费用为 0 的边，所有点⁵向 t 连容量为 1，费用为 0 的边。然后保留中间二分图的边，容量为 1 ，费用为原费用。跑最大费用最大流即可。

题单链接 ZR 2026 Summer C 8.12 ZR 2026 Summer C 8.13

匹配 (洛谷-P3967)

首先对原图跑一个二分图最大权匹配，并记下所有的匹配边。

随后枚举每一条匹配边，删除后重新跑匹配。若权值减少了，说明这个边不能删。否则可以删。

Shoot the Bullet | 东方文花帖 (洛谷-P5192)

回旋镖终于是打回来了吗…

考虑图论建模，将原题转换为有源汇上下界最大流。建立虚拟源点 s 与汇点 t，建立编号 $1\sim n$ 的点作为每一天，编号为 $n+1\sim n+m$ 的点作为每个少女，源点到每天连上下界为 $[0,D_i]$ 的边，每天到对应的 $C_i$ 个少女，上下界为给定的 $[L,R]$ ，每个少女连接汇点上下界为 $[G_i,+\infin]$ 的边即可。

方格取数问题 (洛谷-P2774)

我们对原图中的方格进行分组，通过横纵坐标之和的奇偶分为两组，并将原图上一个方格的 4 个相邻方格连上容量为无穷的边，一组连接源点，一组连接汇点，容量为原点权，跑最大流即可。

1. 关于交错路和增广路，详见OI-Wiki ↩︎
2. OI-Wiki 上给出了详细的证明，但是信息竞赛不需要证明 ↩︎
3. 大概率是作者比较懒 ↩︎
4. 可以理解为邪修，但是很好用的 ↩︎
5. 需要保证最大流量与左侧点数量相同 ↩︎