题解 | #Head of a Gang#

#include<iostream>
#include<map>
#include<set>
#include<vector>
using namespace std;


map<string, int>strToInt;
map<int, string>intToStr;
int weights_array[2000];
int name_index;
int father[2000];

void init_Config() {
    strToInt.clear();
    intToStr.clear();
    fill(weights_array, weights_array + 1001, 0);
    name_index = 0;
    for (int i = 0; i < 1001; i++) {
        father[i] = i;
    }
}
struct block {
    int block_index = 0; //团伙id,某个连通分量的成员ID
    int sum_weights = 0; //团伙权重
    int head_of_weights = 0; //团后头目的权重
    int head_of_gang = 0; //团伙头目的id
    int count = 0;
    block() {
        block_index = 0;
        sum_weights = 0;
        head_of_weights = 0;
        head_of_gang = 0;
        count = 0;
    }
    block(int a, int b, int c, int d, int e) {
        block_index = a;
        sum_weights = b;
        head_of_weights = c;
        head_of_gang = d;
        count = e;
    }

};
struct person {
    string name;
    int num;
    person(string a, int b) {
        name = a;
        num = b;
    }
};
int findFather(int x) {
    if (x != father[x]) father[x] = findFather(father[x]);
    return father[x];
}
void unionFather(int x, int y) {
    int x_father = findFather(x);
    int y_father = findFather(y);
    father[y_father] = father[x_father];
}

int transStrToInt(string str) {
    if (strToInt.find(str) != strToInt.end()) {
        return strToInt[str];
    } else {
        strToInt[str] = name_index;
        intToStr[name_index] = str;
        name_index++;
        return strToInt[str];

    }
}


int main() {
    int N, K;
    while (scanf("%d %d", &N, &K) != EOF) {
        init_Config();
        string name1, name2;
        int weight;
        for (int i = 0; i < N; i++) {
            cin >> name1 >> name2 >> weight;
            int name1int = transStrToInt(name1);
            int name2int = transStrToInt(name2);
            //无向图添加双向
            weights_array[name1int] += weight;
            weights_array[name2int] += weight;
            unionFather(name1int, name2int);
        }
        map<int, block>result;
        for (int gang_id = 0; gang_id < name_index; gang_id++) {
            int block_index = findFather(gang_id);
            if (result.find(block_index) == result.end()) {
                result[block_index] = block(block_index, weights_array[gang_id],
                                            weights_array[gang_id], gang_id, 1);
            } else {
                result[block_index].block_index = block_index;
                result[block_index].sum_weights += weights_array[gang_id];
                result[block_index].count++;
                if (result[block_index].head_of_weights < weights_array[gang_id]) {
                    result[block_index].head_of_weights = weights_array[gang_id];
                    result[block_index].head_of_gang = gang_id;
                }
            }

        }
        int count = 0;
        vector<person>head_of_gang;
        for (auto iter = result.begin(); iter != result.end(); iter++) {
            if (iter->second.count > 2 && iter->second.sum_weights / 2 > K) {
                count++;
                head_of_gang.push_back(person(intToStr[iter->second.head_of_gang],
                                              iter->second.count));
            }
        }
        cout << count << endl;
        for (auto iter : head_of_gang) {
            cout << iter.name << " " << iter.num << endl;
        }
        //printf("");

    }
}