1639

题意:求无向图的最小度限制生成树。

最小度限制生成树,就是满足结点 $v_0$ 的度不超过 $k$ 的最小生成树。

由于这道题目数据范围很小,图中最多有20个结点,所以我们可以枚举从 $v_0$ 连出的边,然后在其余边中进行Kruskal算法。复杂度 $O(ElogE+2^VE)$ 。

最小度限制生成树有更加出色的 $O(kV)$ 做法。它的过程是:先将结点 $v_0$ 与和它相连的边从图中删去,设剩余部分得到 $s$ 个连通块。若 $s > k$,则无解;否则,先求出所有连通块各自的最小生成树,然后从 $v_0$ 向每个连通块连一条权值最小的边。这样,我们已经得到了一个度限制为 $s$ 的最小生成树。但是,这不一定是最优的,若我们从 $v_0$ 再向原先的其中一个连通块连边,有可能会去掉连通块中一条权值比较大的边。具体的做法是维护一个数组 $max[i]$ ,表示从 $v_0$ 到 $i$ 的路径中权值最大的边的权值,所以我们每次选择 $max[i]-w(v_0,i)$ 最大的边进行更新,直到总权值不会被更新得更小或结点 $v_0$ 的度已经达到 $k$ 。

下面给出的代码采用暴力做法。

Code