警察找到团伙头的一种方法是检查人们的电话。如果 AAA 和 BBB 之间有电话,我们说 AAA 和 BBB 是相关的。关系的权重定义为两个人之间所有电话通话的总时间长度。“帮派”是指由两个以上相互关联的人组成的集群,并且总关联权重大于给定的阈值 K。在每个帮派中,总重量最大的是该帮派的头领。现在给出电话列表,你需要找到帮派和其头领。
输入第一行均包含两个正数 N 和 K、电话呼叫次数和权重阈值。然后是 N 行,每行以Name1 Name2 Time
的格式给出一个电话记录的信息。其中 Name1 和 Name2 是通话两端的人员名称,Time 是通话时间。名称是从 A-Z 中选择的三个大写字母的字符串。时间长度是一个不超过 1000 分钟的正整数。
首先在一行中打印帮派总数。然后,对于每个帮派,在一行中打印头领的名称和成员总数。可以确保每个帮派的头都是唯一的。注意,打印帮派信息时,需根据头领名称的字母顺序对输出进行排序。
0 < N , K < 1000 0<N,K<1000 0<N,K<1000
由于输入的名字是字符串,不好操作,可以将输入的人名全部不重复地存储到vector<string> v
中,这样我们就可以通过名字在 v 中的下标来唯一指代这个名字。为了方便找到名字对应的下标,可以在额外使用unordered_map<string, gg> um
存储名字和下标的对应关系。换句话说,我们可以利用这个下标对不同的姓名进行编号,这样的编号是从 0 开始连续的。
使用并查集,每一个集合对应于一个帮派。读取每个电话记录时,将电话记录的两个名字所对应的编号所在集合进行合并,并更新相关编号所对应的通话长度。所有电话记录读取完毕后,遍历所有的编号,以集合跟结点作为该集合的唯一标识,更新根结点对应的总通话长度和集合结点个数,此外,为了找到帮派头领,还可以定义一个 head 数组负责追踪帮派中的头领。
所有信息更新完毕,将相关信息按要求进行输出即可。
#include <bits/stdc++.h>
using namespace std;
using gg = long long;
const gg MAX = 2005;
vector<gg> ufs(MAX), Time(MAX), num(MAX), totalTime(MAX), head(MAX);
void init() {
iota(ufs.begin(), ufs.end(), 0);
iota(head.begin(), head.end(), 0);
}
gg findhead(gg x) { return ufs[x] == x ? x : ufs[x] = findhead(ufs[x]); }
void unionSets(gg a, gg b) { ufs[findhead(a)] = findhead(b); }
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
gg ni, ki, ti;
string s1, s2;
cin >> ni >> ki;
unordered_map<string, gg> um; //存储姓名和下标的对应关系
vector<string> v; //存储所有的名字
init();
while (ni--) {
cin >> s1 >> s2 >> ti;
if (not um.count(s1)) {
um.insert({s1, um.size()});
v.push_back(s1);
}
if (not um.count(s2)) {
um.insert({s2, um.size()});
v.push_back(s2);
}
Time[um[s1]] += ti;
Time[um[s2]] += ti;
unionSets(um[s1], um[s2]); //合并集合
}
for (gg i = 0; i < v.size(); ++i) {
gg r = findhead(i); //根结点
++num[r]; //递增该集合人数
totalTime[r] += Time[i]; //更新该集合的总通话长度
if (Time[i] > Time[head[r]]) { //更新该集合的头领
head[r] = i;
}
}
vector<pair<string, gg>> ans;
for (gg i = 0; i < v.size(); ++i) {
if (i == ufs[i] and num[i] > 2 and totalTime[i] > ki * 2) {
ans.push_back({v[head[i]], num[i]});
}
}
sort(ans.begin(), ans.end());
cout << ans.size() << "\n";
for (auto& i : ans) {
cout << i.first << " " << i.second << "\n";
}
return 0;
}