节点1是有度数限制的，把节点1去掉，就会形成若干个连通块，在每个连通块内部求最小生成树（prim算法实现），并求出每个连通块与1相连的最短的边，这样形成了初始状态的生成树。

假设（1，x）这条边没在生成树中，如果在生成树中从1到x的路径中的最大边权大于（1，x），考虑加上（1，x），去掉这条最大边权的边，答案就更加优秀了，若干次重复这样的操作，直到达到度数限制，就可以得到最优解。

记录最大边权的思路基于DP，回溯打标记。

完成一次拓展后，加入了（1，x）这条边，修改x的f[ ],fx[ ],fy[ ]，给1打上标记，从x开始DP，因为只是修改了x所在的连通块，没有必要再从1遍历一次。（可以画图理解一下）。

1 #include
2 using namespace std;
3 int n,m,s,deg,ans;
4 int a[32][32],d[32],conn[32];
5 bool v[32],c[32];
6 int tree[32][32];
7 int ver[32],p;
8 int f[32],fx[32],fy[32];//1-x的路径最大边权是f[x]，两个端点是fx[x],fy[x]
9
10 void read(){
11 map h;
12 cin>>m;
13 h["Park"]=1;n=1;
14 memset(a,0x3f,sizeof(a));
15 for(int i=1;i<=m;i++){ 16 int x,y,z; 17 char sx[12],sy[12]; 18 scanf("%s%s%d",sx,sy,&z); 19 if(!h[sx]) h[sx]=++n; 20 if(!h[sy]) h[sy]=++n; 21 x=h[sx],y=h[sy]; 22 a[x][y]=min(a[x][y],z); 23 a[y][x]=min(a[y][x],z); 24 } 25 cin>>s;
26 }
27
28 void prim(int root){
29 d[root]=0;
30 for(int i=1;i<=p;i++){ 31 int x=0; 32 for(int j=1;j<=p;j++) 33 if(!v[ver[j]]&&(x==0||d[ver[j]]a[x][y])
38 d[y]=a[x][y],conn[y]=x;
39 }
40 }//prim算法模板
41 int closest=root;
42 for(int i=1;i<=p;i++){ 43 int x=ver[i]; 44 if(x==root) continue; 45 ans+=d[x]; 46 tree[conn[x]][x]=tree[x][conn[x]]=d[x]; 47 if(a[1][x]tree[x][y]){
80 f[y]=f[x];
81 fx[y]=fx[x],fy[y]=fy[x];
82 }else{
83 f[y]=tree[x][y];
84 fx[y]=x,fy[y]=y;
85 }
86 dp(y);
87 }
88 }
89 v[x]=false;//回溯
90 }
91
92 bool solve(){
93 int min_val=1<<30,mini; 94 for(int i=2;i<=n;i++){//枚举从1出发的非树边(1,i),看加哪一条 95 if(tree[1][i]!=0x3f3f3f3f||a[1][i]==0x3f3f3f3f) continue; 96 //加入非树边(1,i),删去树边(fx[i],fy[i]) 97 if(a[1][i]-tree[fx[i]][fy[i]]=0) return false;
103 ans+=min_val;
104 tree[1][mini]=tree[mini][1]=a[1][mini];
105 tree[fx[mini]][fy[mini]]=tree[fy[mini]][fx[mini]]=0x3f3f3f3f;//删去原边，增加新边
106 f[mini]=a[1][mini];
107 fx[mini]=1,fy[mini]=mini;
108 v[1]=true;
109 dp(mini);//重新计算以mini为根的子树的dp状态
110 return true;
111 }
112
113 int main(){
114 read();
115 prim_for_all_comp();
116 memset(v,0,sizeof(v));
117 dp(1);
118 while(deg<s){
119 if(!solve()) break;
120 deg++;
121 }
122 printf("Total miles driven: ");
123 cout<<ans<<endl;
124 }