专栏文章

暑假专题9 二分图匹配与网络流应用

__Cheems
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miocuycf
此快照首次捕获于
2025/12/02 17:07
3 个月前
此快照最后确认于
2025/12/02 17:07
3 个月前
查看原文

Hall 定理

二分图左右部点集合为 L,RL,R，LL 有完美匹配等价于 ∀S∈L,∣S∣≤∣N(S)∣\forall S\in L,|S|\le |N(S)|，N(S)N(S) 为与 SS 相连的点集。
推广：二分图最大匹配为 ∣L∣−max⁡(∣S∣−∣N(S)∣)|L|-\max(|S|-|N(S)|)。
证明：原式 =min⁡(∣L∣−∣S∣+∣N(S)∣)=\min(|L|-|S|+|N(S)|)。如下图：
发现等价于求最小点覆盖。因为可视为枚举左部 SS 不选而 L−SL-S 选，那么 N(S)N(S) 必选。

一般图完美匹配：Tutte定理

一般图有完美匹配当且仅当 2∣n2\mid n 且 ∀S,odd(A−S)≤∣S∣\forall S,odd(A-S)\le |S|，其中 odd(S)odd(S) 表示 SS 构成的所有连通块中奇连通块个数。
推论：记 def(S)=odd(A−S)−∣S∣def(S)=odd(A-S)-|S|，则最大匹配为 n−max⁡def(S)2\frac {n-\max def(S)}2。
证明：我们将直接证明推论，考虑 SS 为取到 defdef 最大值且点数最多的连通块，将其去掉后得到若干连通块 H1…HmH_1\dots H_m。
引理 1：HH 中不可能有奇连通块。
对于一个偶连通块，将其中任意一个点加入 SS 后 odd(S)odd(S) 至少加一，所以 defdef 不降，不符定义，矛盾。
引理 2：任意 HiH_i 去掉任意一点后它存在完美匹配。
记它为 Hi−vH_i-v。考虑归纳证明，只需证明 Hi−vH_i-v 满足 Tutte 定理的条件。考虑 T∈Hi−vT\in H_i-v，推一下式子勾连原图：
odd(Hi−v−T)=odd(A−S−T−v)−(odd(S)−1)odd(H_i-v-T)=odd(A-S-T-v)-(odd(S)-1)
defHi−v(T)=odd(A−S−T−v)−odd(A−S)+1−∣S∣def_{H_i-v}(T)=odd(A-S-T-v)-odd(A-S)+1-|S|
defHi−v(T)+∣T∣=defA(S+T+v)+∣S∣+∣T∣+1−(defA(S)+∣S∣)+1def_{H_i-v}(T)+|T|=def_{A}(S+T+v)+|S|+|T|+1-(def_{A}(S)+|S|)+1
defHi−v(T)=defA(S+T+v)−defA(S)+2def_{H_i-v}(T)=def_A(S+T+v)-def_A(S)+2
根据定义有 defA(S+T+v)<defA(S)def_A(S+T+v)<def_A(S)，所以 defHi−v(T)<1def_{H_i-v}(T)<1。只要能证明左式为偶即可。分讨：
  • 2∣∣T∣2\mid |T|：2∣∣Hi−v−T∣2\mid |H_i-v-T|，故 2∣odd(Hi−v−T)2\mid odd(H_i-v-T)。
  • 2∤∣T∣2\nmid |T|：同上 2∤odd(Hi−v−T)2\nmid odd(H_i-v-T)。
得证。
引理 3：将 SS 视为左部点，HiH_i 视为右部点，左部点存在完美匹配。
考虑 Hall 定理。考虑 T,N(T)T,N(T) 构成的经典结构（T∈S,N(T)∈HT\in S,N(T)\in H）。推式子找与 defdef 的联系，由于 H−N(T)H-N(T) 的奇连通块被 A−TA-T 包括了，放缩一下：
defA(S−T)≥m−N(T)−∣S−T∣def_A(S-T)\ge m-N(T)-|S-T|
根据定义：
defA(S−T)≤defA(S)=m−∣S∣def_A(S-T)\le def_A(S)=m-|S|
∣N(T)∣−∣T∣=(m−(m−∣N(T)∣))+(∣S∣−(∣S∣−∣T∣))|N(T)|-|T|=(m-(m-|N(T)|))+(|S|-(|S|-|T|))
=m−∣S∣−(m−N(T)−∣S−T∣)=m-|S|-(m-N(T)-|S-T|)
≥defA(S)−defA(S−T)\ge def_A(S)-def_A(S-T)
≥0\ge 0
得证。
所以，只需按照引理 3 做完美匹配，那么由引理 2，被匹配的 HH 的剩下的点也能有完美匹配。最后剩下一些无法匹配的只能扣掉一个点。显然是最优的。此时，剩下的未匹配点个数恰为 oddA(S)−∣S∣odd_A(S)-|S|，证毕。结合图像理解下：

