# 高阶扩展：从彩虹环到关联图最大生成森林 ## 本节目标 把“每个集合内部产生同色团”的彩虹环条件，转写成集合—元素二分关联图中的普通环；再把最小删除代价取补，变成最大权森林。 ## 前置知识与课前自测 前置：DSU、Kruskal、二分关联图。 1. 一个集合节点连接多个元素节点时，两条关联边能代表原图中的什么？ 2. 二分关联图的一条交替环怎样投影成原图彩虹环？ 3. 最小删除权与最大保留权如何互补？
答案 1. 两元素间一条颜色为该集合编号的边。 2. 每经过一个集合节点，就在它相邻的两个元素间取一条该颜色边；环上集合节点互异时颜色互异。 3. 删除权等于全部权减保留权。
## 问题动机 每个集合在原图中展开成同色团，显式边数可能平方级；而“彩虹”限制又要求记住边来自哪个集合。把集合升格为节点，可以同时压缩团并保留颜色身份。 ## 精选例题：Avoid Rainbow Cycles ### 来源与题意 - VJudge：[CodeForces-1408E](https://vjudge.net/problem/CodeForces-1408E) - 原题：[Codeforces 1408E](https://codeforces.com/problemset/problem/1408/E) - 难度：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, $$ 则原图中 $j_t,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$。 ## 实现指南、核心伪代码与附件 ```text 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 ``` [完整 GNU C++17 实现](../../参考实现/06-最小与最大生成树/CodeForces-1408E.cpp) ## 扩展与联系 关联图把“超边/集合”降成普通二分边。类似技巧还用于超图连通性与矩阵行列关系；但具体禁形是否等价于关联图环，必须逐方向证明。 ## 实现边界与复盘 - 同一元素在同一集合内互异，但不同集合可形成平行的原图边；关联图用不同集合节点自然区分颜色。 - 不能直接在 $n$ 个元素点上跑 Kruskal：一条“保留出现”不是原图的一条固定元素边。 - 若禁止的是任意环而非彩虹环，关联图环等价不再成立，同一集合团内部的三角形就已违规。 - 识别信号是“对象属于若干组，组内任意两点建立同标签关系”；先尝试把组本身升格为节点。 ## 总结与自检 请分别证明关联图环推出彩虹环、彩虹环推出关联图环。为什么目标是最大生成森林而不是最小生成树？ ## 课后训练建议 先证明两个方向的环对应，再写代码；若只记住“二分图 + 最大生成树”，换题后很容易误用。用小关联图枚举保留边集对拍。