将1号点从图中去掉过后，图会形成几个连通块，那么我们首先可以在这些连通块内部求最小生成树。
假设有\(tot\)个连通块，那么我们会从1号点至少选\(tot\)个出边，使得图连通。这时我们贪心地选择最小的，这应该都很好懂。
因为题目中的要求是度数不超过\(s\)，那么也就是说我们可以从1号点出发，再加入\(s-tot\)条边，因为可能这些边的边权比连通块中的某些边边权小，那么替换过后答案肯定最优。
具体替换方法为：如果当前顶点度数为\(k\)，我们现在要向\(k+1\)的度数扩展，我们肯定要枚举所有没用到过的出边，因为只会添加一条边，那么就会形成一个环。单独考虑一条边\((1,x)\)，肯定会选择将\(1\)到\(x\)路径上面边权最大的边给替换掉。那么我们可以枚举所有的情况，最后取min，就能得到\(k+1\)度的最优解。最后一次类推就行了。。。。如果向\(k+1\)度扩展得不到更优解时，直接break掉就行了。
具体思路就是这样。。。。但是代码细节稍微有点多。
因为求最小生成树时会利用到边的信息，以及最后会考虑1的每个出边，所以我先把边给标号，并且用了一个\(v[i]\)来保存\(i\)号结点所有的出边，这样就会方便一些。
细节见代码吧：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <string>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 35;
int t;
int n, s;
struct Edge{
int u, v, w;
}e[N * N];
vector <int> v[N], vec;
bool vis[N], used[N * N], check[N * N];
int tot;
ll ans ;
void dfs(int x) {
vis[x] = 1;
for(auto i : v[x]) {
int to = e[i].v, u = e[i].u;
if(to == x) to = u ;
if(to != 1 && !check[i]) {
vec.push_back(i) ;
check[i] = 1;
}
if(!vis[to] && to != 1) dfs(to) ;
}
}
bool cmp(int a, int b) {
return e[a].w < e[b].w;
}
int f[N], d[N], ee[N];
int find(int x) {
return f[x] == x ? x : f[x] = find(f[x]) ;
}
int insert(int i) {
int x = e[i].u, y = e[i].v;
int fx = find(x), fy = find(y) ;
if(fx != fy) {
f[fx] = fy;
ans += e[i].w;
used[i] = 1;
return 1;
} else return 0;
}
void dfs2(int x) {
vis[x] = 1;
for(auto i : v[x]) {
int u = e[i].u, to = e[i].v;
if(to == x) to = u;
if(!vis[to] && used[i]) {
if(e[i].w > d[x]) {
d[to] = e[i].w;
ee[to] = i;
} else {
d[to] = d[x] ;
ee[to] = ee[x] ;
}
dfs2(to) ;
}
}
}
int main() {
cin >> t;
while(t--) {
ans = 0;
//处理输入
cin >> n;
for(int i = 1; i < N; i++) v[i].clear() ;
map <string ,int> mp;
memset(check, 0, sizeof(check)) ;
memset(used, 0, sizeof(used)) ;
mp["Park"] = 1;
int num = 1;
tot = 0;
string s1, s2;
for(int i = 1; i <= n; i++) {
int dis;
cin >> s1 >> s2 >> dis;
if(mp.find(s1) == mp.end()) mp[s1] = ++num;
if(mp.find(s2) == mp.end()) mp[s2] = ++num;
e[i] = Edge{mp[s1], mp[s2], dis} ;
v[mp[s1]].push_back(i) ;
v[mp[s2]].push_back(i) ;
}
cin >> s;
//在每个连通块内求最小生成树
for(int i = 1; i < N; i++) f[i] = i;
memset(vis, 0, sizeof(vis)) ;
for(int i = 2; i <= num; i++) {
if(!vis[i]) {
vec.clear() ;
tot++;
dfs(i);
sort(vec.begin(), vec.end(), cmp) ;
for(auto i : vec) insert(i) ;
}
}
//选出最小的边让树连通
vec.clear() ;
for(auto i : v[1]) vec.push_back(i) ;
sort(vec.begin(), vec.end(), cmp) ;
int l = vec.size(), k;
for(int i = 0; i < tot; i++) {
for(k = 0; k < l; k++) {
int ok = insert(vec[k]) ;
if(ok) break ;
}
}
//贪心换边
int cnt = s - tot;
while(cnt--) {
memset(d, 0, sizeof(d)) ;
memset(vis, 0, sizeof(vis)) ;
dfs2(1);
int mn = 0, f = -1;
for(int j = 0; j < l; j++) {
int i = vec[j] ;
if(used[i]) continue ;
int x = e[i].u, y = e[i].v, to;
if(x == 1) to = y;
else to = x;
if(e[i].w - d[to] < mn) {
mn = e[i].w - d[to] ;
f = i;
}
}
if(f == -1) break ;
int i = f ;
int x = e[i].u, y = e[i].v, to;
if(x == 1) to = y;
else to = x;
used[i] = 1;
used[ee[to]] = 0;
ans += mn;
}
cout << "Total miles driven: ";
cout << ans << '\n';
if(t) cout << '\n' ;
}
return 0;
}
/*
13
Park 1 9
Park 2 10
Park 3 10
Park 4 10
Park 5 10
Park 6 10
Park 7 10
1 2 11
1 4 13
2 3 12
4 5 14
5 6 14
6 7 13
6
*/