POJ1251 Jungle Roads（最小生成树）

题意：输入n,代表景点数，接下来n-1行,每一行第一的字母代表景点，后面的数字代表与它相连的景点数，后面有n对字母与数字，代表与该景点相连的景点及距离。

分析：Kruskal最小生成树

//#include "pch.h"
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#define maxn 10010
using namespace std;
typedef long long ll;
typedef struct Node {
    ll sta, ed, cost;
}node;
node e[maxn];
ll ans = 0,n,m,t,tt,pos;
char c,cc;
ll pa[maxn];
bool cmp(node x, node y) {
    return x.cost < y.cost;
}
ll findSet(ll x) {
    if (x != pa[x]) pa[x] = findSet(pa[x]);return pa[x];
}
void unionSet(ll x, ll y) {
    x = findSet(x);y = findSet(y);if (x == y) return;pa[x] = y;
}
bool isSame(ll x, ll y) {
    return findSet(x) == findSet(y);
}
int main() {
    std::ios::sync_with_stdio(false);while (cin >> n) {
    if (n == 0) break;ans = 0;pos = 0;memset(pa, 0, sizeof(pa));for (int i = 0; i < n - 1; i++) {
    cin >> c >> t;while (t--) {
    cin >> cc >> tt;int tmp = cc - 'A';int res = c - 'A';e[pos].sta = res;e[pos].ed = tmp;e[pos].cost = tt;pos++;}}for (int i = 0; i <= n; i++) {
     pa[i] = i; }sort(e, e + pos, cmp);for (ll i = 0; i < pos; i++) {
    if (isSame(e[i].sta, e[i].ed)) continue;unionSet(e[i].sta, e[i].ed);ans += e[i].cost;//cout << ans << endl;}cout << ans << endl;}return 0;
}