这是最小度限制生成树的经典问题，题意就不说了
题目链接：?id=1639
一般都是1个顶点的度有限制k，如果每个顶点的度都有限制，那么当前是NP难的。
为了解决这个题目，先把限制度数的点设为V0点，那么把这一点先除外，那么剩下的点都没有度数限制，所有先对他们进行分析，把他们求生成森林后，假设得到t个连通分量，所以为了生成一棵把v0包含在内的树，必须让v0的度数限制度数k>=t,如果<t，无解。
接下来k度中已经用掉了t度，如何求从t度到k度的最小生成树呢，还是添边成环再删边的思想，所以：遍历从V0的出边找到一条删掉的边比添加的边差值最大的那一方案，也就是让t+1度生成树尽可能小。就这样循环k-t次即可。当然如果某一次历遍从v0的出边（没用过的出边）以后，发现每种方案成环删掉的边都要比添边小，那么生成树不可能再变小，所以已是最优解。
思路很简单，但是代码实现的确有点难…我的代码实现用的是kruskal总的复杂度是log(Vk+Elog|E| )，难点在于找到最小差值添删操作，我用dfs维护v0到各个连通分量间的各个顶点路径间的最大边。然后用tree[ ][ ]数组记录v0外生成森林的边，，可以任意修改添删。
另外这个ppt说的不错，
还有黑书p300~303给了严谨和较详细的证明，实现方法比较说的比较粗略
//256 KB16 ms#include<cstdio>#include<iostream>#include<algorithm>#include<cstring>#include<map>#include<string>#include<vector>#define inf 0x3f3f3f3fusing namespace std;struct node{int a,b,w;}edge[505];struct node2{int to,w;bool cancel;}v0[25]; // 记录v0点的出边 int tree[25][25]; //记录把v0除外的生成森林（也就是各个连通分区，而不是包括V0的整棵生成树，这样操作是便于后面从v0遍历连接的连通分区，更新pathmax），用数组单独记录可以灵活修改 int pathmax[25]; //记录v0点到其他点的路径上除了v0出边以外的最长边 int maxedge[2][25]; //记录对应pathmax最长边的两个顶点，便于后面生成树的边的删除。 bool vis[25]; //用于dfs过程中的标记 int f[25]; int m,k,n,n0,ans; //n0是v0出边的总数 map <string,int>IDache; //把字符型顶点转化成序号 bool cmp1(const node &a,const node &b){return a.w<b.w;}bool cmp2(const node2 &a,const node2 &b){return a.w<b.w;}int getID(string &x){if(IDache.count(x)) return IDache[x];return IDache[x]=++n;}void ini(){IDache["Park"]=0;scanf("%d",&m);for(int i=1;i<=m;i++){string s1,s2;int w;cin>>s1>>s2>>w;int t1=getID(s1),t2=getID(s2);edge[i].a=t1;edge[i].b=t2;edge[i].w=w;}scanf("%d",&k);for(int i=0;i<=n;i++) f[i]=i; }int getf(int x){return x==f[x]? x:f[x]=getf(f[x]);}void unite(int x,int y){int t1=getf(x),t2=getf(y);if(t1==t2) return;f[y]=x;}int kruskal(){memset(tree,0x3f,sizeof(tree)); //把树的各个顶点的距离初始化成inf表示没边sort(edge+1,edge+1+m,cmp1);//先把V0除外去生成森林for(int i=1;i<=m;i++){if(!edge[i].a||!edge[i].b) continue;int x=getf(edge[i].a),y=getf(edge[i].b);if(x==y) continue;unite(x,y);ans+=edge[i].w;tree[edge[i].a][edge[i].b ]=tree[edge[i].b ][edge[i].a ]=edge[i].w;}return ans;}//logV，从v0遍历生成树一次来记录v0点到其他点的路径上除了v0出边以外的最长边 void dfs(int u,int v,int maxn,int maxnu,int maxnv) // maxnu,maxnv表示最长边的两个顶点 {vis[u]=1;if(u!=0&&tree[u][v]>maxn){maxn=tree[u][v];maxnu=u;maxnv=v;}pathmax[v]=maxn;maxedge[0][v]=maxnu;maxedge[1][v]=maxnv;for(int i=1;i<=n;i++){if(tree[v][i]!=inf&&!vis[i]) dfs(v,i,maxn,maxnu,maxnv);}}int main(){ini();ans=kruskal();//找到V0的出边for(int i=1;i<=m;i++){if(edge[i].a&&edge[i].b) continue;v0[++n0].to=max(edge[i].a,edge[i].b);v0[n0].w=edge[i].w;v0[n0].cancel=false;}sort(v0+1,v0+n0+1,cmp2);//排序 ，便于后面把连通分区连通的操作int cnt=0;//连通各个连通分区，合成一棵树for(int i=1;i<=n0;i++){int x=getf(v0[i].to),y=getf(0);if(x==y) continue;unite(x,y);ans+=v0[i].w;v0[i].cancel=true; //这条出边已用过，标记，下次不需再用了cnt++;memset(vis,0,sizeof(vis));dfs(0,v0[i].to,0,0,0);}//递归求出从cnt度到K度的生成树for(int j=1;j<=k-cnt;j++){int minn=inf;int t,book;for(int i=1;i<=n0;i++){ //遍历n0条出边中没用过的出边，找到差额最小添删操作if(v0[i].cancel) continue;int to=v0[i].to;if(minn>v0[i].w-pathmax[to]){minn=v0[i].w-pathmax[to];t=to;book=i;}}if(minn>=0) break;//如果连最小的差额都是正数，那么就不可能再让当前的生成树更小了，已是最优解break。ans+=minn;tree[maxedge[0][t] ][maxedge[1][t]]=tree[maxedge[1][t]][maxedge[0][t]]=inf;//森林删边v0[book].cancel=true;memset(vis,0,sizeof(vis));dfs(0,t,0,0,0); //维护V0与这个连通分量的pathmax数组。}printf("Total miles driven: %d\n",ans);return 0;}
若不给自己设限，则人生中就没有限制你发挥的藩篱。
