Acasă Explorează Ajutor
Autentificare
wfirstzhang
/
lessons
oglindă de https://gitee.com/wfz7789/noip_lessons.git
1
0
Bifurcare 0
Fisiere Probleme 0 Wiki
Ramură: main
Ramuri Etichete
lessons
/
课程
/
06-最小与最大生成树
/
02-替换边与MST边分类.md

02-替换边与MST边分类.md 6.9 KB
Permalink Istoric Crud

MST 替换边、强制选边与边的三分类

本节目标

学完后，你应能利用“非树边加入后形成唯一环”计算强制选边代价，并在 Kruskal 同权批次中判断一条边属于所有、至少一棵或不属于任何 MST。

前置知识与课前自测

前置：Kruskal、LCA/倍增、桥。

  1. 向一棵生成树加入非树边 $(u,v)$ 后形成几个环？
  2. 强制保留该边时，应从环上删最轻边还是最重边？
  3. 同权边为什么不能按任意顺序立即并查集合并后再分类？
自测答案 1. 唯一一个，由该边和树上 $u-v$ 路径组成。 2. 删树路径上的最重边，得到包含新边的最小权生成树。 3. 先处理的同权边会人为改变后处理边的连通性，把本可互换的边误标成无用。

问题动机与核心知识

固定一棵 MST $T$，加入非树边 $e=(u,v,w)$。任一包含 $e$ 的生成树必须在它形成的环上删一条边；为最小化新树权，应删路径最大边 $M$：

$$ W_e=W(T)+w-M. $$

若 $w=M$，存在等权替换，说明 MST 可能不唯一。这个结论把“每条边强制选入”转为树上路径最大值查询。

另一类问题要求不先固定某棵 MST，而直接分类全部边。处理权值 $w$ 前，Kruskal 已由更小权边形成若干分量：

  • 两端已在同一分量：加入必成环，不属于任何 MST；
  • 两端不同：在以这些分量为点、当前同权边为边的临时多重图中，它至少属于一棵 MST；
  • 若它还是临时图的桥，则连接两侧没有同权替代，属于每棵 MST。

实现指南

  • 路径最大值用二进制提升（binary lifting），预处理 $O(n\log n)$、查询 $O(\log n)$。
  • 同权分类必须分成“查询当前 DSU—临时图判桥—整批 union”三阶段。
  • 临时图可能出现平行边，即使原图无重边，因为多个原点可能压到同一对 DSU 分量；桥算法必须按边编号跳父边。

精选例题 1：Minimum spanning tree for each edge

来源信息与题意

连通简单无向图有 $n,m\le2\times10^5$，边权至 $10^9$。对每条边，求必须包含它的最小生成树权值。

Hint 1先任选一棵 MST 并记录总权。
Hint 2非树边加入后，只需删除其两个端点在 MST 路径上的最大权边。
Hint 3树边答案就是原 MST 总权；路径最大值用 LCA 倍增。

Observations、Editorial 与证明

Kruskal 得到 MST。对非树边 $e$，加入后产生唯一环；任一包含 $e$ 的树需删环上一条树边，删最大边最优。设存在更优的包含 $e$ 的生成树 $T'$，把 $e$ 从 $T'$ 删掉得到一个割；原 MST 必有一条边 $f$ 跨越该割，且 $w(f)\le w(e)$（否则把 $f$ 换入 $T$ 可改进 MST）。用 $f$ 替换 $T'$ 中的某条边得到的生成树仍不差于 $T'$，故 $T'$ 不是更优者，删路径最大边即最优。

总复杂度 $O((n+m)\log n)$，答案用 long long。

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

T, total = Kruskal_MST(graph)
preprocess binary lifting for maximum edge on every tree path
for edge e=(u,v,w):
    if e belongs to T: answer[e] = total
    else: answer[e] = total + w - maximum_on_tree_path(u,v)

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

复盘与变式

若问强制删除一条 MST 边后的最优值，需要找所有跨越该树边割的非树边最小权，通常用树上路径区间取最小的离线更新。

精选例题 2：Edges in MST

来源信息与题意

给连通简单带权无向图，$2\le n\le10^5$，逐边输出：属于每棵 MST（any）、至少一棵（at least one）或不属于任何 MST（none）。

Hint 1按权分组；处理权 $w$ 时，DSU 只能包含严格小于 $w$ 的边。
Hint 2两端已经同组的边是 `none`；其余边在当前 DSU 分量构成的临时图中竞争。
Hint 3临时图中的桥无法由另一组同权边替代，是 `any`；其他候选为 `at least one`。
Hint 4分类结束后再把整组边 union，为下一权值做准备。

Observations、Editorial 与证明

Kruskal 在权 $w$ 前的 DSU 分量由所有更轻边强制形成。组内一条边若两端同分量，加入会在更轻边上成环，必不入 MST。否则，任何 MST 在临时图每个连通块中选择一棵生成森林；非桥可通过交换进入某棵森林，桥则是连接其两侧的唯一同权选择，所有森林都必须包含。

每条边只进入一次临时图，桥判定总规模线性，加排序总复杂度 $O(m\log m+n\alpha(n))$。

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

sort edges into equal-weight groups; DSU contains only lighter edges
for each group:
    edges already inside one DSU component are 'none'
    contract DSU roots and build a temporary multigraph from remaining edges
    temporary bridges are 'any'; other remaining edges are 'at least one'
    union all group edges in the global DSU

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

复盘与变式

若只问 MST 是否唯一，只要某个同权临时图存在非桥候选可交换即可判否；也可在固定 MST 上检查非树边权是否等于树路径最大值。

扩展与联系

  • 次小生成树用同一替换公式：在所有非树边中取 $w>max$ 的最小 $w-max$，再加上 $W$ 即为次小生成树权。
  • 最大生成树把路径最大替换为路径最小，比较方向反转。
  • CodeForces-1108F MST Unification 本质是在同权临时图中消除可交换选择；可作为本节迁移训练。

总结与自检

  1. 强制选非树边的替换公式为何删路径最大边？
  2. 正权/非负权是否影响这个替换结论？
  3. 边分类为何必须按同权批次？
  4. 临时图桥为何对应 any？平行边如何影响桥？

课后训练建议

先用枚举全部生成树对拍两份实现。第一题重点验证非树边公式；第二题构造同权三角形、同权平行缩点边和严格最轻割边。完成后做 MST Unification，只在无法建立“同权临时图”时回看 Hint。