题解 | #Head of a Gang#

//暴力解法：照着题目说的统计权重，然后使用map存储结果输出即可
#include <iostream>
#include<cstring>
#include<string>
#include<vector>
#include<map>
const int maxn = 26;
using namespace std;
int father[maxn];
int height[maxn];
int phone[maxn];
void init(int n) {
    for (int i = 0; i < n; i++) {
        father[i] = i;
        height[i] = 0;
        phone[i] = 0;
    }
}

int find(int x) {
    if (x != father[x]) {
        x = father[x];
    }
    return father[x];
}

void Union(int x, int  y) {
    x = find(x);
    y = find(y);
    if (x != y) {
        if (height[x] < height[y]) {
            father[x] = y;
        } else if (height[x] > height[y]) {
            father[y] = x;
        } else {
            father[y] = x;
            height[x] += 1;
        }
    }
}


int countFather(int x) {
    int count = 0;
    for (int i = 0; i < maxn; i++) {
        if (find(i) == find(x)) {
            count++;
        }
    }
    return count;
}


int main() {
    int num, weight;
    string a, b;
    int numa, numb, minute; //通话时长

    while (cin >> num >> weight) { // 注意 while 处理多个 case
        map<int, int> result;
        map<int, string> m;
        init(maxn);
        while (num--) {
            cin >> a >> b >> minute;
            numa = a[0] - 'A';
            numb = b[0] - 'A';
            m[numa] = a;
            m[numb] = b;
            phone[numa] += minute;
            phone[numb] += minute;
            Union(numa, numb);
        }
        for (int i = 0; i < maxn; i++) {
            if (i == find(i) && countFather(i) > 2) {
                int sumWeight, maxWeight, maxIndex;
                sumWeight = 0;
                maxWeight = 0;
                maxIndex = 0;
                for (int j = 0; j < maxn; j++) {
                    if (find(j) == i) {
                        sumWeight += phone[j];
                        if (phone[j] > maxWeight) {
                            maxWeight = phone[j];
                            maxIndex = j;
                        }
                    }
                }
                sumWeight /= 2;
                if (sumWeight > weight) {
                    result[maxIndex] = countFather(i);

                }
            }
        }
        cout << result.size() << endl;
        map<int, int>::iterator it;
        for (it = result.begin(); it != result.end(); it++) {
            cout << m[it->first] << " " << it->second << endl;
        }



    }
}
// 64 位输出请用 printf("%lld")