一群小丑演员，以其出色的柔术表演，可以无限量的钻进同一辆汽车中，而闻名世界。现在他们想要去公园玩耍，但是他们的经费非常紧缺。他们将乘车前往公园，为了减少花费，他们决定选择一种合理的乘车方式，可以使得他们去往公园需要的所有汽车行驶的总公里数最少。为此，他们愿意通过很多人挤在同一辆车的方式，来减少汽车行驶的总花销。由此，他们可以很多人驾车到某一个兄弟的家里，然后所有人都钻进一辆车里，再继续前进。公园的停车场能停放的车的数量有限，而且因为公园有入场费，所以一旦一辆车子进入到公园内，就必须停在那里，不能再去接其他人。现在请你想出一种方法，可以使得他们全都到达公园的情况下，所有汽车行驶的总路程最少。

输入格式
第一行包含整数n，表示人和人之间或人和公园之间的道路的总数量。接下来n行，每行包含两个字符串A、B和一个整数L，用以描述人A和人B之前存在道路，路长为L，或者描述某人和公园之间存在道路，路长为L。道路都是双向的，并且人数不超过20，表示人的名字的字符串长度不超过10，公园用“Park”表示。再接下来一行，包含整数s，表示公园的最大停车数量。你可以假设每个人的家都有一条通往公园的道路。

输出格式
输出“Total miles driven: xxx”，其中xxx表示所有汽车行驶的总路程。

输入样例：
10
Alphonzo Bernardo 32
Alphonzo Park 57
Alphonzo Eduardo 43
Bernardo Park 19
Bernardo Clemenzi 82
Clemenzi Park 65
Clemenzi Herb 90
Clemenzi Eduardo 109
Park Herb 24
Herb Eduardo 79
3
输出样例：
Total miles driven: 183

看大佬的题解（https://www.acwing.com/solution/acwing/content/2488/）后写的，注意题目中虽说人数不超过20但oj上有的数据超过20了。

#include <bits/stdc++.h>using namespace std;
map<string, int> name_num;
struct {int x, y;
} max_locate[1000];
int center, s;
vector<int> vis[100];
int point_set[100];
int judge[100];
int minimal_spanning_tree[100][100], tab[100][100];
map<int, int> max_size;
int num, n, part_count = 1;struct node {int x, y, z;bool operator<(const node &a)const {return z < a.z;}
} edge[1000];int pic[100][100];int gets(int x) {return point_set[x] == x ? x : (point_set[x] = gets(point_set[x]));
}void read() {cin >> n;name_num["Park"] = 1;num = 2;for (int i = 0; i < n; i++) {string A, B;cin >> A >> B;if (!name_num[A]) {name_num[A] = num;num++;}if (!name_num[B]) {name_num[B] = num;num++;}edge[i].x = name_num[A];edge[i].y = name_num[B];cin >> edge[i].z;pic[name_num[A]][name_num[B]] = edge[i].z;pic[name_num[B]][name_num[A]] = edge[i].z;}for (int i = 1; i < num; i++)point_set[i] = i;cin >> s;
}void dfs(int x) {judge[x] = 1;vis[part_count].push_back(x);for (int i = 2; i < num; i++)if (judge[i] != 1 && pic[x][i] != 0 && gets(i) != center) {point_set[i] = center;dfs(i);}
}void bfs() {max_size[1] = 0;queue<int> q;q.push(1);while (!q.empty()) {int x = q.front();q.pop();for (int i = 1; i < num; i++)if (minimal_spanning_tree[x][i] && tab[x][i] == 0) {if (minimal_spanning_tree[x][i] > max_size[x]) {max_size[i] = minimal_spanning_tree[x][i];max_locate[i].x = x;max_locate[i].y = i;} else {max_size[i] = max_size[x];max_locate[i].x = max_locate[x].x;max_locate[i].y = max_locate[x].y;}tab[x][i] = 1;tab[i][x] = 1;q.push(i);}}
}void divide_the_area() {for (int i = 2; i < num; i++)if (judge[i] == 0) {center = i;dfs(i);part_count++;}
}int kruskal() {int ans = 0;for (int i = 1; i < num; i++)point_set[i] = i;sort(edge, edge + n);for (int i = 0; i < n; i++) {int x = gets(edge[i].x), y = gets(edge[i].y);if (x == y || x == 1 || y == 1)continue;else {point_set[y] = x;ans += edge[i].z;minimal_spanning_tree[edge[i].y][edge[i].x] = edge[i].z;minimal_spanning_tree[edge[i].x][edge[i].y] = edge[i].z;}}return ans;
}void work() {divide_the_area();int ans = kruskal();for (int i = 1; i < part_count; i++) {int size = vis[i].size(), min0 = 0x3f3f3f3f, min_j = 0;for (int j = 0; j < size; j++) {if (pic[1][vis[i][j]] != 0 && pic[1][vis[i][j]] < min0) {min0 = pic[1][vis[i][j]];min_j = vis[i][j];}}ans += min0;minimal_spanning_tree[1][min_j] = min0;minimal_spanning_tree[min_j][1] = min0;}while (s > part_count - 1) {s--;int max0 = 0, max_i = 0;bfs();for (int i = 1; i < num; i++)for (int j = 1; j < num; j++)tab[i][j] = 0;for (int i = 2; i < num; i++) {if ((max_size[i] - pic[i][1] > max0) && pic[i][1] && minimal_spanning_tree[i][1] == 0) {max0 = max_size[i] - pic[i][1];max_i = i;}}if (max0 == 0)break;else {ans -= max0;minimal_spanning_tree[max_i][1] = pic[max_i][1];minimal_spanning_tree[1][max_i] = pic[1][max_i];minimal_spanning_tree[max_locate[max_i].x][max_locate[max_i].y] = 0;minimal_spanning_tree[max_locate[max_i].y][max_locate[max_i].x] = 0;}}cout << "Total miles driven: " << ans;
}int main() {read();work();return 0;
}

