#include <bits/stdc++.h>
using namespace std;

const int N = 25, inf = 0x3f3f3f3f;

int g[N][N], dist[N];
int tr[N][N], pre[N]; // tr最小生成树的矩阵，pre[y] = x: (x - > y) tr[y][pre[y]];
int n, m, ans, s, deg;
int f[N], fx[N], fy[N]; // 以某个点为子树的树边的最大值为f[i], 这条边连接的点为(fx[i], fy[i])
bool v[N], c[N];
vector<int> con;
unordered_map<string, int> h;

int get(string x) {
    if(!h[x]) h[x] = ++ n;
    return h[x];
}

void prim() { // 求最小生成树
    dist[con[0]] = 0;
    for(int i = 0; i < con.size(); i ++ ) {
        int x = 0;
        for(int j = 0; j < con.size(); j ++ ) 
            if(!v[con[j]] && (x == 0 || dist[x] > dist[con[j]])) x = con[j];
        v[x] = true;
        ans += dist[x];
        for(int y = 0; y < con.size(); y ++ ) 
            if(!v[con[y]] && dist[con[y]] > g[x][con[y]]) dist[con[y]] = g[x][con[y]], pre[con[y]] = x;
    }
    int mini = con[0];
    for(int i = 1; i < con.size(); i ++ ) {
        int x = con[i];
        tr[pre[x]][x] = tr[x][pre[x]] = dist[x];
        if(g[1][mini] > g[1][x]) mini = x;
    }
    deg ++ ;
    ans += g[1][mini];
    tr[1][mini] = tr[mini][1] = g[1][mini];
}

void dfs(int x) {
    c[x] = true;
    con.push_back(x);
    for(int i = 2; i <= n; i ++ ) 
        if(!c[i] && g[x][i] < 0x3f3f3f3f) dfs(i);
}

void con_prim() {
    memset(tr, 0x3f, sizeof tr);
    memset(dist, 0x3f, sizeof dist);
    c[1] = true;
    for(int i = 2; i <= n; i ++ ) {
        if(!c[i]) {
            con.clear();
            dfs(i);
            prim();
        }
    }
}

void dp(int x) {
    c[x] = true;
    for(int y = 1; y <= n; y ++ ) 
        if(!c[y] && tr[x][y] < inf) {
            if(tr[x][y] < f[x]) {
                f[y] = f[x];
                fx[y] = fx[x], fy[y] = fy[x];
            }
            else {
                f[y] = tr[x][y];
                fx[y] = x, fy[y] = y;
            }
            dp(y);
        }
    c[x] = false;
}

bool solve() { //  删除输边，加非树边的操作
    int min_edge = inf, mini;
    for(int i = 2; i <= n; i ++ ) {
        if(tr[1][i] < 0x3f3f3f3f || g[1][i] == inf) continue;
        if(g[1][i] - f[i] < inf && min_edge > g[1][i] - f[i]) {
            min_edge = g[1][i] - f[i];
            mini = i;
        }
    }
    if(min_edge >= 0) return false;
    ans += min_edge;
    deg ++ ;
    tr[1][mini] = tr[mini][1] = g[1][mini];
    tr[fx[mini]][fy[mini]] = tr[fy[mini]][fx[mini]] = inf;
    f[mini] = g[1][mini];
    fx[mini] = 1, fy[mini] = mini;
    dp(mini);
    return true;
}

