题目描述

察找到团伙头目的一种方法是检查人们的通话。

如果 A 和 B 之间有通话，我们就说 A 和 B 是相关的。并且关联具有传递性，即如果 A 与 B 关联，B 与 C 关联，那么 A 与 C 也是关联的。

关联权重定义为两人之间所有通话的总时间长度。

一个“帮派”是一个由至少3个相互关联的人组成的群体，并且其总关联权重大于给定的阈值 K。

在每个帮派中，总权重最大的就是头目，数据保证每个帮派中总权重最大的人是唯一的。

你需要确定各个帮派以及帮派头目。

输入格式
第一行包含两个整数 N 和 K，表示通话数量以及权重阈值。

接下来 N 行，每行采用如下形式描述通话：

Name1 Name2 Time
Name1 和 Name2 是通话的两人的名字，Time 是通话时间。

名字的长度固定为 3，且只包含大写字母。

时间是一个不超过 1000 的正整数。

输出格式
第一行输出帮派数量。

接下来每行输出一个帮派的信息，包括帮派头目名字以及帮派人数。

帮派信息按头目名字字典序输出。

数据范围
1≤N,K≤1000

样例

输入样例1：
8 59
AAA BBB 10
BBB AAA 20
AAA CCC 40
DDD EEE 5
EEE DDD 70
FFF GGG 30
GGG HHH 20
HHH FFF 10
输出样例1：
2
AAA 3
GGG 3
输入样例2：
8 70
AAA BBB 10
BBB AAA 20
AAA CCC 40
DDD EEE 5
EEE DDD 70
FFF GGG 30
GGG HHH 20
HHH FFF 10
输出样例2：
0

算法1

(并查集) $O(n^2)$

1. 第一步，要使用并查集，首先需要将每一个人的名字和一个编号对应起来，nam,nam2就是使用了两个哈希表来完后才能这个任务
2. 这里维护了一下每一个集合内部的数量，老模板了
3. 这一个题，注意读懂题意，实际上只要每一个连通块的所有节点的权值之和大于阈值而且连通块中的节点个数大于3就可以看成一个帮派

时间复杂度

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;

const int N=1010;
int p[N];
int idx=1;
unordered_map<string,int>nam;
unordered_map<int,string>nam2;
int n,k;
int v[N];//每一个点的权值
int cnt[N];
typedef pair<string,int>PSI;
vector<PSI>ans;
bool  st[N];//判断某一个点是否已经确定在某一个集合中

int find(int x)
{
    if(x!=p[x])p[x]=find(p[x]);
    return p[x];
}
int main()
{
    cin>>n>>k;

    for(int i=1;i<=n;i++)p[i]=i,cnt[i]=1;//并查集初始化


    for(int i=0;i<n;i++)
    {
        string x,y;
        int t;
        cin>>x>>y>>t;
        if(!nam.count(x))nam[x]=idx++;//建立string类型的名字到int类型的映射
        if(!nam.count(y))nam[y]=idx++;

        nam2[nam[x]]=x;//建立映射
        nam2[nam[y]]=y;


        v[nam[x]]+=t;
        v[nam[y]]+=t;

        int px=find(nam[x]),py=find(nam[y]);
        if(px!=py)
        {
            p[px]=py;
            cnt[py]+=cnt[px];

        }



    }

    // cout<<nam.size();
    //  cout<<p[6]<<p[7]<<p[8];




    for(int i=1;i<=nam.size();i++)
    {
        int fa=find(i);//找到当前集合的代表元素
        int max_value=0;
        int sum=0;//计算每一个连通块权值的和
        int max_id;//找到每一个集合内部权值最大的点

        for(int j=1;j<=nam.size();j++)
        {
            if(!st[j])
            {
                if(fa==find(j))
                {
                    st[j]=true;
                    if(v[j]>max_value)max_id=j,max_value=v[j];
                    sum+=v[j];
                }
            }
        }
        sum/=2;
        if(cnt[fa]>=3&&sum>k)
        ans.push_back({nam2[max_id],cnt[fa]});
    }



     sort(ans.begin(),ans.end());
     cout<<ans.size()<<endl;

     for(auto t:ans)cout<<t.first<<" "<<t.second<<endl;


    return 0;



}