标签:Kruskal
4 个条目
-
题目 Earthquake
每条边有成本 c 和时间 t,最大化 (f - Σc) / Σt;二分答案后把边权改为 c + p t,用最小生成树判定。
2026-11-12 -
概念 Kruskal 算法实现
Kruskal 算法的并查集实现,含调用示例和实现细节。
2026-11-10 -
题目 Envy
多次询问一组边能否同时属于某棵 MST;按权值分组,用 Kruskal 的连通块不变性和可撤销并查集判定。
2026-11-10 -
构造 m 条边的连通简单图,边权为 a_u a_v;先求 MST,再用排序后的点权多路归并选剩余最小边。
2026-11-10