lessons/课程/07-二分图/03-带权匹配与二分网络流.md

带权二分匹配与二分网络流

本节目标

学完后，你应能区分“最大匹配数”“完美匹配最大权”和“带容量的多次配对”，理解 KM/Hungarian 的顶标对偶，并把可重复消耗的二分关系建成最大流。

前置知识与课前自测

前置：二分匹配、最短路松弛思想、最大流基本定义、质因数分解。

1. 最大权完美匹配能否按边权从大到小贪心？
2. 一个左点可提供 5 份资源、右点可接收 3 份时，普通匹配的一点一次模型还适用吗？
3. 公因数操作中选择合数 $v$，为什么通常不如拆成若干次质数操作？

自测答案

1. 不能，早选一条大边可能迫使剩余点使用极差边。 2. 不适用，应把资源量作为容量，用网络流而非复制大量点。 3. 合数一次同时消耗多个质因子；逐个质因子操作合法且操作次数更多或相等。

问题动机与核心知识

最大权完美匹配的线性规划对偶可理解为给左右点顶标 $l_x,l_y$，始终保持

$$ l_x+ly\ge w{xy}. $$

等号边构成“相等子图”。若其中能找到完美匹配，匹配权和等于顶标和，达到对偶上界，必最优；否则根据未访问右点的最小松弛量调整顶标，产生新的等号边。这就是 KM（Kuhn–Munkres）/Hungarian 的核心，而不是“带权版 DFS”一句话。

当点能被使用多次，容量网络更自然：源到左点是供给，右点到汇是需求，中间边表示允许流动。整数容量最大流的整数性自动给出离散操作次数。

实现指南

• KM 求最大权时左顶标初始化为该行最大边权，右顶标为 0。
• 每次增广失败，用未访问右点最小 slack 调整；slack 必须在 DFS 中持续更新。
• 最大流边要同时建反向残量边；Dinic 的层次图只沿剩余容量正且层数 +1 的边。
• 多个质因子子问题互相独立时分别建流图，避免把不同资源错误混流。

精选例题 1：奔小康赚大钱

来源信息与题意

• VJudge：HDU-2255 奔小康赚大钱
• 原来源：HDOJ 2008 Summer Exercise
• 大致难度：KM 模板建立；考点：最大权完美匹配

多组数据，$n\le300$ 户村民与 $n$ 间房，每户对每间房给一个出价。每户恰得一房、每房恰给一户，最大化总收入。

Hint 1

村民为左点、房屋为右点，目标是最大权完美匹配。

Hint 2

维护可行顶标 `lx[x]+ly[y]>=weight[x][y]`，只在等号边上增广。

Hint 3

增广失败时按最小 slack 调整，让至少一条新边变成等号边。

Observations、Editorial 与证明

初始化 lx[x]=max_y w[x][y]，保证顶标可行。为每个左点在等号子图找增广路；失败时，已访问左点减 delta，已访问右点加 delta，其他右点 slack 减 delta。已匹配等号边仍等号，所有不等式仍可行，并至少新增一条等号边。

获得完美匹配后，每条匹配边为等号，匹配权和等于全部顶标和；任何匹配权和不超过该对偶上界，所以最优。复杂度 $O(n^3)$，空间 $O(n^2)$。

核心伪代码与参考实现附件

initialize left label lx[x] = max_y weight[x][y], right label ly = 0
for every left vertex root:
    search an augmenting path using only equality edges lx+ly == weight
    if search fails:
        delta = minimum slack of every unvisited right vertex
        subtract delta from visited lx; add it to visited ly; update slack
    repeat until root is matched
output weight sum of the perfect matching

完整 GNU C++17 参考实现见附件：HDU-2255.cpp

复盘与变式

若左右点数不同或允许不匹配，可补虚拟点和零权边，但负权场景要确认“宁可不选”与补边权值是否一致。

精选例题 2：Array and Operations

来源信息与题意

• VJudge：CodeForces-498C Array and Operations
• 原题：Codeforces Round 284 (Div. 1)
• 难度：2100；考点：按质因子拆分、奇偶下标二分图、最大流

$n,m\le100$，数组 $a_i\le10^9$。每个允许对 $(i,j)$ 满足 $i+j$ 为奇数。一次可选允许对和公因数 $v>1$，同时把两数除以 $v$；同一对可多次用。求最多操作数。

Hint 1

最优操作只需取质数；合数可拆成多次质数操作。

Hint 2

对每个质数独立考虑，各点可供给/消耗的数量是该质数指数。

Hint 3

奇下标放左侧、偶下标放右侧；源到左容量为指数，右到汇容量为指数，允许对连无穷容量边。

Observations、Editorial 与证明

每次质数 $p$ 操作消耗允许对两端各一个 $p$。对固定 $p$，这是把奇侧指数单位经允许边匹配到偶侧指数单位，最大次数等于容量网络最大流。不同质数的指数资源互不影响，总答案为各质数最大流之和。

任一原操作可拆成其质因子的若干合法操作，故存在只用质数且不更差的最优解；流的每个整数单位对应一次该质数操作，反向也成立。质因子种类很少，每次 Dinic 图仅百点百边，规模充分可行。

核心伪代码与参考实现附件

factor all array values and iterate over each distinct prime p
capacity[i] = exponent of p in a[i]
build flow network: source->odd indices, even indices->sink
for every allowed pair add infinite-capacity odd->even edge
answer += maximum_flow(network)
output answer

完整 GNU C++17 参考实现见附件：CodeForces-498C.cpp

复盘与变式

若允许对不保证下标奇偶不同，关系图可能不是二分图，这个单向容量模型失效；需要重新分析资源在一般图上的配对。

灵活性训练：Buying Sets

CodeForces-103E Buying Sets（2900）显式给出 Hall 条件，却要求找“集合数 = 并集元素数”的最小价格子集。它适合训练把 Hall 紧集、负价格选择与最小割联系起来；与本章只有部分相关，作为灵活性题，不作为后续课程前置。

扩展与联系

• 一般带权、非完美匹配可用最小费用最大流统一处理，但复杂度通常高于专门的 Hungarian。
• 顶标是对偶可行解；“原始方案权 = 对偶上界”是最优性证书。
• 二分网络中的最小割还能恢复最小点覆盖，连接上一节 Kőnig 构造。

总结与自检

1. KM 顶标不等式代表什么上界？
2. 调整顶标时为何不会破坏已有等号匹配边？
3. 容量网络的整数流怎样映射回离散操作？
4. 质因子子问题为什么可以独立求和？

课后训练建议

先用排列枚举对拍 $n\le8$ 的 KM；再对固定质数手画源—奇点—偶点—汇网络。Array and Operations 调试时逐质数打印指数总供给、总需求和流量上界。最后只阅读 Buying Sets 的题面，尝试指出 Hall 条件在何处给出可行性结构。