1. 贪心正确性证明的'安全边'框架中以 Kruskal 为例，如何用切割性质（cut property）证明每次选择的边都属于某个最小生成树？
问题
说明贪心正确性证明的"安全边"框架，并以 Kruskal 算法为例，用切割性质（cut property）证明每次选择的边都属于某个最小生成树？
考察点
- 安全边（safe edge）的概念
- 切割性质（cut property）的叙述
- 用切割性质证明 Kruskal 边安全
答案
安全边框架：若已构造一个不完整的最小生成树 A（A 是某个 MST 的子集），则"安全边"是一条加入 A 后仍保持 A 是某个 MST 子集的边。若每次选择安全边，则最终 A 扩展为 MST。切割性质（cut property）：设 A 是某个最小生成树的子集，对任意切割 (S, V−S)，若 A 不包含跨越该切割的边，且 e 是跨越该切割的最小权边，则 e 是安全边。Kruskal 的证明：算法按权值从小到大遍历边，检查是否形成环。设当前处理的边 e=(u,v)，若 e 的端点分属不同连通分量，则 e 不构成环。考虑切割：把 u 所在连通分量记为 S，则 (S, V−S) 是一个切割，A 中无跨越它的边（因为 u、v 分属不同分量，A 中无连接两者的边）。e 是跨越该切割的最小权边吗？因为 Kruskal 按权值升序处理，之前加入的边权都 ≤ w(e)，且 e 是当前最小的安全候选，故 e 是跨越该切割的最小权边。由切割性质，e 是安全边，加入后 A 仍是某个 MST 的子集。归纳得最终 A 是 MST。
解析
安全边框架把贪心正确性归约为"每次选择都是安全边"。切割性质提供了一种通用的安全边判定：只要存在一个不含 A 中边的切割，且所选边是该切割最小权边，它就是安全的。Kruskal 用"连通分量"构造切割，用"升序处理"保证最小权，从而每次选择都满足切割性质。
示例代码
// Kruskal 最小生成树（并查集 + 按权排序）
class Edge implements Comparable<Edge> { int u, v, w; public int compareTo(Edge o){return w-o.w;} }
int kruskal(int n, Edge[] edges) {
Arrays.sort(edges);
DSU dsu = new DSU(n);
int total = 0;
for (Edge e : edges) {
if (dsu.find(e.u) != dsu.find(e.v)) { // 不构成环：e 是安全边
dsu.union(e.u, e.v);
total += e.w;
}
}
return total;
}