ZJYYCOJ-援军通道（最小生成树）

胖肚子最近在玩一款策略游戏，他现在占领了N个城市，他想在这N个城市之间修建一些道路，方便以后受到攻击时可以快速支援。现在有M条修建道路的选项，胖肚子希望他的军队从任意一个城市出发都能到达另一个任意的城市，修建每条道路需要一定的银两，现在请你帮胖肚子计算一下，最低需要多少银两才能完成胖肚子的需求。

测试样例由多组测试数据组成。对于每组测试数据，第一行输入两个正整数N（2 <= N <= 300）和M（1 <= M <= 105），分别代表胖肚子占领的城市数量和能够修建的道路选项数量。接下来N行，每行输入一个字符串str（1 <= str.length <= 10）代表胖肚子占领的每个城市的名字（不存在相同的城市名字），再接下来M行，每行输入两个字符串u,v（1 <= u.length,v.length <= 10）和一个整数w（1 <= w <= 10000），分别代表在城市u和城市v之间可以修建一条道路，所需要的银两数量为w。

对于每组测试样例，输出胖肚子完成自己的需求最低需要多少银两。如果胖肚子无法完成自己的需求，则输出-1

样例输入 1

Copy

3 3

chengdu

hanzhong

jiange

chengdu hanzhong 5

hanzhong jiange 3

chengdu jiange 10

样例输出 1

Copy

8

思路：最小生成树模板

#include

using namespace std;
typedef long long ll;
const int maxn = 1e5;
struct node{
    string a;
    string b;
    int w;
    int u,v;
}arr[maxn];
int s[maxn];
int x[maxn];
void csh(int x){
    for (int i = 0 ;i <= x ;i++){
        s[i] = i;
    }
}
int findx(int x){
    if (s[x] == x){
        return x;
    }
    else{
        return s[x] = findx(s[x]);
    }
}
void merge(int x,int y){
    x = findx(x),y = findx(y);
    if (x != y){
        s[x] = y;
    }
}
bool cmp(node a,node b){
    return a.w < b.w;
}
int main() {
    int n,m;
    while (cin>>n>>m){
        csh(n);
        string ss;
        map mp1;
        for (int i = 1 ; i <= n ;i++){
            cin>>ss;
            mp1[ss] = i;
        }
        for (int i = 0 ; i < m;i++){
            cin>>arr[i].a>>arr[i].b>>arr[i].w;
            arr[i].u = mp1[arr[i].a];
            arr[i].v = mp1[arr[i].b];
        }
        sort(arr,arr+m,cmp);
        ll sum = 0;
        for (int i = 0 ; i < m ;i++){
            if (findx(arr[i].u) != findx(arr[i].v)){
                merge(arr[i].u,arr[i].v);
                sum += arr[i].w;
            }
        }
        int cnt = 0;
        for (int i = 1 ; i <= n ;i++){
            if (i == findx(s[i])){
                cnt++;
            }
        }
        if (cnt > 1){
            cout<<-1<