题意：一个 NN 个点 MM 条边的无向图，求无向图的最小生成树，且满足 11 号节点的度数不超过给定整数 SS。

经典的最小度限制生成树问题，可以参考这位大佬的博客。

首先去掉 11 号节点，则图会分成几个连通块，把每个连通块的最小生成树求出来，累计答案；

然后在每个连通块中选出一个节点 pp ，使得无向边 (1,p)(1,p) 的权值尽量小；

设连通块个数为 TT 个，这时我们就得到了一个 TT 度的最小生成树，考虑改动 S−TS-T 条边，使答案更优。

对于每个从 11 号节点出发的无向边 (1,x)(1,x)，边权为 zz，如果这条边不在最小生成树中，则一定会与其中一个连通块构成环，寻找在连通块中，xx 到 11 路径上最大的边，边权为 ww，在所有连通块中找到 w−zw-z 最大的节点 x0x_0，如果 x0x_0 对应的 w0−z0>0w_0-z_0>0，就用 (1,x0)(1,x_0) 替换这条边，答案就会变小。

重复这一步 S−TS-T 次，或者直到 w0−x0≤0w_0-x_0\leq0，就得到了最小生成树。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<string>
#include<map>
using namespace std;
#define INF 1000000000
#define MAXN 105
struct node{int x,y,v;}e[MAXN*MAXN],dp[MAXN];
int n(1),m,K,oo,ans,md,Min[MAXN],temp[MAXN],f[MAXN],a[MAXN][MAXN],check[MAXN][MAXN];
string s;
map<string,int> Map;
inline int read()
{
    int x=0,f=1;  char ch=getchar();
    while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
    while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
    return x*f;
}
bool cmp(node a,node b)  {return a.v<b.v;}
int cal()  {if(Map.find(s)==Map.end())  Map[s]=++n;  return Map[s];}
int find(int x)  {return f[x]==x?x:f[x]=find(f[x]);}
void init()
{
    m=read();  Map["Park"]=1;
    memset(a,-1,sizeof(a));
    memset(Min,10,sizeof(Min));
    oo=Min[0];
    for(int i=1;i<=m;i++)
    {
        cin>>s;  e[i].x=cal();
        cin>>s;  e[i].y=cal();
        e[i].v=read();
        if(a[e[i].x][e[i].y]==-1)  a[e[i].y][e[i].x]=a[e[i].x][e[i].y]=e[i].v;
        else a[e[i].x][e[i].y]=a[e[i].y][e[i].x]=min(a[e[i].x][e[i].y],e[i].v);
    }
    K=read();
}//处理字符串，建图
void kruskal()
{
    for(int i=1;i<=n;i++)  f[i]=i;
    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        if(e[i].x==1||e[i].y==1)  continue;
        int x=find(e[i].x),y=find(e[i].y);
        if(x==y)  continue;
        check[e[i].x][e[i].y]=check[e[i].y][e[i].x]=1;
        f[y]=x;
        ans+=e[i].v;
    }
}//求出除park外的最小生成树
void solve1()
{
    for(int i=2;i<=n;i++)
        if(a[i][1]!=-1)
        {
            int t=find(i);
            if(a[i][1]<Min[t])
            {
                temp[t]=i;
                Min[t]=a[i][1];
            }
        }//找到park出发到每个连通块的最小的边
    for(int i=1;i<=n;i++)
        if(Min[i]!=oo)
        {
            md++;
            check[1][temp[i]]=check[temp[i]][1]=1;
            ans+=a[1][temp[i]];
        }
}//找最小边并连接
void dfs(int x,int fa)
{
    for(int i=2;i<=n;i++)
        if(check[x][i]&&i!=fa)
        {
            if(dp[i].v==-1)
            {
                if(a[x][i]<dp[x].v)  dp[i]=dp[x];
                else dp[i].x=x,dp[i].y=i,dp[i].v=a[x][i];
            }
            dfs(i,x);
        }
}//求出从park出发到达每个连通块上最大的路径权值
void solve2()
{
    for(int i=md+1;i<=K;i++)
    {
        memset(dp,-1,sizeof(dp));  dp[1].v=-INF;
        for(int j=2;j<=n;j++)  if(check[1][j])  dp[j].v=-INF;
        dfs(1,-1);  int t=0,minn=INF;
        for(int j=2;j<=n;j++)
            if(a[1][j]!=-1&&a[1][j]-dp[j].v<minn)
            {
                minn=a[1][j]-dp[j].v;
                t=j;
            }
        if(minn>=0)  break;
        check[1][t]=check[t][1]=1;
        int x=dp[t].x,y=dp[t].y;
        check[x][y]=check[y][x]=0;
        ans+=minn;
    }
}//查找是否可以用其他park开始的边替换最大的边，更新答案
int main()
{
    init();
    kruskal();
    solve1();
    solve2();
    printf("Total miles driven: %d\n",ans);
    return 0;
}