关于最小生成树

P4208 [JSOI2008] 最小生成树计数

枚举某个边权 $v$,删去所有边权等于 $v$ 的边。 如果有两个点集它们在一种最小生成树中联通,另一种最下生成树中不连通,那你考虑联通时连接两个连通块的边权: 1. 边权比 $v$ 大:那么将这条边删去,用一条边权为 $v$ 的边使他俩联通一定更优; 2. 边权比 $v$ 小:那将一条边权为 $v$ 的边权删掉,连接这条边会更优。
by APJifengc @ 2023-02-19 10:25:08


考虑 Kruskal 的过程也可以,你肯定是先连完边权比 $v$ 小的边,形成若干个联通块后再用 $v$ 连接起来一些连通块,最后将不连通的用大于 $v$ 的边连起来
by APJifengc @ 2023-02-19 10:27:17


@[Delov](/user/277792)
by APJifengc @ 2023-02-19 10:27:28


@[APJifengc](/user/279652) OK /bx
by Delov @ 2023-02-19 10:28:22


|