题解 | #Head of a Gang#

思路就是并查集，但是使用map构造

#include <iostream>
#include <cstdio>
#include <map>
#include <set>
#include <string>
using namespace std;

int main()
{
    int n,k,i,j,w,sum;
    string s1,s2,t1,t2,head;
    while(cin>>n>>k)
    {
        map<string,string> father;//属于哪个集合
        map<string,int> weight;//成员权重
        map<string,int> tw;//帮派总权重的2倍
        map<string,int> mem;//帮派人数
        map<string,int> gang;//所有帮派头目和人数;
        k=k*2;
        for(i=0;i<n;i++)
        {
            cin>>s1>>s2>>w;
            if(weight.find(s1)==weight.end()&&weight.find(s2)==weight.end())
            {
                father[s1]=s1;
                father[s2]=s1;
                weight[s1]=w;
                weight[s2]=w;
                mem[s1]=2;
            }
            else if(weight.find(s1)==weight.end()&&weight.find(s2)!=weight.end())
            {
                father[s1]=father[s2];
                weight[s1]=w;
                weight[s2]+=w;
                mem[father[s2]]++;
            }
            else if(weight.find(s2)==weight.end()&&weight.find(s1)!=weight.end())
            {
                father[s2]=father[s1];
                weight[s2]=w;
                weight[s1]+=w;
                mem[father[s1]]++;
            }
            else
            {
                if(father[s1]==father[s2])
                {
                    weight[s2]+=w;
                    weight[s1]+=w;
                }
                else
                {
                    weight[s2]+=w;
                    weight[s1]+=w;
                    t1=father[s1];
                    t2=father[s2];
                    mem[t1]+=mem[t2];
                    for(map<string,string>::iterator it=father.begin();it!=father.end();it++)
                    {
                        if(it->second==t2)
                            it->second=t1;
                    }
                }
            }
        }
        for(map<string,string>::iterator it=father.begin();it!=father.end();it++)
        {
            tw[it->second]+=weight[it->first];
        }
        for(map<string,int>::iterator it=tw.begin();it!=tw.end();it++)
        {
            if(mem[it->first]>2&&it->second>k)
            {
                w=0;
                for(map<string,string>::iterator its=father.begin();its!=father.end();its++)
                {
                    if(its->second==it->first&&weight[its->first]>w)
                    {
                        w=weight[its->first];
                        head=its->first;
                    }
                }
                gang[head]=mem[it->first];
            }
        }
        cout<<gang.size()<<endl;
        if(gang.size()>0)
            for(map<string,int>::iterator it=gang.begin();it!=gang.end();it++)
            {
                cout<<it->first<<' '<<it->second<<endl;
            }
    }
    return 0;
}