题解 | Head of a Gang

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

struct Member {
    string name,father;
    int height, minute;
};

bool compare(Member lhs,Member rhs){
    return lhs.minute>rhs.minute;
}

map<string, Member> gang;

void Initial(string name,int minute) {
    map<string, Member>::iterator it = gang.find(name);
    if (it == gang.end()) {
        Member member;
        member.name=name;
        member.father = name;
        member.height = 0;
        member.minute = minute;
        gang[name] = member;
    }else{
        it->second.minute+=minute;
    }
}

string Find(string name) {
    map<string, Member>::iterator it = gang.find(name);
    if (name != it->second.father) {
        it->second.father = Find(it->second.father);
    }
    return it->second.father;
}

void Union(string name_1, string name_2) {
    name_1 = Find(name_1);
    name_2 = Find(name_2);
    if (name_1 == name_2) {
        return;
    } else {
        map<string, Member>::iterator it_1 = gang.find(name_1);
        map<string, Member>::iterator it_2 = gang.find(name_2);
        if (it_1->second.height > it_2->second.height) {
            it_2->second.father = name_1;
        } else if (it_1->second.height < it_2->second.height) {
            it_1->second.father = name_2;
        }else{
            it_2->second.father = name_1;
            it_1->second.height++;
        }
    }
}


int main() {
    int n, k;
    while (cin >> n >> k) {
        getchar();
        while (n--) {
            string str;
            getline(cin, str);
            string str_1=str.substr(0,str.find(" "));
            str=str.substr(str.find(" ")+1);
            string str_2 = str.substr(0,str.find(" "));
            str=str.substr(str.find(" ")+1);
            int minute = stoi(str.substr(0));
            Initial(str_1,minute);
            Initial(str_2,minute);
            Union(str_1,str_2);
        }

        map<string,Member>::iterator it=gang.begin();
        int gang_count=0;
        vector<string> answer;
        for(;it!=gang.end();it++){
            if(it->first==it->second.father){
                vector<Member> myMember;
                int total_minute=0,member_count=0;
                map<string,Member>::iterator it_1=gang.begin();
                for(;it_1!=gang.end();it_1++){
                    if(it->second.father==Find(it_1->second.father)){
                        member_count++;
                        total_minute+=it_1->second.minute;
                        myMember.push_back(it_1->second);
                    }
                }
                sort(myMember.begin(),myMember.end(), compare);
                string head=myMember[0].name;
                if(member_count>=3 && total_minute/2>k){
                    gang_count++;
                    string ans=head+" "+ to_string(member_count);
                    answer.push_back(ans);
                }
            }
        }
        cout<<gang_count<<endl;
        sort(answer.begin(),answer.end());
        for(int i=0;i<answer.size();i++){
            cout<<answer[i]<<endl;
        }
        gang.clear();
    }
}