黑书上的例题，所以题意就不啰嗦了，具体模型是求一个无向图的最小生成树，其中有一个点的度有限制（假设为 k）。
要求最小 k 度生成树，我们可以按照下面的步骤来做：
设有度限制的点为 V0 ，V0称为根节点
1，把所有与 V0 相连的边删去，图会分成多个子图（假设为 m 个，显然的，如果 m > k，那么问题无解），让他们分别求最小生成树；然后用最小的代价将 m 个最小生成树和 V0 连起来，那我们就得到了一棵关于 V0 的最小 m 度生成树。
2，在 m 度生成树中找一个点和 V0 相连（设这条边的权值为 a），会生成一个环，为了满足最小生成树的要求，我们必须删掉一条边（设这条边的权值为 b），以使总权值尽量小，那么就要求 a 尽量的小，b 尽量的大。
完成一次 2 的操作后得到的是 m+1 度最小生成树，以此类推，直到得到最小 k 度生成树。
具体参见
汪汀2004年的国家集训队论文，讲的很详细。
PS：这道题并不是要求 k 度的最小生成树，而是要求根节点的度在不超过 k 值的情况下，该图的最小生成树。也就是说，不一定要求到 k 度生成树，只要图的总权值不能继续减小我们就可以停下来了。
代码是“拿来”的，因为用map处理数据，所以代码量小了一点，而且方便的多了，STL是真的很强大，orz……
#pragma warning (disable : 4786)//屏蔽VC中的一些警告
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<queue>
#include<map>
#include<climits>
using namespace std;
const int N = 21;
struct node{
int v,cost;//点 v ,dist[v]
node(){}
node(int vv,int ww):v(vv),cost(ww) {}
};
bool operator < (const node &l,const node &r){
return l.cost > r.cost;
}
priority_queue<node> q;
map<string,int> Map;
int mat[N][N],dist[N],clo[N],pre[N],fst[N],max_side[N];
int n,K;
int prim(int s,int id){
while(!q.empty())q.pop();
dist[s]=0;
q.push(node(s,0));
int res=0;
while(!q.empty()){
node cur=q.top();
q.pop();
int u=cur.v;
if(!clo[u]){
clo[u]=id;
res+=dist[u];
for(int i=1;i<n;i++){
if(!clo[i] && mat[u][i]!=0 && mat[u][i]<dist[i]){//满足松弛条件
pre[i]=u; dist[i]=mat[u][i];
q.push(node(i,dist[i]));
}
}
}
}
return res;
}
void update(int cur,int last,int maxside){//也是一个dfs过程,直到搜回到起点,同时完成了max_side[]更新
max_side[cur]=maxside>mat[cur][last]?maxside:mat[cur][last];
for(int i=1;i<n;i++){
if(i!=last && mat[cur][i]!=0 && (pre[cur]==i || pre[i]==cur))
update(i,cur,max_side[cur]);
}
}
void solve(){
int i,res,cnt;
for(i=0;i<n;i++){
dist[i]=INT_MAX;
clo[i]=pre[i]=fst[i]=0;
}
res=0; cnt=1;//除去根节点后,图中的连通子图个数,即最小生成树个数
for(i=1;i<n;i++){
if(!clo[i]) res+=prim(i,cnt++);
}
for(i=1;i<n;i++){//找到每个生成树和 Park 最近的点使之和 Park 相连
int id=clo[i];
if(mat[0][i]!=0 && (!fst[id] || mat[0][i]<mat[0][fst[id]]) )
fst[id]=i;
}
for(i=1;i<cnt;i++){//把m个生成树上和根节点相连的边加入res,得到关于Park的最小m度生成树
res+=mat[0][fst[i]];
mat[0][fst[i]]=mat[fst[i]][0]=0;//之所以用邻接阵就是因为删除边很方便
update(fst[i],0,0);
}
/*
添删操作:将根节点和生成树中一个点相连,会产生一个环,将这个环上(除刚添的那条边外)权值最大
的边删去.由于每次操作都会给总权值带来影响 d=max_side[tmp]-mat[0][tmp],我们需要得到最小生
成树,所以我们就要求 d 尽量大
*/
K=K-cnt+1;//接下来重复操作,直到度数满足条件
while(K--){
int tmp=0;
for(i=1;i<n;i++){//找 d 值最大的点(就是说完成添删操作后可以使总边权减小的值最大)
if(mat[0][i]!=0 && (tmp==0 || max_side[tmp]-mat[0][tmp]<max_side[i]-mat[0][i]))
tmp=i;
}
if(max_side[tmp]<=mat[0][tmp])break;//总权值无法再减小
res-=max_side[tmp]-mat[0][tmp];
mat[0][tmp]=mat[tmp][0]=0;
int p=0;
for(i=tmp;pre[i]!=0;i=pre[i]){
if(p==0 || mat[p][ pre[p] ]<mat[i][ pre[i] ]) p=i;
}
pre[p]=0;
update(tmp,0,0);
}
printf("Total miles driven: %d\n",res);
}
int main()
{
int m,x;
string ch1,ch2;
while(~scanf("%d",&m))
{
Map["Park"]=0;
n=1;
memset(mat,0,sizeof(mat));
while(m--){
cin>>ch1>>ch2>>x;
if(!Map.count(ch1)) Map[ch1]=n++;
if(!Map.count(ch2)) Map[ch2]=n++;
int u=Map[ch1];
int v=Map[ch2];
if(!mat[u][v] || x<mat[u][v])
mat[u][v]=mat[v][u]=x;
}
scanf("%d",&K);
solve();
}
return 0;
}