题目链接：https://vjudge.net/problem
题意：
给各位看一下题意，算法详解看下面大佬博客吧，写的很好。
参考博客：最小k度限制生成树 - chty - 博客园 https://www.cnblogs.com/chty/p/5934669.html
代码：
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<vector>
#include<set>
#include<cstdio>
#include<string>
#include<deque>
using namespace std;
typedef long long LL;
#define eps 1e-8
#define INF 0xffffff
#define maxn 105
map<string,int>mp;
struct node{
int u,v,w,next;
}edge[maxn*maxn],dp[maxn];
int n,m,k,t,id,cnt;
int sum,md;//边权和，最小的度
int pre[maxn],check[maxn][maxn],dis[maxn][maxn],minn[maxn],temp[maxn];
//集合的祖先，check[i][j]表示在生成树里面i和j是否有边相连，dis[i][j]表示i和j之间的边权
//minn[i]表示以点i为祖先节点的点集里和树根直接相连的最小边权，temp记录这个点的下标
void init(){
id=;
sum=md=;
memset(check,,sizeof(check));
;i<maxn;i++){
;j<maxn;j++){
dis[i][j]=INF;
}
}
;i<maxn;i++)
pre[i]=i;
}
void read(){
init();
cin>>m;
string u,v;
int w;
mp[;
;i<=m;i++){
cin>>u>>v>>w;
)
mp[u]=++id;
)
mp[v]=++id;
edge[i].u=mp[u];
edge[i].v=mp[v];
edge[i].w=w;
dis[mp[u]][mp[v]]=dis[mp[v]][mp[u]]=min(dis[mp[u]][mp[v]],w);
}
cin>>k;
}
bool cmp(node a,node b){
return a.w<b.w;
}
int find(int a){
return pre[a]==a?a:pre[a]=find(pre[a]);
}
void cal_m_tree(){//计算度为m的最小生成树
sort(edge+,edge++m,cmp);
;i<=m;i++){
int u=edge[i].u;
int v=edge[i].v;
int w=edge[i].w;
||v==)
continue;
int x=find(u);
int y=find(v);
if(x!=y){
pre[x]=y;
sum+=w;//把边权加上
check[u][v]=check[v][u]=;//标记链接u，v的边已经走过
}
}
;i<=id;i++)
minn[i]=INF;
;i<=id;i++){//寻找各个连通块里面和树根直接相连的最小边
int f=find(i);
]!=INF&&minn[f]>dis[i][]){//更新连通快f的值并记录点的下标
minn[f]=dis[i][];//
temp[f]=i;
}
}
;i<=id;i++){
if(minn[i]!=INF){
md++;//度增加
sum+=minn[i];//权值增加
check[][temp[i]]=check[temp[i]][]=;//标记边
}
}
}
void DFS(int u,int fa){//用动态规划来计算从树根到生成树上每一个点的1路径上面的最大边权
//同时记录这条边所连接的两点
;i<=id;i++){
if(i==fa)
continue;
){//动态规划，到点i的最大边权dp[i].w=max{dp[u].w,dis[i][u]}
){
dp[i].w=dis[i][u];
dp[i].u=u;
dp[i].v=i;
}
else{
dp[i]=dp[u];
}
DFS(i,u);
}
}
}
void cal_k_tree(){//计算度为m+1到k的最小生成树，可以直接跳出
;i<=k;i++){
;j<=id;j++)
dp[j].w=-INF;
DFS(,-);
int ans=INF,u;//ans记录接下来度为i的生成树和之前生成树的权值之差的最小值，如果ans<0,说明还可以
//使边权变小，否则在度数增加时边权和只会变大，所以可以直接跳出
;j<=id;j++){
]==&&dis[][j]!=INF){
][j]-dp[j].w){
ans=dis[][j]-dp[j].w;
u=j;
}
}
}
)//无法增广，直接跳出
break;
int a=dp[u].u;
int b=dp[u].v;
check[a][b]=check[b][a]=;//去掉一条边
check[][u]=check[u][]=;//增加一条边
sum+=ans;//边权减少
}
}
int main()
{
read();
cal_m_tree();
cal_k_tree();
printf("Total miles driven: %d\n",sum);
;
}