题目链接：https://ac.nowcoder.com/acm/contest/1056/B
书P368

①：Kruskal算法
https://blog.nowcoder.net/n/012b92baab1f4ee59bb17b9bcb8dadb4
本题中用这个算法求去掉根节点1后的最小生成树

②贪心策略
本题要找满足1号节点度数不超过S的最小生成树
如果去掉节点1后，连通块个数为T大于S，则无解。接下来我们从每个连通块中寻找与节点1边长最短的点，加入生成树
然后还可以改S-T条边，每条（1,x）的边，我们找到与1的本身路径最长的一条减去（1,x）的长度，那么整个生成树长度就减少了

/*#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=100;

struct rec
{
    int x,y,z;
}edge2[maxn];//edge2为去掉根节点1后的最小生成树

int edge3[maxn][maxn],fa[maxn],edge1[maxn],t[maxn],d[maxn];//fa为并查集，edge1为1到各个点的边长度，t为判断当前边是否已经加入，d为scan时避免重复搜点

int n,m,ans=0,to=0,minn,dian,s;//minn是scan时最小边长度，dian是与1距离最近的点，s是1的最大度数 

bool operator <(rec f1,rec f2)
{
    return f1.z<f2.z;
}

int get(int x)//搜索所在集合
{
    if(x==fa[x])
    {
        return x;
    }
    return fa[x]=get(fa[x]);
}

int scan(int x)//搜索每个集合的点与1的最短边 
{
    if(edge1[x]<minn)
    {
        minn=edge1[x];
        dian=x;
    }
    if(x==fa[x])
    {
        return x;
    }
    return fa[x]=get(fa[x]);
}

int dfs(int u,int maxb)
{

    for(int i=1;i<=n;i++)
    {
        if(edge3[u][i]!=-1&&d[i]==0)
        {
            dfs(i,max(maxb,edge3[u][i]));
        }
    }
}

void init()
{
    memset(edge1,INF,sizeof(edge1));
    memset(edge3,-1,sizeof(edge3));
}

int main()
{
    cin>>n>>m;
    init();
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        if(x!=1&&y!=1)
        {
            edge2[i].x=x;
            edge2[i].y=y;
            edge2[i].z=z;
            to++;
        }
        else
        {
            edge1[max(x,y)]=z;
        }
        edge3[i].x=x;edge3[i].y=y;edge3[i].z=z;
    }
    cin>>s;

    sort(edge2+1,edge2+1+to);//按权值从小到大排序

    for(int i=1;i<=n;i++)
    {
        fa[i]=i;
    }

    int shu=n-1;
    for(int i=1;i<=to;i++)
    {
        int x=get(edge2[i].x);
        int y=get(edge2[i].y);
        if(x==y)
        {
            continue;
        }
        edge3[edge2[i].x][edge2[i].y]=z; edge3[edge2[i].y][edge2[i].x]=z;
        fa[x]=y;//合并集合
        shu--;
    }
    if(shu>s)
    {
        cout<<"can not be a tree!!!"<<endl;
        return 0;
    }

    for(int i=2;i<=n;i++)
    {
        if(d[i]==0)
        {
            minn=INF;
            scan(i);
            edge3[1][dian]=minn; edge3[dian][1]=minn;
            t[dian]=1;
        }
    }

    memset(d,0,sizeof(d));
    d[1]=1;
    dfs(1,-1);

    cout<<ans<<endl;
    return 0;
}*/

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <string>

#define INF 0x3f3f3f3f
#define MAXN 22

using namespace std;

struct Edge{
    int u, v, d;
    Edge() {}
    Edge(int a, int b, int c) : u(a), v(b), d(c) {}
    bool operator < (const Edge &e) const {
        return d < e.d;
    }
};

int n, m, k;
int cnt;
int ans;
int parent[MAXN]; // 并查集
map<string, int> nodes;
vector<Edge> edges;
Edge dp[MAXN];
int g[MAXN][MAXN];
bool tree[MAXN][MAXN]; // tree[i][j]=true表示<i, j>这条边在最小生成树中
int minEdge[MAXN];

int find(int p) {
    if (p == parent[p]) return parent[p];
    return parent[p] = find(parent[p]);
}

void un(int p, int q) {
    parent[find(p)] = find(q);
}

void kruskal() {
    sort(edges.begin(), edges.end());
    for (int i = 0; i < edges.size(); i++) {
        int p = edges[i].u;
        int q = edges[i].v;
        if (p == 1 || q == 1) continue; // 忽略根节点
        if (find(p) != find(q)) {
            un(p, q);
            tree[p][q] = tree[q][p] = 1;
            ans += edges[i].d;
        }
    }
}

void dfs(int cur, int pre) {
    for (int i = 2; i <= cnt; i++) {
        if (i == pre || !tree[cur][i]) continue;
        if (dp[i].d == -1) {
            if (dp[cur].d > g[cur][i]) dp[i] = dp[cur];
            else {
                dp[i].u = cur;
                dp[i].v = i;
                dp[i].d = g[cur][i];
            }
        }
        dfs(i, cur);
    }
}

void solve() {
    int keyPoint[MAXN];
    for (int i = 2; i <= cnt; i++) {
        if (g[1][i] != INF) {
            // 点i在哪颗最小生成树中
            int color = find(i);
            // 每颗最小生成树中距离根节点最近的点与根节点的距离
            if (minEdge[color] > g[1][i]) {
                minEdge[color] = g[1][i];
                keyPoint[color] = i;
            }
        }
    }
    for (int i = 1; i <= cnt; i++) {
        if (minEdge[i] != INF) {
            m++;
            tree[1][keyPoint[i]] = tree[keyPoint[i]][1] = 1;
            ans += g[1][keyPoint[i]];
        }
    }
    // 由i-1度生成树得i度生成树
    for (int i = m + 1; i <= k; i++) {
        memset(dp, -1, sizeof(dp));
        dp[1].d = -INF;
        for (int j = 2; j <= cnt; j++)
            if (tree[1][j]) dp[j].d = -INF;
        dfs(1, -1); // dp预处理
        int idx, minnum = INF;
        for (int j = 2; j <= cnt; j++) {
            if (minnum > g[1][j] - dp[j].d) {
                minnum = g[1][j] - dp[j].d;
                idx = j;
            }
        }
        if (minnum >= 0) break;
        tree[1][idx] = tree[idx][1] = 1;
        tree[dp[idx].u][dp[idx].v] = tree[dp[idx].v][dp[idx].u] = 0;
        ans += minnum;
    }
}

void init() {
    memset(g, 0x3f, sizeof(g));
    memset(tree, 0, sizeof(tree));
    memset(minEdge, 0x3f, sizeof(minEdge));
    m = 0;
    cnt = 1;
    ans = 0;
    nodes["Park"] = 1;
    for (int i = 0; i < MAXN; i++)
        parent[i] = i;
}

int main() {
    scanf("%d", &n);
    string s1, s2;
    int d;
    init();
    for (int i = 1; i <= n; i++) {
        cin >> s1 >> s2 >> d;
        if (!nodes[s1]) nodes[s1] = ++cnt;
        if (!nodes[s2]) nodes[s2] = ++cnt;
        int u = nodes[s1], v = nodes[s2];
        edges.push_back(Edge(u, v, d));
        g[u][v] = g[v][u] = min(g[u][v], d);
    }
    scanf("%d", &k);
    kruskal(); // 忽略根节点先计算一次最小生成树，此时得到一个森林
    solve();
    printf("Total miles driven: %d\n", ans);
    return 0;
}

来源：https://blog.csdn.net/u011265346/article/details/42919889