3个月后，不看题解，用自己的想法重新写了一遍

#include<bits/stdc++.h>using namespace std;
const int N = 25, M = 1e3;
int cnt, cn;
int pic[N][N];
struct {int x, y, z;
} mxe[N];struct node {int x, y, z;bool operator<(const node &a) const {return z < a.z;}
} e1[M];vector<pair<int, int>> e2;bool cmp(const pair<int, int> a, const pair<int, int> b) {return a.second < b.second;
}int par;
int n, s;
int ans;
bool v[N];
set<pair<int, int>> se;
map<string, int> mp;
int fa[N];int get(int x) {return fa[x] == x ? x : (fa[x] = get(fa[x]));
}void read() {cin >> n;string s1, s2;int z;for (int i = 1; i <= n; i++) {cin >> s1 >> s2 >> z;if (!mp[s1])mp[s1] = ++cnt;if (!mp[s2])mp[s2] = ++cnt;if (s1 == "Park")e2.emplace_back(mp[s2], z);else if (s2 == "Park")e2.emplace_back(mp[s1], z);else {e1[++cn].x = mp[s1];e1[cn].y = mp[s2];e1[cn].z = z;}}cin >> s;
}void kruskal() {memset(pic, 0x3f, sizeof(pic));sort(e1 + 1, e1 + 1 + cn);for (int i = 1; i <= cnt; i++)fa[i] = i;for (int i = 1; i <= cn; i++) {int x = get(e1[i].x), y = get(e1[i].y);if (x == y)continue;fa[x] = y;ans += e1[i].z;pic[e1[i].x][e1[i].y] = pic[e1[i].y][e1[i].x] = e1[i].z;}
}void bfs1(int sta) {queue<int> q;v[sta] = true;q.push(sta);while (!q.empty()) {int x = q.front();q.pop();for (int y = 1; y <= cnt; y++)if (!v[y] && pic[x][y] != 0x3f3f3f3f) {v[y] = true;q.push(y);}}
}void bfs2() {queue<int> q;memset(v, false, sizeof(v));for (int i = 1; i <= cnt; i++)mxe[i].z = 0;v[par] = true;q.push(par);while (!q.empty()) {int x = q.front();q.pop();for (int y = 1; y <= cnt; y++)if (!v[y] && pic[x][y] != 0x3f3f3f3f) {v[y] = true;if (pic[x][y] < mxe[x].z) {mxe[y].x = mxe[x].x;mxe[y].y = mxe[x].y;mxe[y].z = mxe[x].z;} else {mxe[y].x = x;mxe[y].y = y;mxe[y].z = pic[x][y];}q.push(y);}}
}void solve() {par = mp["Park"];sort(e2.begin(), e2.end(), cmp);for (auto &it:e2)if (!v[it.first]) {bfs1(it.first);pic[par][it.first] = it.second;pic[it.first][par] = it.second;ans += it.second;s--;} else se.insert(it);while (s-- && !se.empty()) {bfs2();int mx = -0x3f3f3f3f;pair<int, int> temp;for (auto &it:se)if (mxe[it.first].z - it.second > mx) {mx = mxe[it.first].z - it.second;temp = it;}if (mx <= 0)break;se.erase(temp);ans -= mx;pic[temp.first][par] = pic[par][temp.first] = temp.second;pic[mxe[temp.first].x][mxe[temp.first].y] = pic[mxe[temp.first].y][mxe[temp.first].x] = 0x3f3f3f3f;}cout << "Total miles driven: " << ans;
}int main() {read();kruskal();solve();return 0;
}