算法1

(并查集) $O(n)$

1.两个哈希表来维护名字-id,id-名字的映射。

2.在读入时维护并查集，并用cost[N]维护每个集合的权值（$O(n)$）

3.扫一遍所有人，用一个哈希表来维护临时队长-队伍列表的映射
（此时把权值不到K的组织排除在外）（$O(n)$）

4.扫一下所有队伍（人数不足3的排除在外），
三人以上则扫出队长，加入答案vector中（$O(n)$）

5.排序一下vector里的m组，顺序输出。（这里严格算mlogm但组数至多为n/3）

C++ 代码

#include<iostream>
#include<unordered_map>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1010;

unordered_map<string,int> getid;//名字-id
string getname[N];//id-名字 

unordered_map<int,vector<int>> teams;//存符合要求的队伍
vector<pair<string,int>> res;//存答案

int n,k,idx;
int p[N];
int val[N];//每个点的权值
int cost[N];//每个组的权值

int find(int x){
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++) p[i]=i;//初始化并查集
    //读入数据
    for(int i=0;i<n;i++){
        string a,b;
        int t;
        cin>>a>>b>>t;
        if(!getid.count(a)){
            getid[a]=idx;
            getname[idx++]=a;
        }
        if(!getid.count(b)){
            getid[b]=idx;
            getname[idx++]=b;
        }
        int ai=getid[a],bi=getid[b];
        val[ai]+=t,val[bi]+=t;

        if(find(ai)!=find(bi)) {
            cost[find(bi)]+=cost[find(ai)];
            p[find(ai)]=find(bi);
        }

        cost[find(bi)]+=t;

    }

    //↓扫一遍，把每个人加入自己的队伍
    for(int i=0;i<n;i++){
        if(cost[find(i)]>k) teams[find(i)].push_back(i);
    }

    //↓每个队伍里找到队长
    for(auto te:teams){
        auto team=te.second;
        if(team.size()<3) continue;
        int boss=team[0],maxv=val[team[0]];
        for(auto mem:team){
            if(val[mem]>maxv){
                boss=mem;
                maxv=val[mem];
            }
        }
        res.push_back({getname[boss],team.size()});
    }

    //↓处理输出
    sort(res.begin(),res.end());
    cout<<res.size()<<endl;
    for(auto re:res){
        cout<<re.first<<" "<<re.second<<endl;
    }

    return 0;
}