题解 | #Head of a Gang#

详细注释

#include <iostream>
#include "string"
#include "map"

const int MAXN = 1000 + 10;

using namespace std;
struct Relation {
    string p1;
    string p2;
    int time;
};


Relation relalte[MAXN];//存储电话记录
map<string, string> father;
map<string, int> weight;//存储每个人打电话的总时长

//初始化
void InitSet(int n) {
    for (int i = 0; i < n; ++i) {
        cin >> relalte[i].p1 >> relalte[i].p2 >> relalte[i].time;
        weight[relalte[i].p1] += relalte[i].time;
        weight[relalte[i].p2] += relalte[i].time;
        father[relalte[i].p1] = relalte[i].p1;
        father[relalte[i].p2] = relalte[i].p2;
    }
}

//找到爸爸
string FindFather(string name) {
    if (name == father[name]) {
        return name;
    } else {
        father[name] = FindFather(father[name]);
        return father[name];
    }
}

//合并
void UnionSet(string name1, string name2) {
    string name1F = FindFather(name1);
    string name2F = FindFather(name2);
    if (name1F != name2F) {
        if (weight[name1F] < weight[name2F]) {//name2F是老大
            father[name1] = name2F;
        } else {//name1F是老大
            father[name2] = name1F;
        }
    }
//如果相同就没必要动。
}


//检查黑帮的人头数、打电话总数
void CheckGangs(map<string, int> &head_weight, map<string, int> &head_member) {
    for (auto it: father) {
        string head = FindFather(it.first);//当前这个人所属的帮派
        head_weight[head] += weight[it.first];//这个帮派头目名下的人打电话的总和（重复算了一遍）
        head_member[head]++;//这个帮派下人头数
    }
}

//筛选出符合要求的黑帮
void
ElectGangs(int K, map<string, int> &head_weight, map<string, int> &head_member, map<string, int> &legal_head_member) {
    for (auto itHead: head_weight) {
        if (itHead.second > K * 2 && head_member[itHead.first] > 2) {//这个帮派头目名下的人打电话的总和大于K，且人数大于2
            legal_head_member[itHead.first] = head_member[itHead.first];
        }
    }
}


int main() {
    int N;//N条通话记录
    int K;//权重。大于K的才有可能是Gang
    while (scanf("%d%d", &N, &K) != EOF) {
        InitSet(N);//录入N组数据
        for (int i = 0; i < N; ++i) {//合并并查集
            UnionSet(relalte[i].p1, relalte[i].p2);
        }
        //以老大的名字作为黑帮的名字
        map<string, int> head_weight;//整个黑帮的通话量
        map<string, int> head_member;//黑帮下属人头数量
        map<string, int> legal_head_member;//符合要求的黑帮以及下属人头数量
        //检查黑帮的条件
        CheckGangs(head_weight, head_member);
        //选出黑帮
        ElectGangs(K, head_weight, head_member, legal_head_member);
        //输出结果
        printf("%zu\n", legal_head_member.size());
        for (auto it: legal_head_member) {
            cout << it.first << " " << it.second << endl;
        }
        father.clear();
        weight.clear();
    }
    return 0;
}