int main() {
    cin >> m;
    get("Park");
    memset(g, 0x3f, sizeof g);
    for(int i = 0; i < m; i ++ ) {
        int x, y, z;
        string a, b;
        cin >> a >> b >> z;
        x = get(a), y = get(b);
        g[x][y] = g[y][x] = min(g[x][y], z);
    }
    cin >> s;
    con_prim(); // O(n ^ 2)
    memset(c, 0, sizeof c);
    dp(1); // 以某个点为根的子树的树边的最大值
    while(deg < s) { // O(n ^ 4)
        if(!solve()) break;
    }
    cout << "Total miles driven: " << ans << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int N = 25, inf = 0x3f3f3f3f;

int g[N][N], dist[N];
int tr[N][N], pre[N]; // tr最小生成树的矩阵，pre[y] = x: (x - > y) tr[y][pre[y]];
int n, m, ans, s, deg;
bool v[N];
unordered_map<string, int> h;

int get(string x) {
    if(!h[x]) h[x] = ++ n;
    return h[x];
}

void prim() { // 求最小生成树
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for(int i = 0; i < n; i ++ ) {
        int x = 0;
        for(int j = 1; j <= n; j ++ ) 
            if(!v[j] && (x == 0 || dist[x] > dist[j])) x = j;
        v[x] = true;
        ans += dist[x];
        for(int y = 1; y <= n; y ++ ) 
            if(!v[y] && dist[y] > g[x][y]) dist[y] = g[x][y], pre[y] = x;
    }
    memset(tr, 0x3f, sizeof tr);
    for(int x = 1; x <= n; x ++ ) {
        if(pre[x] == 1) deg ++ ;
        tr[pre[x]][x] = tr[x][pre[x]] = dist[x];
    }
}

void dfs(int x) {
    v[x] = true;
    for(int i = 2; i <= n; i ++ ) 
        if(!v[i] && tr[x][i] < 0x3f3f3f3f) dfs(i);
}

int find_min(int &x, int &y) { // 找最小边
    int min_edge = 0x3f3f3f3f;
    for(int i = 2; i <= n; i ++ ) if(!v[i])
        for(int j = 2; j <= n; j ++ ) if(v[j]) 
            if(min_edge > g[i][j]) {
                min_edge = g[i][j];
                x = i, y = j;
            }
    return min_edge;
}

void solve() { //  删除输边，加非树边的操作
    int min_edge = inf, minx, miny, mini;
    for(int i = 2; i <= n; i ++ ) {
        if(tr[1][i] == 0x3f3f3f3f) continue;
        memset(v, 0, sizeof v);
        v[1] = true;
        dfs(i);
        int x, y;
        int add_edge = find_min(x, y);
        if(add_edge < inf && min_edge > add_edge - tr[1][i]) {
            minx = x, miny = y, mini = i;
            min_edge = add_edge - tr[1][i];
        }
    }
    ans += min_edge;
    deg -- ;
    tr[1][mini] = tr[mini][1] = inf;
    tr[minx][miny] = tr[miny][minx] = g[minx][miny];
}

int main() {
    cin >> m;
    get("Park");
    memset(g, 0x3f, sizeof g);
    for(int i = 0; i < m; i ++ ) {
        int x, y, z;
        string a, b;
        cin >> a >> b >> z;
        x = get(a), y = get(b);
        g[x][y] = g[y][x] = min(g[x][y], z);
    }
    cin >> s;
    prim();
    while(deg > s) {
        solve();
    }
    cout << "Total miles driven: " << ans << endl;
    return 0;
}

然后由于边数量不超过200，点不超过20，所以我们可以用比较暴力的方式完成这道题 O(n^4)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 33, INF = 0x3f3f3f3f;

unordered_map<string, int> mapp;
int n, m, ans, f[N], g[N][N], d[N], v[N], cnt, sum;
int pre[N]; // pre[x] = y; 指x点通过y点连接到生成树中 
int tr[N][N]; // 记录一颗生成树，内部是矩阵的形式，[i][j]即i和j两点在树中直接相连 

int get(string a){
	if(!mapp[a]) mapp[a] = ++ n;
	return mapp[a];
}

void prim(){
	memset(v, 0, sizeof v);
	memset(d, 0x3f, sizeof d);
	memset(tr, 0x3f, sizeof tr);
	d[1] = 0;
	
	for(int i=0;i<n;i++){
		int x = 0;
		for(int j=1;j<=n;j++) 
		if(!v[j] && (!x || d[x] > d[j])) x = j;
		
		v[x] = 1;
		ans += d[x];
		
		for(int y=2;y<=n;y++)
		if(!v[y] && d[y] > g[x][y]) d[y] = g[x][y], pre[y] = x; 
	}
	
	// 生成最小树之后建立tr数组，表示树中哪两个点之间是直接连接的
	for(int i=1;i<=n;i++){
		if(pre[i] == 1) cnt ++;
		tr[pre[i]][i] = tr[i][pre[i]] = d[i];
	}
}

void dfs(int x){
	v[x] = 1;
	for(int i=2;i<=n;i++) 
	if(!v[i] && tr[x][i] < INF) dfs(i);
    // 每次找到能拓展的并且还没有打标记的点，以此打标记并向下拓展
    // 这样就把所有的小树的点打上标记了
}

int find_min(int &x, int &y){
	int minn = INF;
	for(int i=2;i<=n;i++) if(v[i]) // 一个在子树
	for(int j=2;j<=n;j++) if(!v[j]) // 一个在主树
	if(g[i][j] < minn){
		minn = g[i][j];
		x = i; y = j;
	} return minn;
}

void work(){ // 删除1号点的入边，加新的树边的操作
    // minn是改边后的ans增量，mii与1号点之间的边是要删的
    // mix与miy之间的边是要连接起来的
	int minn = INF, mix, miy, mii;
	for(int i=2;i<=n;i++){ 
		if(tr[1][i] == INF) continue;
		// 此处continue是保证在生成树中起点直接连接到这个i号点，
		// 也代表这我们可以删除这个1号点的这个入边
		// 因为删除了一个树边，原来的生成树会分裂为两个树，
		// 一棵是以1号点为根的主树，另一棵树是以i号点为根，且不经过1号点的小树
		
		memset(v, 0, sizeof v); // 重置打标记数组，打上标记的为小树的点
		// 此处的小树指的是以i号点为根，不经过1号点形成的子树，
		// 待会在整个小树里面所有的点和原树中所有的点中找到最短的一条边，
		// 使两棵树重新连接，也就重新构成了一个图的生成树
        v[1] = true; // 因为我们不能经过1号点，所以先把1号点打上标记
        dfs(i); // 遍历现在生成树中以i号点为根且不经过1号点的子树的点，打上标记，形成小树
		int x, y;
		int add_w = find_min(x, y); // x，y分别一个在子树，一个在主树
		
		// 因为外循环是遍历了除了1号的所有点，所以此处的处理是
		// 尽量使删边后加入的新边后ans权值增加最小，
		if(add_w < INF) if(add_w - tr[1][i] < minn){ 
			minn = add_w - tr[1][i];
			mix = x; miy = y; mii = i;
			// minn是改边后的ans增量，mii与1号点之间的边是要删的
 			// mix与miy之间的边是要连接起来的
		}
	}
	// 找到最小的可以连接两棵树的边了，
	cnt --; // 删边后连接在1号点的边数量-1
	ans += minn;
	tr[1][mii] = tr[mii][1] = INF; // 删除在tr数组中的i号点与1号点之间的边
	tr[mix][miy] = tr[miy][mix] = g[mix][miy]; // 连接新的边，构成新的生成树
}

int main(){
	memset(g, 0x3f, sizeof g);
	
	cin>>m;
	get("Park"); // 这样子就默认park是1号点了，非常好的小操作，不像我个byd，写一堆构式
	for(int i=0;i<m;i++){
		string a, b;
		int x, y, z;
		cin>>a>>b>>z;
		x = get(a), y = get(b);
		g[x][y] = g[y][x] = min(g[x][y], z);
	} cin>>sum;
	
	prim(); // O(n^2)
	while(cnt > sum) work(); // O(n^4)
	printf("Total miles driven: %d\n",ans);
	return 0;
}

当然也有O(n^2)的做法

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 22, M = 222, INF = 0x3f3f3f3f;

int ans, dep;
int n, m, s;
bool v[N], c[N]; 
int f[N], fx[N], fy[N]; // 都是dp找1号节点到某节点的时候最长的树边的，f是边权，fx和fy都是整个边对应的两个点 
int g[N][N], tr[N][N], pre[N], d[N]; // tr是生成树内点的矩阵, pre[y]=x是指在树内通过x点访问y点 
unordered_map<string, int> mapp;

vector<int> cno; // 每次生成树需要的点都存在cno里面 

int get(string x) {
    if(!mapp[x]) mapp[x] = ++ n;
    return mapp[x];
}

void prim(){
	// 由于连通块生成树不会出现重复点编号，
	// 所以我们在这里就不memset，v和d数组了 
	//下面就是标准prim流程了，不过注意用的点是cno内部存的点 
	d[cno[0]] = 0; 
	int n = cno.size();
	for(int i=0;i<n;i++){
		int x = 0;
		for(int j=0;j<n;j++) if(!v[cno[j]])
		if( !x || d[x] > d[cno[j]] ) x = cno[j];
		
		v[x] = 1;
		ans += d[x]; // 由于连通块的最小生成树最后也是整个图的最小生成树
		// 所以直接在这里把ans加上 
		
		for(int y=0;y<n;y++) if(!v[cno[y]])
		if(d[cno[y]] > g[x][cno[y]]) d[cno[y]] = g[x][cno[y]], pre[cno[y]] = x;
	}
	
	// 接下来要在这个连通块生成树内部找一个点与1号点(也就是park)相连接 
	// 顺便建立生成树矩阵，也就是tr数组 
	int mini = cno[0]; // 首先cno[0]肯定是能与1号点连接的，但是不一定是边权最小的 
	for(int i=1;i<n;i++){
		int x = cno[i];
		if(g[1][mini] > g[1][x]) mini = x; // 找到最小边权的连接点 
		tr[x][pre[x]] = tr[pre[x]][x] = d[x];
	}
	dep ++; // 1号点的入度+1
	ans += g[1][mini]; // 整颗生成树的ans上也加上这个边权 
//	pre[mini] = 1; // 为什么pre没改上？ // 因为，对于mini点的pre，在上面一定是写过一次值的了 
	tr[mini][1] = tr[1][mini] = g[1][mini]; // 矩阵也加上
} 

void dfs(int x){
	c[x] = 1;
	cno.push_back(x); // 待会生成连通块的树的时候要用 
	for(int i=2;i<=n;i++) 
	if(!c[i] && g[x][i] < INF) dfs(i); // 拓展连通块中其他的点 
}

void cno_prim(){
	memset(d, 0x3f, sizeof d);
	memset(tr, 0x3f, sizeof tr);
	c[1] = 1;
	
	// 在去除1号节点后，图的最小生成树会分成几个连通块
	// 我们先把1号点打上标记，再跑dfs就一定不会经过1号点，
	// 这个时候跑dfs打标记，就会形成几个连通块
	// 然后对于每个连通块，我们跑一个最小生成树，
	//从每个连通块中找一个点，与1号点相连接，当然边权尽量选最小的 
	
	for(int i=2;i<=n;i++){
		if(c[i]) continue;
		cno.clear();
		dfs(i); // 通过dfs，这个连通块已经打完标记了 
		prim(); // 开始生成连通块的最小生成树 
	}
}

void dp(int x){
	c[x] = 1; // 给x点打上标记，因为我们要保证的是从1号点出发，向下搜索 
	// 那么对于待会要dp的y点，y点作为x的子节点，不能往上走，只能往下搜索
	// 所以打上标记，到时候continue就好了 
	
	for(int y=1;y<=n;y++){
		if(c[y] || tr[x][y] == INF) continue; // 如果是上游的节点，或者不连通continue 
		if(tr[x][y] < f[x]){ // 说明x，y之间直接相连，且y为直接相连的子节点 
		// 但是从1号点出发到x有一条树边是大于两者之间的边权的，那么也要顺便更新一下y的f数组群 
			f[y] = f[x];
			fy[y] = fy[x]; fx[y] = fx[x]; 
		}else{ // 说明x，y之间的边权是≥f的，我们从1号点出发到y点的最长边权就是x -> y这个边 
			f[y] = tr[x][y];
			fx[y] = x; fy[y] = y;
		} dp(y); // 继续向下拓展 
	} c[x] = 0; // 回溯 
}

bool work(){ // 进行删除树边，增加一个新的边的操作
	int minn = INF, mini;
	for(int i=2;i<=n;i++){
		if(tr[1][i] < INF || g[1][i] == INF) continue; // 在树中与1号有直接相连的边不能删，
		// 因为现在已经是入度为dep的最小生成树了，我们现在可以选择再增加入度，减小生成树的大小，
		// 但是这个点是直接与1号点相连的，不能删
		// || 或者在图中不与1号相连通，是肯定无法建立新的边的，所以也要continue掉
		if(minn > g[1][i] - f[i]){
			minn = g[1][i] - f[i];
			mini = i;
		}
	} if(minn >= 0) return 1;
	
	dep ++;
	ans += minn;
	tr[1][mini] = tr[mini][1] = g[1][mini];
	tr[fx[mini]][fy[mini]] = tr[fy[mini]][fx[mini]] = INF;
	
	f[mini] = g[1][mini];
	fx[mini] = 1, fy[mini] = mini;
	
	dp(mini); // 因为从mini点这里删除了一条原来生成树的一条边，加了新的边，
	// 那么所有跟在mini点后面的点(mini下面所有的子节点)的f数组群都要更新掉 
	return 0;
} 

int main(){
	cin>>m;
	get("Park"); // 小小巧妙的操作，这样子PARK就是1号节点了，后面写代码就方便很多
	memset(g, 0x3f, sizeof g);
	for(int i=0;i<m;i++){
		string a, b;
		int x, y, z;
		cin>>a>>b; cin>>z;
		x = get(a), y = get(b);
		g[x][y] = g[y][x] = min(g[x][y], z);
	}
	cin>>s;
	cno_prim(); // n^2
	memset(c, 0, sizeof c);
	dp(1); // 遍历整颗生成树找从x点到1号点的树上路径中，最大的边权 
	
	while(dep < s) if(work()) break;
	printf("Total miles driven: %d\n",ans);
	return 0;
}