有度数限制的最小生成树

· · 算法·理论

以下所有令有度数限制的点为 s，常数为 k。

例 1 P5633（某一点度数恰好为一个常数）

考虑把 s 从做法中独立出来，即建立一个以 s 为根的生成树。

如果某一个非 s 的点与 s 间有直接连边，则它可以构成 s 的一度，规定点权就是这条边的边权，如果没有直接连边点权为正无穷。
显然最后只能选 k 个点权非正无穷的点当做 s 的直接孩子。

先对非 k 点求最小生成树（森林），组成答案的边也一定在最小生成树（森林）上，显然每一棵生成树中一定有一个点权非正无穷的，我们令点权最小的点为树根。
如果此时森林中树的个数大于 k，则一定不可能存在答案。
因为此时我们需要增加树的个数，所以一定要破坏原有最小生成树（森林）。

考虑加点的代价，即为 +E_u-w(u,v)，注意能加树的当且仅当 E_u 不为正无穷。

所以排序做一下即可。

例 2 P5633（某一点度数小于等于一个常数）

与例 1 基本相同。

这里不必须加点，但是 +E_u-w(u,v) 不一定为正，所以还需要加点求最小。

更深的思考

如果有多个点有度数限制，能不能有可靠解法？如果生成树是 k 叉树，有没有非 NP-Hard 解法？

希望读者能够思考出这些问题，并拿到图灵奖！