概念：在一个无向图中，在某个特殊点限制了必须为k度的情况下，而求出的最小生成树。
一些阐述：
[关于字母]：
设边集为E，特殊点为V0，最小限制生成树为D。
Hi表示V0的度数为i时的最小生成树。
[关于操作]：
删添操作：在树上加入某条顶点为V0的点，在构成的环中删掉另一条不与V0关联的边。
最大删添：删添时去掉环中最大的一条不与V0关联的边。
差额最大删添：加入的边与最大删添的差值最大的一次删添。
原理：见黑书p300-p303。
证明有些复杂，于是跳过证明得到定理一：
若T为V1...Vn的某棵最小生成树，若边(i,j)不属于T，则(i,j)不属于D。
这样可以大大缩小选择边的范围。
定理二：
H1为T的基础上加一条最短的(V0,Vi)
H1可以通过k-1次差额最小删添操作得到Hk。
这样可以方便我们从H1逐渐递推到Hk
具体步骤：
1.找到V1...Vn的所有连通块，求出每个连通块的最小生成树Ti。
2.在每个块中选出一条最小的与V0相连的边 [ 若块的数目t>k则无解 ]，从而得到Ht。
3.for i=t+1 to k
通过Hi-1 上进行“差额最小删添操作”，添加并删除一条边得到Hi。
其中差额最小删添操作的优化可以用：令Maxi表示Vi到V0的路径上的最大边，那么连上(V0,Vi)的代价就是f(Vi)=w(V0,Vi)-Maxi，所有f(Vi)中的最小值就是差额最小删添操作。
Maxi的预处理需要O(n)从V0开始dfs，每次选了一条(V0,Vi)后则需要从Vi再跑一次，也是O(n)的。
4.输出答案
题目练习：Poj 1639 Picnic Planning野餐计划
还没打过代码...未完待续
原文：http://www.cnblogs.com/Robert-Yuan/p/5034467.html