题解 | #Head of a Gang#

真是究极麻烦的一道并查集！！

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

const int maxn=20000;
int father[maxn];
int height[maxn];
int number[maxn];//帮派总人数
int weight[maxn];//帮派总权重
int visit[maxn];
int relation[maxn];//每个人的权重

struct tuanhuo{
    string head;
    int people;
    tuanhuo(string head,int people):head(head),people(people){}
};

void initial(){
    for(int i=0;i<=maxn;i++){
        father[i]=-1;
        height[i]=0;
        number[i]=1;
        weight[i]=0;
        visit[i]=0;
        relation[i]=0;

    }
}

int Find(int x){
    if (father[x]==-1)return x;
    return Find(father[x]);
}
void Union(int x,int y,int newweight){
    int fx=Find(x);
    int fy=Find(y);
    if(fx==fy){
        weight[fx]+=newweight;
    }
    else if(height[fx]>height[fy]){
        father[fy]=fx;
        number[fx]+=number[fy];
        weight[fx]+=weight[fy]+newweight;
    }
    else if(height[fx]<height[fy]){
        father[fx]=fy;
        number[fy]+=number[fx];
        weight[fy]+=weight[fx]+newweight;
    }
    else{
        father[fx]=fy;
        height[fy]++;
        number[fy]+=number[fx];//作为根节点的fy，它记录的人数和总权重都应该更新
        weight[fy]+=weight[fx]+newweight;
    }
}

int str2int(string str){
    int ans=0;
    int tmp;
    for(int i=0;i<str.size();i++){
        tmp=str[i]-'A'+1;
        ans=ans*26+tmp;
    }
    return ans;
}

string int2str(int x){
    string str="";
    while(x>0){
        char c=x%26+'A'-1;
        str=c+str;
        x/=26;
    }
    return str;
}

int findhead(int root){
    int maxi=relation[root];
    int head=root;
    for(int i=0;i<maxn;i++){
        if (Find(i)==root){
            visit[i]=0;
            if (relation[i]>maxi){
                maxi=relation[i];
                head=i;
            }
        }
    }
    return head;
}

int compare(tuanhuo x,tuanhuo y){
    return x.head<y.head;
}

int main()
{
    int n;//联系数
    int k;//威胁
    string para1,para2;int nw;
    int p1,p2;
    while(cin>>n>>k){
    vector<tuanhuo>v;
    initial();
    while(n--){
        cin>>para1>>para2>>nw;
        p1=str2int(para1);
        p2=str2int(para2);
        visit[p1]=1;
        visit[p2]=1;
        relation[p1]+=nw;
        relation[p2]+=nw;
        Union(p1,p2,nw);
    }

    int candidateroot,people;string head;
    for(int i=0;i<maxn;i++){
        if(!visit[i])continue;
        candidateroot=Find(i);
        if(number[candidateroot]>2&&weight[candidateroot]>k){//这是一个团伙
            int inthead=findhead(candidateroot);
            head=int2str(findhead(candidateroot));
            people=number[candidateroot];
            tuanhuo a(head,people);
            v.push_back(a);
        }
    }
    sort(v.begin(),v.end(),compare);
    cout<<v.size()<<endl;
    for(int i=0;i<v.size();i++)cout<<v[i].head<<" "<<v[i].people<<endl;
    }
    return 0;
}