最小割相关补充

对于任意一组割，记 S,TS,T 分别为方案中与 s,ts,t 连通的点集。
∑u∈S,v∈Tc(u,v)≥∑u∈S,v∈Tf(u,v)=w\sum\limits_{u\in S,v\in T} c(u,v)\ge \sum\limits_{u\in S,v\in T} f(u,v)=w
ww 是最大流。关于等号为什么有，因为考虑其中一个流量，它会从 SS 出发，从 SS 走到 TT 产生 11 贡献、反之 −1-1 贡献。最终走到 TT 所以恰为 11 贡献。
由此可知最小割的边必然满足满流。然后我们考虑一下此时残量网络的结构，首先最大流 >0>0 所以 t→st\to s，而且不存在增广路因此 ss 不能到 tt。即缩点后为 t→st\to s 的 DAG。
可行边判定：满流；同时残量网络中 uu 不能走到 vv，等价于 sccu≠sccvscc_u\ne scc_v。
必经边判定：是可行边，且 sccu=sccs,sccv=scctscc_u=scc_s,scc_v=scc_t。因为只可能 (u,v)(u,v) 在 s,ts,t 的 sccscc 间才能做到改变它就改变最大流。
最小割方案：残量网络上令 ss 所在 sccscc（也就是 ss 能走到的点）为 SS，其余为 TT。不难验证。

最小割常见模型

  • 二元关系建图：有若干 0/10/1 变量，当 x=1,y=0x=1,y=0 产生贡献等等。
  • 分层图的割建图：可用于刻画覆盖所有转移路径等。例如 LIS。
  • 最大权闭合子图：建超级源汇，SS 连向正权点、容量为点权，负权点连向 TT、容量为点权相反数，原图的边权均为 infinf。构造方案考虑最小割，若 S→iS\to i 割了代表不取 ii、i→Ti\to T 割了代表取 ii。
  • 最小割中割掉一点却可能代表取这个点，所以要灵活。

平面图割与对偶图路径的转化

首先由对偶图环对应平面图割集，不难想象。但这是不便利用的。
做如下构造：原图中，将 s,ts,t 连边（一般来说画在原图很外面，可以画成几条无限延伸的射线），那么得到一个新的面，令它为对偶图上的起点 s′s^\prime，无限面为中终点 t′t^\prime，忽略刚才 s,ts,t 连边对应的边。
则此时，s′→t′s^\prime\to t^\prime 的简单路径对应平面图上 s,ts,t 一组简单割（不存在点同时与 s,ts,t 分隔），路径长度即为割边数量，所以平面图最小割对应对偶图最短路径。
证明容易，加上 s,ts,t 连边（即 s′→t′s^\prime\to t^\prime 连边）后构成了环，环将 s,ts,t 分开，便对应原来 s,ts,t 割。

CF1178H Stock Exchange

link
第一问：股票的转换相对独立，考虑转换过程。一个重要的观察是，一只股票除 00 时刻和最后一次变换的时刻外产生的变换，都是不必要的。证明考虑 00 时刻往后 kk 时刻第一次变换，记原来股票 xx、变成 yy，那么 fk(x)≥fk(y)f_k(x)\ge f_k(y)，发现若 f0(x)<f0(y)f_0(x)< f_0(y) 则 ∀p>k,fp(x)>fp(y)\forall p>k,f_p(x)>f_p(y)，也就是价值更低不必换了。所以想到二分答案 midmid，由结论只会在 0,mid0,mid 时刻变换，便能求出每只股票最终可得的股票为一个前缀，由 Hall 定理知判定条件为排序后 i≥preii\ge pre_i。O(nlog⁡n)O(n\log n)。
第二问：网络流建模是容易的，只会产生两次变换，每次变换的建边可用前缀优化，边数线性了。O(n2log⁡n)O(n^2\log n)

CF708D Incorrect Flow

