04-高阶扩展-关联图中的最大森林.md 4.7 KB
高阶扩展：从彩虹环到关联图最大生成森林
本节目标
把“每个集合内部产生同色团”的彩虹环条件，转写成集合—元素二分关联图中的普通环；再把最小删除代价取补，变成最大权森林。
前置知识与课前自测
前置：DSU、Kruskal、二分关联图。
- 一个集合节点连接多个元素节点时，两条关联边能代表原图中的什么？
- 二分关联图的一条交替环怎样投影成原图彩虹环？
- 最小删除权与最大保留权如何互补？
答案
1. 两元素间一条颜色为该集合编号的边。 2. 每经过一个集合节点，就在它相邻的两个元素间取一条该颜色边；环上集合节点互异时颜色互异。 3. 删除权等于全部权减保留权。问题动机
每个集合在原图中展开成同色团，显式边数可能平方级；而“彩虹”限制又要求记住边来自哪个集合。把集合升格为节点，可以同时压缩团并保留颜色身份。
精选例题：Avoid Rainbow Cycles
来源与题意
- VJudge：CodeForces-1408E
- 原题：Codeforces 1408E
- 难度：2400；考点：关联图、环的等价转化、最大生成森林
有 $m,n\le10^5$，集合 $A_i\subseteq[1,n]$，总出现次数不超过 $2\times10^5$。保留元素 $j\in A_i$ 后，集合内任意两保留元素间都有一条颜色 $i$ 的边；删除该出现需付 $a_i+b_j$。求使图中没有边颜色互异的彩虹环的最小代价。
Hint 1
建立左侧集合 $i$、右侧元素 $j$ 的二分图，每次出现是一条权为 $a_i+b_j$ 的边。Hint 2
保留的关联边若成环，环中集合点与元素点交替；把每个集合点两侧的元素直接相连。Hint 3
反过来，彩虹环的每条颜色选择其集合点，可得到不重复集合点的关联闭合游走，并抽出一个环。Hint 4
因此保留边必须构成森林；最大化保留权即可。Observations、Editorial 与证明
原图把每个集合展开成同色团，边数可能平方级；关联图只为每次出现建一条边，总规模线性。
若关联图有简单环
$$ j_1-i_1-j_2-i_2-\cdots-j_k-i_k-j_1, $$
则原图中 $jt,j{t+1}$ 同属 $A_{i_t}$，可取颜色 $i_t$ 的边；简单环上的集合点互异，得到彩虹环。
若原图有彩虹环，对每条颜色边 $(x,y)$ 插入对应集合点 $i$，得到关联图闭合游走。颜色互异保证这些集合点不重复；闭合游走中可删去重复片段抽出简单环。因此“无彩虹环”等价于“保留出现边在关联图中无环”。
每条出现边删除代价就是其权。设全部权和为 $S$，删除集合代价为 $S-$保留权。合法保留集是森林，所以目标是最大权森林；所有权为正，按权降序运行 Kruskal，能加入且不成环的边全部加入。图可不连通，故是森林而非强求生成树。
环等价证明给出可行域一致；Kruskal 的割性质给出最大保留权，取补即最小删除代价。时间 $O(K\log K)$、空间 $O(m+n+K)$，$K=\sum|A_i|\le2\times10^5$。
实现指南、核心伪代码与附件
total = 0
for every occurrence j in set i:
add bipartite edge (set_i, value_j) with weight a[i]+b[j]
total += weight
sort all incidence edges by decreasing weight
kept = sum of edges accepted by DSU Kruskal
answer = total - kept
扩展与联系
关联图把“超边/集合”降成普通二分边。类似技巧还用于超图连通性与矩阵行列关系；但具体禁形是否等价于关联图环，必须逐方向证明。
实现边界与复盘
- 同一元素在同一集合内互异，但不同集合可形成平行的原图边；关联图用不同集合节点自然区分颜色。
- 不能直接在 $n$ 个元素点上跑 Kruskal：一条“保留出现”不是原图的一条固定元素边。
- 若禁止的是任意环而非彩虹环，关联图环等价不再成立，同一集合团内部的三角形就已违规。
- 识别信号是“对象属于若干组，组内任意两点建立同标签关系”；先尝试把组本身升格为节点。
总结与自检
请分别证明关联图环推出彩虹环、彩虹环推出关联图环。为什么目标是最大生成森林而不是最小生成树？
课后训练建议
先证明两个方向的环对应，再写代码；若只记住“二分图 + 最大生成树”，换题后很容易误用。用小关联图枚举保留边集对拍。