题解 | #Head of a Gang#

//题目说人名是3个字母组成的，结果测试用例里面还有1、2个字母的人名

//这个题目思路很简单，就是磨人

#include <iostream>
using namespace std;

int sj[30];//在并查集的基础上，每个结点还要存通话时间
int height[30];
int father[30];
int visit[30];
int root[30];//记录哪些结点是根
int number[30];//每棵树的结点数量
long long total[30];//每棵树的总时长
string rm[30];//存各种长度的人名
int sl[30];//是否是首领


void Initial()
{
    for(int i=0;i<30;i++)
    {
        height[i]=0;
        father[i]=i;
        sj[i]=0;
        visit[i]=0;
        root[i]=-1;//这里我i写成了30，就这个错误找了半小时，气死了
        number[i]=0;
        total[i]=0;
        rm[i]="";
        sl[i]=0;
    }
}

int Find(int x)
{
    if(father[x]==x)return x;
    else
     {
        return Find(father[x]);
     }
}

void Union(int a,int b)
{
    a=Find(a);
    b=Find(b);
    if(a!=b)
    {
        if(height[a]>height[b])father[b]=a;
        else if(height[a]<height[b])father[a]=b;
        else
         {
            father[b]=a;
            height[a]++;
         }
    }
}

int main() {
    int a, b;
    while (cin >> a >> b) { 
        Initial();
        for(int i=1;i<=a;i++)
        {
            string str1,str2;int t;
            cin>>str1>>str2>>t;

            rm[str1[0]-'A']=str1;
            rm[str2[0]-'A']=str2;

            sj[str1[0]-'A']+=t;
            sj[str2[0]-'A']+=t;
          
            visit[str1[0]-'A']=1;
            visit[str2[0]-'A']=1;
            Union(str1[0]-'A',str2[0]-'A');

            getchar();
            

        }

        //找出有哪些根
        for(int i=0;i<30;i++)
        {
            if(visit[i])
            {
                if(i==Find(i))
                {
                    root[i]=-2;
                    
                }
            }
        }

        //找出每颗树的总时长和人数
        for(int i=0;i<30;i++)
        {
            if(root[i]==-2)//i是根
            {
                for(int j=0;j<30;j++)
                {
                    if(Find(j)==i)//是该树的结点
                    {
                        number[i]++;//该根对应的树的人数
                        total[i]+=(sj[j]);//该根对应的树的总通话时间*2
                    }
                }
            }
        }

        //找出是帮派的树  及其首领
        int ans1=0;//帮派数量
        int ans2;//首领字母对应的数字
        for(int i=0;i<30;i++)
        {
            if(root[i]==-2)//i是根
            {
                if(number[i]>2&&total[i]>(b*2))//是帮派
                {
                    ans1++;

                    //找该帮派的首领
                    for(int j=0;j<30;j++)
                    {
                        if(Find(j)==i)
                        {
                            ans2=j; //首领字母对应的数字
                            break;
                        }
                    }

                    for(int j=0;j<30;j++)
                    {
                        if(Find(j)==i)
                        {
                            if(sj[j]>sj[ans2])ans2=j;
                        }
                    }
                    root[i]=ans2;//root里存首领字母对应的数字
                    sl[ans2]=1;
                }

            }

        }  

        cout<<ans1<<endl;
        if(ans1!=0)
        for(int i=0;i<30;i++)
        {
            
            if(sl[i]==1)
            {
                cout<<rm[i]<<" ";
                cout<<number[Find(i)]<<endl;
            }

        }

    }
}