link
考虑先不管 f≤cf\le c 的限制，那么很像上下界流，只需建立超级源汇 S,TS,T，若流进来的不够就向 TT 连对应流量的边，反之同理。跑最大流即可。
接下来刻画 f≤cf\le c 的限制和修改，除了 f≥cf\ge c 时 ff 变大要花费 22 以外花费都是 11，分讨一下：
  • f≤cf\le c：u→vu\to v 先有 c−fc-f 容量、花费 11，然后 infinf 容量、花费 22。
  • f>cf> c：无论如何必须花 c−fc-f 代价使得 c=fc=f，先提前计算。然后 v→uv\to u 有 f−cf-c 容量花费 00，此后 v→uv\to u 容量 cc 花费 11，u→vu\to v 容量 infinf 花费 22。
对于边的最优修改显然不会又增又减的，所以上面这种对增减分开处理的方法是正确的。跑 MCMF 即可。

CF103E Buying Sets

link
子集视为左部点，元素视为右部点，子集向包含的元素连边。子集的并的大小不小于子集，即为满足 Hall 定理。
如何利用完美匹配来刻画子集数量恰为它的并？考虑最小权闭合子图，原来的边左往右连，并跑出来一组完美匹配让右往左连，答案即为最小权闭合子图。
证明：显然最小权闭合子图左右部点数相同；考虑某个合法方案中存在右部点满足其对应（完美匹配）的左部点没被选，那么它会被另一个左部点选，同时这个左部点本身也对应一个右部点，接下来容易发现左右部点数量不可能相同。
也存在补集转化最小割的构造方法。

P3488 [POI 2009] LYZ-Ice Skates

link
之前做过。建二分图，用 Hall 定理判定 max(k∣N(S)∣−∣S∣)≤0max(k|N(S)| - |S|)\le 0，那么假如两个人 x<yx<y 满足 x+d≥yx+d\ge y，那么显然把 [x,y][x,y] 都选上更优。所以形如若干个 N(S)N(S) 互不相交连续段，只需知道正负即可，所以只需考虑一个连续段的情况。维护个最大子段和即可。
启示：一些复杂问题，利用 Hall 定理转化再加上一些最优化分析，往往可以得到简洁优美的结构。

CF981F Round Marriage

link
显然二分答案，然后每个点匹配的是环上一段。破环成链。同上，N(S)N(S) 相交的话可以把中间的都取了，所以形如若干不相交的连续段，然后考虑一段即可。

P8484 「HGOI-1」Mole

link
考虑费用流建图，SS 连向地鼠，地鼠可以被打多次所以需要复制多个代表不同代价，由于代价递减所以一只地鼠不会出现非前缀的情况。然后地鼠连向对应的区间、区间再连向 TT：
考虑滑动窗口，每次右边新增一个地鼠和区间。动态加点的情况下需依次考虑：消负环、跑增广。
考虑上述过程，注意到将一个区间向 TT 的边退流是没有意义的，因为之后这条边也会满流。
接下来继续模拟费用流感觉没有前途，因为增广路形态太多了，回归原问题。但是根据上面的讨论，不会出现地鼠被锤的次数变少的情况。
每次找到可以被锤的地鼠中贡献最大的，锤他。刻画“可以被锤”，点对区间的形式联想到前面几题，利用 Hall 定理。记 aia_i 为被锤次数，当前考虑到区间 [x−m+1,x][x-m+1,x]，合法当且仅当每个区间 [l,r][l,r] 满足 ∑i∈[l,r]ai≤min⁡(r+m−1,x)−max⁡(l,m)+1\sum\limits_{i\in [l,r]} a_i\le \min(r+m-1,x)-\max(l,m)+1，考虑分讨去掉 min⁡,max⁡\min,\max：
  • 首先，假如 l<ml< m 不妨直接取 l=1l=1、r≥x−m+1r\ge x-m+1 不妨直接取 r=xr=x。
  • l=1,r=xl=1,r=x：sum(1,x)≤x−m+1sum(1,x)\le x-m+1，由于 sum(1,x−1)≤x−msum(1,x-1)\le x-m，而 axa_x 新来不可能 >1>1，所以一定合法。
  • l≥m,r=xl\ge m,r=x：同上。
  • l=1,r≤x−ml=1,r\le x-m：sum(1,r)≤rsum(1,r)\le r。
  • l≥m,r≤x−ml\ge m,r\le x-m：sum(l,r)≤r+m−lsum(l,r)\le r+m-l。
