题解 | #Head of a Gang#

/*
这题有点复杂，思路：
1.先存下所有人的电话总时间，并且将他们分为集合；
2.遍历集合，得到集合的数量，记录集合标识
3.对于每个集合，遍历所有人判断他们是否属于这个集合，是则贡献集合的总weight，member++，且随时记录weight最大的人，
若最后weight>k*2且member>=3，就把这个gang存起来
4.输出总gang数，按顺序输出集合leader+member
*/
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include<vector>
using namespace std;
map<string, string> father;
map<string, int> weight;
map<string, int> gang_weight;
string find(string name)
{
    if(father.find(name)!=father.end())
    {
        if(father[name]!=name)
            return find(father[name]);
    }
    else 
    {
        father[name] = name;
    }
    return father[name];
}


void Union(string name1,string name2)
{
    name1 = find(name1);
    name2 = find(name2);
    father[name1] = name2;
}


int main()
{
    int N, K;
    while (cin >> N >> K)
    {
        for (int i = 0; i < N; i++)
        {
            string name1, name2;
            int time;
            cin >> name1 >> name2 >> time;
            Union(name1, name2);
            weight[name1] += time, weight[name2] += time;
        }
        
        vector<string> gang_leader;
        for (auto it = father.begin(); it != father.end();it++)
        {
            if(it->first==it->second)
                gang_leader.push_back(it->second);//可能还不是首领
        }
        int gangs = 0;
        vector<string> gang_name;
        vector<int> gang_member;
        for (int i = 0; i < gang_leader.size();i++)
        {
            int member = 0;
            int weight_sum = 0;
            int leader_weight =0 ;
            string leader_name;
            for (auto it = father.begin(); it != father.end();it++)
            {
                if(find(it->first)==gang_leader[i])
                {
                    if(weight[it->first]>leader_weight)
                    {
                        leader_weight = weight[it->first];
                        leader_name = it -> first;
                    }
                    weight_sum += weight[it->first];
                    member++;
                }
            }

            if(member>=3&&weight_sum>K*2)
            {
                gangs++;
                gang_name.push_back(leader_name);
                gang_member.push_back(member);
            }
        }
        cout << gangs << endl;
        for (int i = 0; i < gangs;i++)
            cout << gang_name[i] << " " << gang_member[i]<<endl;
        father.clear();
        weight.clear();
    }
}