经典的顶点度数限制为K的最小生成树。我是靠模版做出来的。这题的详细解法建议看黑书的生成树那章的相关内容。这里引用czyuan神的做法吧，我的模版就是那里来的。。。。。
具体步骤：（算法的证明可以参照lrj的《算法艺术和信息学竞赛》）
（我们假定度有限制的结点为V0）
1. 求出除去V0，其他每个森林的最小生成树（除去V0后，其他的点不一定都是连通的）。
2. 在每个森林中找出与V0距离最近的点，并与V0相连（此时即为一棵生成树，这棵生成树的根结点为V0，即在与V0相连时，要修改前驱数组pre[]）。
3. 循环 （度数 – 森林数）次，每次找到g[0][i] – max_value[i]最小的i结点，其中max_value[i]为Vi到V0的路径上不与V0相连的边的最大权值。
如果g[0][i] – max_value[i] >= 0说明已经是最优解了，退出。
否则加入g[0][i]这条边，删去Vi到V0的路径上不与V0相连的最大权值的边。
这里算法的瓶颈在于如何快速快速找到“Vi到V0的路径上不与V0相连的边的最大权值”。一开始我是用O(kn2)的模拟，即每次从Vi向上找到根结点，求出最大权值。提交上去16ms。
Lrj书上说可以用max_value[i]记录Vi到V0的路径上不与V0相连的边的最大权值，而初始化和维护都只要O(n)，想了半天，发现其实就是递推呀。我们可以从Vi向上找到根结点，再用栈反向递推回来，即：
max_value[Stack[i]] = MAX(max_value[Stack[i + 1]], g[Stack[i]][ pre[Stack[i]]]
还可以用数组max_value_v记录最大权值的边的起点。这样每次只要直接比较g[0][i] – max_value[i]，找到最小值，然后添加(i, 0)边，并修改Vi到V[max_value_v[i]]的前驱数组pre[]，再，反向递推求出V[max_value_v[i]]到 V0路径上结点的max_value值。
这样第3步的复杂度就降为O(kn)。
但可能是程序在输入上用map，处理比较慢，结果还是16ms(晕……)，POJ这题数据太弱了，(n <= 20)。
以下是代码：
#include<iostream> #include<map> #include<queue> #include<climits> #include<fstream> #include<string> using namespace std; const int N=30; const int inf=1<<29; struct node { int v,w; }; struct cmp { bool operator() (const node &a,const node &b) { return a.w>b.w; } }; int n,m,s; int num; int minV0[N]; int total; int dist[N]; int g[N][N]; bool p[N]; int pre[N]; int max_value[N],max_value_v[N]; priority_queue<node,vector<node>,cmp > Q; map<string,int> Map; int ans; void cal_max_value(int t) { int i,j,k; int stack[N]; int top=-1; i=t; while(pre[i]!=0 && pre[i]!=-1) { p[i]=1; stack[++top]=i; i=pre[i]; } if(top<0) return ; j=stack[top]; max_value[j]=g[j][pre[j]]; max_value_v[j]=j; for(i=top-1;i>=0;i--) { j=stack[i]; k=stack[i+1]; if(max_value[k]>g[i][pre[j]]) { max_value[j]=max_value[k]; max_value_v[j]=max_value_v[k]; } else { max_value[j]=g[j][pre[j]]; max_value_v[j]=j; } } } void solve() { int i,j,k,l; int mini,opti_i,opti_maxV; for(k=1;k<=num;k++) { ans+=g[0][minV0[k]]; j=minV0[k];i=pre[j]; while(i!=-1) { l=i; i=pre[l]; pre[l]=j; j=l; } pre[minV0[k]]=0; } memset(p,0,sizeof(p)); for(i=1;i<=n;i++) { if(!p[i]) cal_max_value(i); } for(k=1;k<=total-num;k++) { mini=0; for(i=1;i<=n;i++) { if(pre[i]==0) continue; if(g[0][i]-max_value[i]<mini) { mini=g[0][i]-max_value[i]; opti_i=i; opti_maxV=max_value_v[i]; } } if(mini==0) break; ans+=mini; pre[opti_maxV]=-1; j=opti_i; i=pre[j]; while(i!=-1) { l=i; i=pre[l]; pre[l]=j; j=l; } pre[opti_i]=0; cal_max_value(opti_maxV); } } void prim() { int i,j,k; node min,temp; while(!Q.empty()) Q.pop(); dist[s]=0; temp.v=s; temp.w=0; Q.push(temp); for(k=1;k<=n;k++) { while(!Q.empty()) { min=Q.top(); Q.pop(); j=min.v; if(!p[j]) { p[j]=1; if(g[0][j]<g[0][minV0[num]]) { minV0[num]=j; } for(i=1;i<=n;i++) { if(i!=j && !p[i] && dist[i]>g[j][i]) { dist[i]=g[j][i]; pre[i]=j; temp.w=dist[i];temp.v=i; Q.push(temp); } } break; } } } } int main() { // freopen("in.txt","r",stdin); int i,j; string name1,name2; int a,b,w; map<string,int>::iterator it; Map.clear(); Map["Park"]=0; for(i=0;i<=N-1;i++) { dist[i]=inf; pre[i]=-1; for(j=0;j<=N-1;j++) { g[i][j]=inf; } } n=0; cin>>m; for(i=1;i<=m;i++) { cin>>name1>>name2>>w; it=Map.find(name1); if(it==Map.end()) { n++; Map[name1]=n; } a=Map[name1]; it=Map.find(name2); if(it==Map.end()) { n++; Map[name2]=n; } b=Map[name2]; if(g[a][b]>w) { g[a][b]=g[b][a]=w; } } cin>>total; memset(p,0,sizeof(p)); num=0; for(i=1;i<=n;i++) { if(!p[i]) { s=i; num++; minV0[num]=s; prim(); } } ans=0; for(i=1;i<=n;i++) ans+=dist[i]; solve(); printf("Total miles driven: %d/n", ans); return 0; }