---

 度受限的最小生成树：

给定一张N个点,M个边的无向图,求出无向图的一颗最小生成树,但是我们要求一号节点的入度不可以超过给定的整数S

也就是一个最小生成树,要求它的一号节点,最多只能和S个节点相连.

——————————————————————————————————————————————————————————

(1)将一个无向图去掉根节点(编号为1)后得到的连通块：

bool vis[dot_num] = { false };//记录每个节点加入连通块的情况
int cnt = 0;//连通块的数量
for (int i = 1; i <= dot_num; i++){
	if (!vis[i]){
		cnt++;
		vis[i] = cnt;
		dfs(i);
	}
}
void dfs(int x){
	for (int j = 2; j <= dot_num; j++){
		if (G[x][j] && !vis[j]){
			vis[j] = cnt;
			dfs(j);
		}
	}
}

-------------------------------------------------------------------------------------

#include<iostream>
#include<algorithm>
#include<map>
#include<string>
using namespace std;
const int N = 1010;
int edge_num, dot_num, n, m, cnt, root;//cnt；联通快的数量
int father[N], G[50][50], dis[50][50];
map<string,int>q;//将字符串输入映射成节点数字编号
map<pair<int,int>, bool>qq;//记录边是否在生成树中
bool vis[N];//连通块的编号
int degree;//受限制的度

int findfather(int x){
	while (x != father[x]){
		x = father[x];
	}
	return father[x]; 
}

struct edge{
	int from, to, weight;
	bool operator <(const edge b)const{
		return weight < b.weight;
	}
}g[N];

inline int kruskal(){//将除度受限根节点1的剩余其它所有节点求最小生成树
	sort(g + 1, g + edge_num + 1);
	int ans = 0;
	for (int i = 1; i <= edge_num; i++){
		int x = findfather(g[i].from); int y = findfather(g[i].to);
		if (x == 1 || y == 1 || x == y){  //除节点1和x，y若在同一个联通块
			continue;
		}
		father[x] = y;
		ans += g[i].weight;
		//标记该边在最小生成树中
		qq[{g[i].from, g[i].to}] = true; qq[{g[i].to, g[i].from}] = true;
	}
	return ans;//最小生成树的权值和
}

//划分连通块
void dfs(int x){
	for (int j = 2; j <= dot_num; j++){
		if (G[x][j] && !vis[j]){
			vis[j] = cnt;
			dfs(j);
		}
	}
}

struct node{
	int u, v, d;
	inline void init(){
		u = v = 0;
		d = -1;
	}
}dp[N];
void dfs(int now, int last){
	for (int i = 2; i <= n; i++){
		if (last == i || !qq[{now,i}]){//如果最小生成树中没有这条边
			continue;
		}
		if (dp[i].d == -1){
			if (dp[now].d > G[now][i]){
				dp[i] = dp[now];
			}
			else{
				dp[i].u = now;
				dp[i].v = i;
				dp[i].d = G[now][i];
			}
		}
		dfs(i, now);
	}
}

int main(){
	
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	fill(G[0], G[0] + 50 * 50, 0);
	memset(vis, false, sizeof vis);
	cin >> n;

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

	q["Park"] = 1; dot_num++;//根节点，即度受限的点root数字编号为1

	string a, b; int c;
	for (int i = 0; i < n; i++){
		cin >> a >> b >> c;
		if (!q[a]){			//将字符节点映射成数字编号
			q[a] = ++dot_num;
		}
		if (!q[b]){
			q[b] = ++dot_num;
		}
		//加边存入邻接矩阵
		G[q[a]][q[b]] = G[q[b]][q[a]] = c;

		g[++edge_num].from = q[a]; g[edge_num].to = q[b]; g[edge_num].weight = c;//用于kruskal求最小生成树

	}
	cin >> degree;

	//除去根节点后将图划分成连通块
	for (int i = 2; i <= dot_num; i++){
		if (!vis[i]){
			cnt++;
			vis[i] = cnt;
			dfs(i);
		}
	}
	int res = kruskal();
	//将每一个连通块与1相连
	for (int i = 1; i <= cnt; i++){
		int now = 0x3f3f3f3f, index = 0;
		for (int j = 2; j <= dot_num; j++){//找到与1相连边最小的点
			if (vis[j] == i){
				if (now > G[1][j] && G[1][j]){
					now = G[i][j];
					index = j;
				}
			}
		}
		res += now;
		qq[{1, index}] = qq[{index, 1}] = true;
	}
	int t = cnt;
	while (degree > t){
		degree--;
		for (int i = 1; i <= n; i++){
			dp[i].init();
		}
		dfs(1, -1);
		int now = 0, idx = 0;
		for (int j = 2; j <= dot_num; j++){
			if (G[1][j] && now < (dp[j].d - G[1][j])){
				now = dp[j].d - G[1][j];
				idx = j;
			}
		}
		if (now <= 0){ break; }//不会使最小生成树权值更小，1的度只需维持比degree小即可
		res -= now;
		qq[{dp[idx].u, dp[idx].v}] = qq[{dp[idx].v, dp[idx].u}] = false;
		qq[{1, idx}] = qq[{idx, 1}] = true;

	}
	cout << "Total miles driven: " << res << endl;

	return 0;
}