01-MST
完全图边权只有 0/1,给定权值为 1 的边;MST 权值为 0 边补图的连通分量数减 1。来源 Codeforces 1243 D · 难度 Codeforces 2100 · 标签 图论 / 生成树 / 补图 / BFS
题目描述
给定 个点的完全无向图,每条边的权值为 或 。给出其中 条权值为 的边,其余边权值均为 。求该图最小生成树的权值和。
,。
题解
边权只有 和 ,所以优先选 边。把只由 边连接的连通块缩成一个点:块内可以用 边连通,块间任取 条 边即可,其中 是 边图的连通块数。完全图保证块间边一定存在,因此答案为
问题转化为求给定 边图的补图连通块数。补图有 条边,不能显式建图。
用 BFS 和有序集合维护尚未访问的点:
- 初始时把所有点放入
unvisited; - 从
unvisited取出一个点,作为新连通块的起点,连通块数加一; BFS 中,对队首 遍历
unvisited中的所有 :- 若 不是 边,则补图中有 边,把 从
unvisited删除并入队; - 否则保留 ,继续检查下一个点。
- 若 不是 边,则补图中有 边,把 从
外层继续从 unvisited 取出下一个连通块的起点。
复杂度
每条 边最多被检查一次,每个点最多被删除一次,因此总复杂度 ,空间 。
参考
- 题目链接:CF 1243D 0-1 MST。