网络流。

问题本质

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

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

∑c(i→j)(xiand⁡¬j)\sum c(i\to j)(x_i \operatorname{and }\neg j)

cc 表示选 i→ji\to j 的代价，xix_i 表示 ii 是否在 SS 这边。

最大权闭合子图

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

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

常见技巧&模型

  • 无穷的边强制连接。

  • 把一边的变量取反。

  • 拆点常见用途：

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

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

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

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

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

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

例题

P8215 [THUPC 2022 初赛] 分组作业

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

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

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

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

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

P14832 [THUPC 2026 初赛] Unpair Ampere

P14832 [THUPC 2026 初赛] Unpair Ampere。

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

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

设置必须变量->设置被动变量->有必要的时候对变量取反

首先想到的定义变量时发电厂是否转换。

我们发现这样做不了，因为不知道每个节点是否被火力/太阳能连接。

所以我们设置一个被动的变量，表示这个节点是否被火力/太阳能连接。

但是...这样好像有问题，同时被火力和太阳能连接不符合 x∧¬yx\land \neg y。

所以我们尝试反转太阳能节点。

还有就是“可能存在一些设施直接或间接地同时连接到”，所以我们需要保证贡献传播。

然后源点也要反转。源点我们时进行了拆点的。

定义不被太阳能连接时 x′x'。ss 表示源点不反转。

  • x→yx\to y，xx 如果被火力连接，yy 也必须，所以 (x,y,+∞)(x,y,+\infty)。

  • x→yx\to y，yy 不不被火力连接，xx 也要不不被火力连接，所以 (y′,x′,+∞)(y',x',+\infty)。

  • ss 就是不反转所以 xx 一定被火力连接，(s,x,+∞)(s,x,+\infty)。

  • ss 不是不反转所以 xx 一定被太阳能连接，(x′,s,+∞)(x',s,+\infty)。

  • xx 被火力连接且不不被太阳能连接，就要花 aia_i，(x,x′,ax)(x,x',a_x)。

为了防止一个电厂又是火电又是太阳能，就是两条边都被割掉了，所以我们需要给割边加上一个大常数，最后减去。

P2774 方格取数问题

P2774 方格取数问题。

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

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

P6054 [RC-02] 开门大吉

P6054 [RC-02] 开门大吉。

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

C++
还是这个图：

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

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

思路

就是个缝合。。。为什么非要求一遍期望 ai,ja_{i,j}。

然后有 (i,j)(i,j) 表示选手 ii 做第 jj 套题。

  • (i,j)→(i,j+1)(i,j)\to (i,j+1)，边权 ai,ja_{i,j}。

  • (j,p)→(i,p+k)(j,p)\to (i,p+k)，边权 +∞+\infty。

还有神秘剪枝：if(rest>inf)return inf;。

P2762 太空飞行计划问题

P2762 太空飞行计划问题。

思路

首先一些变量是这个仪器选不选。

但是问的是收益最大，我们看看哪些不行。

源点向实验连收益。实验需要向它所需的所有仪器连接 +∞+\infty 的边。仪器向汇点连价格。

然后怎么输出方案？

我们 dinic 最后一次检查中，会保存每一个点的 depdep，能到达的就是 S 集。

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

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

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

思路

其实是性质题。

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

最大生成树同理。

然后建两棵树，<L<L 的和 >L>L 的，然后分别跑 (u,v)(u,v) 之间的最小割。

P5039 [SHOI2010] 最小生成树

P5039 [SHOI2010] 最小生成树。

跟上一道题有点像。

思路

除了那条边全部减就是那条边加。

然后对最后答案的影响就是跟那条指定的边的大小关系。

注意这道题是保证。

P4174 [NOI2006] 最大获利

P4174 [NOI2006] 最大获利。

思路

跟这个 P2762 太空飞行计划问题 很像。

AT_arc176_e [ARC176E] Max Vector

AT_arc176_e [ARC176E] Max Vector。

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

多选一还是用链来表示。

思路

首先把 XiX_i 拆成长度为值域的链，YiY_i 也是。

然后我们建立虚拟点表示当前限制，每一个 ii 建立一个。我们需要防止 XiX_i 和 YiY_i 都小于 ai,ja_{i,j} 的情况，所以把 Y 反过来，然后链接 YiY_i 上 ai,ja_{i,j} 这个点和 XiX_i 上的。

P12824 [NERC 2021] Kingdom Partition

P12824 [NERC 2021] Kingdom Partition。

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

思路

然后列出两个表格：

STTSSSTT
ST2011
TS0211
SS1102
TT1120

对比题目要求的系数矩阵：

ABC
A201
B021
C110

然后 A-ST B-TS c-SS/TT。

P11531 [THUPC 2025 初赛] 检查站

P11531 [THUPC 2025 初赛] 检查站。

拆点可以限制每一个点的流量为 11。

P14885 [ICPC 2019 Yokohama R] Draw in Straight Lines

P14885 [ICPC 2019 Yokohama R] Draw in Straight Lines。

找到性质->设置变量。

关于 ax+bax+b 的构造：一条链，一个点连向下一个点 bb，然后 ss 指向每个点 aa，如果是选取一段的话需要一个 bb 和长度个 aa。

思路

首先，这道题我们需要找到性质。我们发现一个点肯定是横纵最多一次的。

然后我们考虑最小割，先设置变量：

这个点横着是否被覆盖了黑色，横着是否没有被覆盖白色，竖着是否被覆盖了黑色，竖着是否没有被覆盖白色。

如果是黑色点：(x,y,2)(x,y,2) 到 tt 和 ss 到 (x,y,3)(x,y,3) 必须连接 +∞+\infty 的边。(x,y,4)(x,y,4) 连向 (x,y,1)(x,y,1) 的边需要单点覆盖的权值。

如果是白色点：(x,y,4)(x,y,4) 和 (x,y,1)(x,y,1) 必须连接 +∞+\infty 的边。(x,y,3)(x,y,3) 和 (x,y,1)(x,y,1) 与 (x,y,4)(x,y,4) 和 (x,y,2)(x,y,2) 需要单点覆盖的权值。

然后关于边的话，就 s/ts/t 连向每个点，然后有一条横/竖的链，选取一段刚好需要 al+bal+b。