最小度限制生成树是指某一个节点的度限制为k的最小生成树。具体的做法去看论文或者黑书吧，这里不详细讲了。
理解最小度限制生成树的解法，最主要的就是看懂如何由m度生成树求m+1度生成树，另外要理解无解的情况。
今天终于把模板整理出来了，prim那里用了优先队列优化，添加删除边破环那里用的是动态规划。试了试PKU1639这道题，结果正确，但是由于数据水，不知道效率如何。
贴出模板：
1 #define maxn 505 2 struct str 3 { 4 int v,c,n; 5 }edge[maxn<<1];//邻接表 6 int head[maxn],cnt; 7 void init() 8 { 9 memset(head,-1,sizeof(head)); 10 cnt=0; 11 } 12 void addEdge(int u,int v,int c) 13 { 14 edge[cnt].v=v; 15 edge[cnt].c=c; 16 edge[cnt].n=head[u]; 17 head[u]=cnt++; 18 edge[cnt].v=u; 19 edge[cnt].c=c; 20 edge[cnt].n=head[v]; 21 head[v]=cnt++; 22 } 23 int dis[maxn],best[maxn],index[maxn]; 24 //dis是prim里到某节点的最短距离，best具体含义看论文，index是best对应的边号 25 int incom[maxn],com;//记录节点在哪个联通分量里 26 bool vis[maxn],intree[maxn<<1]; 27 struct node 28 { 29 int u,c,e;//u是邻接表里对应的那个v,c是边权，e是边号 30 node(){} 31 node(int _u,int _c,int _e):u(_u),c(_c),e(_e){} 32 bool operator <(const node a)const{return a.c<c;} 33 };//优先队列数据结构 34 priority_queue<node>q; 35 int prim(int n,int s) 36 { 37 for(int i=0;i<=n;i++)dis[i]=inf; 38 memset(vis,0,sizeof(vis));vis[s]=true; 39 memset(intree,0,sizeof(intree));//判断边是否在生成树中 40 int val=0;com=0; 41 for(int i=1;i<=n;i++)if(!vis[i])//求各个连通分量的最小生成树 42 { 43 dis[i]=0;++com;q.push(node(i,0,-1)); 44 while(!q.empty()) 45 { 46 int u=q.top().u,e=q.top().e,c=q.top().c;q.pop(); 47 if(vis[u])continue; 48 val+=c;incom[u]=com; 49 vis[u]=intree[e]=intree[e^1]=true; 50 for(int j=head[u];j!=-1;j=edge[j].n) 51 { 52 int v=edge[j].v,c=edge[j].c; 53 if(vis[v])continue; 54 if(dis[v]>c)dis[v]=c,q.push(node(v,c,j)); 55 } 56 } 57 } 58 memset(vis,0,sizeof(vis));//vis数组复用，判断某节点所在的连通分量是否已经连接 59 for(int i=head[s];i!=-1;i=edge[i].n) 60 { 61 int v=edge[i].v,c=edge[i].c; 62 q.push(node(v,c,i)); 63 } 64 while(!q.empty())//把各个分量连起来，这样就求出m度最小生成树 65 { 66 int v=q.top().u,c=q.top().c,e=q.top().e; 67 q.pop(); 68 if(!vis[incom[v]]) 69 val+=c,intree[e]=intree[e^1]=vis[incom[v]]=true; 70 } 71 return val; 72 } 73 void dfs(int u,int fa,int n,int s)//更新best 74 { 75 for(int i=head[u];i!=-1;i=edge[i].n)if(intree[i]) 76 { 77 int v=edge[i].v,c=edge[i].c; 78 if(v==fa)continue; 79 if(u==s)best[v]=-inf,index[v]=i; 80 else 81 { 82 if(best[u]>c)best[v]=best[u],index[v]=index[u]; 83 else best[v]=c,index[v]=i; 84 } 85 dfs(v,u,n,s); 86 } 87 } 88 //int mval; 89 int klimit(int n,int s,int k)//求k度最小生成树,n是节点个数，s是度被限制的节点，k为限制的度数 90 { 91 int val=prim(n,s); 92 //mval=val; 93 if(k<com)return inf;//如果k小于连通分量个数，则无解 94 best[s]=-inf;dfs(s,-1,n,s); 95 for(int i=com+1;i<=k;i++) 96 { 97 int mn=inf,ed=-1; 98 for(int j=head[s];j!=-1;j=edge[j].n)if(!intree[j]) 99 { 100 int v=edge[j].v,c=edge[j].c; 101 if(mn>c-best[v])mn=c-best[v],ed=j; 102 } 103 if(ed==-1)return inf;//无法再使度扩大则也是无解的 104 int v=edge[ed].v,dx=index[v]; 105 val+=mn; 106 //mval=min(val,mval); 107 intree[ed]=intree[ed^1]=true; 108 intree[dx]=intree[dx^1]=false; 109 best[v]=-inf,dfs(v,s,n,s); 110 } 111 return val; 112 }
如果是求某节点正好为k度则就是上面的模板，如果节点的度不大于k则将上面mval的三条注释取消掉，最后结果就是mval。