传送门：BLINNET - Bytelandian Blingors Network
通过读题，不难发现，把这些点连接起来的最小成本，岂不是最小生成树？
现在先思考一下给出的城市名字需要如何处理？其实直接按照输入顺序标号就好了！
跑一遍最小生成树即可，注意多测清空。
处理最小生成树的策略是，把边按照成本从小到大排序，每次找一个最短的边，根据并查集思想判断是否已经将节点纳入树中，若纳入树中，则不考虑这条边，若尚未纳入树中，就记录成本，并且用并查集做好标记。
见代码：
#include <bits/stdc++.h>
#define N 10010
#define M 1000010
using namespace std;
int n ,m ,ans ,tot ,cnt ,fa[N];
struct Edge{int u ,v ,w;}e[M];
void add(int u,int v,int w) {
++ tot;
e[tot].u = u;
e[tot].v = v;
e[tot].w = w;
}
int find(int x) {
return fa[x] == x ? fa[x]:fa[x] = find(fa[x]);
}
bool cmp(Edge a,Edge b) {
return a.w < b.w;
}
void search() {
sort(e+1 ,e+1+tot ,cmp);
for (int i = 1; i <= tot; ++ i) {
int u = find(e[i].u) ,v = find(e[i].v);
if(u == v) continue;
ans += e[i].w;
++ cnt;
fa[v] = u;
if(++ tot == n-1) break;
}
printf("%d\n" ,ans);
}
int main() {
int t;
scanf("%d" ,&t);
string nam;
for(int k = 1;k <= t; k++){
memset(fa,0,sizeof(fa));
memset(e,0,sizeof(e));
tot = 0;
ans = 0;
cnt = 0;
scanf("%d" ,&n);
for (int i = 1; i <= n; ++ i){
cin >> nam;
fa[i] = i;
scanf("%d" ,&m);
for (int j = 1 ,v ,w; j <= m; ++ j) {
scanf("%d %d",&v ,&w);
add(i ,v ,w);
}
}
search();
}
return 0;
}