PAT 2019甲级春季考试真题3 Telefraud Detection

Telefraud（电信诈骗） remains a common and persistent problem in our society. In some cases, unsuspecting victims lose their entire life savings. To stop this crime, you are supposed to write a program to detect those suspects from a huge amount of phone call records.

A person must be detected as a suspect if he/she makes more than $K$ short phone calls to different people everyday, but no more than 20% of these people would call back. And more, if two suspects are calling each other, we say they might belong to the same gang. $A$ makes a short phone call to $B$ means that the total duration of the calls from $A$ to $B$ is no more than 5 minutes.

Input Specification:

Each input file contains one test case. For each case, the first line gives 3 positive integers $K$ ($\le 500$, the threshold（阈值） of the amount of short phone calls), $N$ (≤103, the number of different phone numbers), and $M$ (≤105, the number of phone call records). Then $M$ lines of one day's records are given, each in the format:

caller receiver duration

where caller and receiver are numbered from 1 to $N$, and duration is no more than 1440 minutes in a day.

Output Specification:

Print in each line all the detected suspects in a gang, in ascending order of their numbers. The gangs are printed in ascending order of their first members. The numbers in a line must be separated by exactly 1 space, and there must be no extra space at the beginning or the end of the line.

If no one is detected, output None instead.

Sample Input 1:

5 15 31
1 4 2
1 5 2
1 5 4
1 7 5
1 8 3
1 9 1
1 6 5
1 15 2
1 15 5
3 2 2
3 5 15
3 13 1
3 12 1
3 14 1
3 10 2
3 11 5
5 2 1
5 3 10
5 1 1
5 7 2
5 6 1
5 13 4
5 15 1
11 10 5
12 14 1
6 1 1
6 9 2
6 10 5
6 11 2
6 12 1
6 13 1

Sample Output 1:

3 5
6

Note: In sample 1, although 1 had 9 records, but there were 7 distinct receivers, among which 5 and 15 both had conversations lasted more than 5 minutes in total. Hence 1 had made 5 short phone calls and didn't exceed the threshold 5, and therefore is not a suspect.

Sample Input 2:

5 7 8
1 2 1
1 3 1
1 4 1
1 5 1
1 6 1
1 7 1
2 1 1
3 1 1

Sample Output 2:

None

题目大意：电信诈骗。一个人，如果给超过K个人打了短电话（不超过5分钟的电话），而且被回拨的人少于打出的20%，则这个人就是嫌疑人。如果这个人与另外一个嫌疑人进行了双向通话，则他们可能是一个犯罪团伙。

这道题使用Set存放邻接表，然后计算回拨，最后使用并查集计算团伙即可。