对于后两种，考虑这样的过程：将取等号的极大区间标记，每次取未被标记的最大 hh。
每次只需考虑 r=x−mr=x-m 即可。不对啊？！之后要是 aa 变化了就有可能出现原本 << 号变成 == 号。

事实证明，存在这样的 hack！群友找到了，群友神力！

fishpear：我没实现这个做法。

P9528 [JOISC 2022] 蚂蚁与方糖

link
运用 Hall 定理推论，求 max⁡(∣S∣−∣N(S)∣)\max(|S|-|N(S)|)。我们还想套用之前题面的套路，不过因为不是简单判定正负的原因，可能会选多个连续段。但是，这些连续段对应的 N(S)N(S) 肯定不交。
没办法，考虑 dp，但是带修改，而矩阵优化也不现实，所以考虑放到权值线段树上。那么记 fu,0/1,0/1f_{u,0/1,0/1} 表示考虑连续段在 uu 对应的区间 [l,r][l,r] 上，且对应的 N(S)N(S) 的左端点（右端点）是否越过 ll（rr）。转移时假如是 flson,0/1,1,frson,1,0/1f_{lson,0/1,1},f_{rson,1,0/1} 才可能出现 N(S)N(S) 相交的情况，由先前结论假如相交时左右拼起来还存在间隙，那么肯定不优，所以只需加上 sum(mid+1−L,mid+L)sum(mid+1-L,mid+L)（区间糖果数）即可。这个东西顺便维护一下即可。
考虑修改，假如是蚂蚁修改好做，逐次 push_up 更新 ff 即可。但是糖果修改会对 [x−L,x+L][x-L,x+L] 的蚂蚁都产生修改，这相当于对动态 dp 做区间修改！
真的能做吗？可以的兄弟，可以的。因为一般来说动态 dp 只能依靠 push_up 来更新，但是本题的问题相对简单可以计算影响。
对于 ff 是容易的，因为 [x−L,x+L][x-L,x+L] 内的区间，只要选了蚂蚁这些糖果就会被计入 ∣N(S)∣|N(S)| 中，所以 f←max⁡(0,f−cnt)f\gets \max(0,f-cnt)，打个标记即可。
不过对于 sumsum 需对节点可能的影响进行分讨。能影响等价于 x−L≤mid≤x+L−1x-L\le mid\le x+L-1，那么 [x−L,x+L][x-L,x+L] 内的区间都会 sum←sum+cntsum\gets sum + cnt 打个标记就好；而拆出来的 O(log⁡n)O(\log n) 个区间的祖先也可能被影响，在 push_up 前处理一下即可。细节：一般线段树 mid<rmid<r，所以上面的也可以看作 mid≤x+Lmid\le x+L 可以与 ff 一起处理。
O(nlog⁡n)O(n\log n)。
启示：这题的转化很典，这种左部点对应一个定长区间的问题一般转化为若干 N(S)N(S) 不交连续段。后面的动态 dp 也不难想（可能就转移对中间相交的处理有点难），但是对动态 dp 区间修改太神了，完全没见过。所以不要先入为主地误认某些问题不可做。

AT_arc190_e [ARC190E] Gaps of 1 or 2

link
考虑建模，考虑 nn 列第 ii 列有 aia_i 个数，距离 ≤2\le 2 的两列的点都有连边，求最大匹配。
考虑 Tutte 定理，选个 SS，最大化 odd(A−S)−∣S∣odd(A-S)-|S|。
考虑无用情况。发现对于一列，若选了点但是不全选非常亏，因为考虑一列选的点逐渐变多但是不选完，那么连通块个数不会变化只是说有一个连通块奇偶性变化。可是 ∣S∣|S| 稳定 −1-1，显然是亏的。
于是一列要么全选要么不选，已经可以 dp 了。有剪枝，注意到 010010 即一列选但相邻都不选是亏的，因为相邻两列还是可以跨过它连边，那不选这列不劣。于是，存在最优解满足没有跨过一列的边，连通块必然是 00 连续段，减少了状态数以及转移难度。
只需 55 种状态，然后矩阵乘法做区间查询即可。注意 010010 不会被最优性过滤，需手动判定。
启示：一般图的最大匹配可以用 Tutte 定理转化，这东西第一次见捏。

P3308 [SDOI2014] LIS

