编程题:团伙头目
警察找到团伙头目的一种方法是检查人们的通话。
如果 A 和 B 之间有通话,我们就说 A 和 B 是相关的。并且关联具有传递性,即如果 A 与 B 关联,B 与 C 关联,那么 A 与 C 也是关联的。
关联权重定义为两人之间所有通话的总时间长度。
一个“帮派”是一个由至少3个相互关联的人组成的群体,并且其总关联权重大于给定的阈值 K。
在每个帮派中,总权重最大的就是头目,数据保证每个帮派中总权重最大的人是唯一的。
你需要确定各个帮派以及帮派头目。
### 数据范围
1≤N,K≤1000
### 输入格式:
第一行包含两个整数 N 和 K,表示通话数量以及权重阈值。
接下来 N 行,每行采用如下形式描述通话:
> Name1 Name2 Time
Name1 和 Name2 是通话的两人的名字,Time 是通话时间。
名字的长度固定为 3,且只包含大写字母。
时间是一个不超过 1000 的正整数。
### 输出格式:
第一行输出帮派数量。
接下来每行输出一个帮派的信息,包括帮派头目名字以及帮派人数。
帮派信息按头目名字字典序输出。
### 输入样例1:
in
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:
out
2
AAA 3
GGG 3
### 输入样例2:
in
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
HHH FFF 10
### 输出样例2:
out
0
答案:若无答案欢迎评论
如果 A 和 B 之间有通话,我们就说 A 和 B 是相关的。并且关联具有传递性,即如果 A 与 B 关联,B 与 C 关联,那么 A 与 C 也是关联的。
关联权重定义为两人之间所有通话的总时间长度。
一个“帮派”是一个由至少3个相互关联的人组成的群体,并且其总关联权重大于给定的阈值 K。
在每个帮派中,总权重最大的就是头目,数据保证每个帮派中总权重最大的人是唯一的。
你需要确定各个帮派以及帮派头目。
### 数据范围
1≤N,K≤1000
### 输入格式:
第一行包含两个整数 N 和 K,表示通话数量以及权重阈值。
接下来 N 行,每行采用如下形式描述通话:
> Name1 Name2 Time
Name1 和 Name2 是通话的两人的名字,Time 是通话时间。
名字的长度固定为 3,且只包含大写字母。
时间是一个不超过 1000 的正整数。
### 输出格式:
第一行输出帮派数量。
接下来每行输出一个帮派的信息,包括帮派头目名字以及帮派人数。
帮派信息按头目名字字典序输出。
### 输入样例1:
in
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:
out
2
AAA 3
GGG 3
### 输入样例2:
in
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
HHH FFF 10
### 输出样例2:
out
0
答案:若无答案欢迎评论