link
LIS 问题有关的一般考虑按 dp 值分层。利用这个建出分层图，相邻层有连边，再让 SS 连向第一层、最后一层连向 TT，那么一个 LIS 对应一条 S→TS\to T 路径。那么就要割掉一些点使得不存在路径，所以点拆为边跑最小割即可。
字典序很难直接刻画，考虑按 cc 从 11 到 nn 看看能不能割掉。相当于是最小割中的可行边，如果是才把它割掉，之后重新跑一遍最小割，以此类推。
启示：这题是典型的分层图最小割建图，并运用可行边相关知识。

P3756 [CQOI2017] 老C的方块

link
观察：所有情况形如一个蓝边两边分别放置一个 1×21\times 2 的矩形，且这恰为所有情况。
矩形可用连边刻画，只需让相邻点连边即可。由此我们得知本题大概框架：建分层图跑最小割。本题应分为 44 层，每层向下一层有边。
考虑染色代表层数，考虑如何染色（建议画图）：
  • 相邻格子必然是相邻颜色。
  • 考虑“田”与“L”型，那么它们有三个格子是共用的，则第四个格子颜色相同。即每条竖线右侧与右下方颜色相同。
  • 考虑“一”型，可知水平方向上四个相邻格子颜色互不相同。
由此便能推出四列的染色方案：
拓展两列也是容易的，相当于沿着边线水平翻转一次即可，那就做完了。
启示：感觉本题不难，联想到形如两个矩形通过蓝边连接后，再手玩几下就没了。但更理性一些的思考应为：分层图路径刻画非法 pattern、构造染色方案、观察特点减少枚举量。

TCO13 Semifinal2 OneBlack

link，topcoder 上的题目
题意：有一个 n×nn\times n 的网格，每个点可能是障碍和空地，求将空地黑白染色的方案，使得任意左上到右下的路径（向下或向右），经过恰好一个黑色格子。n,m≤30n,m\le 30。
原题做法为 dp 套 dp，状态优化后才能过。事实上可以 n,m≤1000n,m\le 1000。
考虑用割刻画，染黑视为割掉一个点。首先点转边，然后向右向下连边。左上入点、右下出点为源汇，一个简单割集（任意点与 s,ts,t 至少一点连通）能够保证恰好经过一个黑色格子，考虑路径对应一个流量，本题建模不带环，故它恰有一次从 SS 集到 TT 集的转变。
考虑平面图割转对偶图路径。形如下图：
那么对偶图中，点为格子四个顶点，每个格子左下到右上有连边，边界除外。而障碍物相当于删掉一个点向外界的连边，最终会构成若干连通块，所以可视为将四个角的点合并。并查集维护即可。O(nm)O(nm)，瓶颈为并查集。
注意特殊情况，上面默认建模出来个连通图，但可能存在空地但是不被任意路径经过，将其视为障碍，答案 ×2\times 2 即可。

AT_arc106_e [ARC106E] Medals

link
做过，二分答案，然后最link小割或者 Hall 定理都行，最后 sosdp。

AT_abc332_g [ABC332G] Not Too Many Balls

link
建模按题意模拟即可。最大流转最小割，这个图结构简单就上下两排，可以考虑直接计算割集。枚举 AA 为球这一排与 ss 连通的，BB 为箱子这一排与 tt 连通的，答案为：
min⁡(∑i∉Aai+∑i∉Bbi+∑i∈Ai∑i∈Bi)\min(\sum\limits_{i\notin A}a_i+\sum\limits_{i\notin B}b_i+\sum\limits_{i\in A} i\sum\limits_{i\in B} i)
为二元项加一元项，难以直接计算。nn 较小，考虑枚举 ∑i∈Ai=k\sum\limits_{i\in A}i=k，那么 ∑i∉Aai\sum\limits_{i\notin A}a_i 背包即可，bb 有关项发现等价于 ∑min⁡(bi,ki)\sum \min(b_i,k_i)，相当于分段函数（每个只有两段）叠加，差分维护一下即可。

CF1919F2 Wine Factory (Hard Version)

相当于求下图最大流：
转最小割。枚举每个点属于 S,TS,T 集，为 pi=0/1p_i=0/1，那么 pi=0/1p_i=0/1 分别产生 bi/aib_i/a_i 代价，同时相邻 01/1001/10 会产生 cic_i 代价。
又看到单点修改，想到放线段树上 dp。记 fu,0/1,0/1f_{u,0/1,0/1} 为 uu 代表的区间左右为 0/10/1 即可。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...