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 (≤500, the threshold（阈值） of the amount of short phone calls), N (≤10^3, the number of different phone numbers), and M (≤10^5, 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 1had 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
题库类似题
1034，这道题能用两种方法做：
（1）并查集（https://blog.csdn.net/a617976080/article/details/99436602）
（2）DFS（https://blog.csdn.net/liuchuo/article/details/52291920）
如果目的就是准备考试，那建议两种都让自己独立写一写，不要偷懒。
题目大意
给定以下条件，作为电信诈骗团伙的判断：
1. 一个人给不同的K个以上的人打电话，其中给每个人的通话总和不超过5分钟的，称为短通话，短通话中只有不超过20%的人给他回电；
2.满足1的两个人互相通话，就是同一个团伙。
要根据通话记录，分析出团伙的成员，按照从小到大的序号输出成员编号。
难点
1.要想到这道题适合用并查集，就得熟悉并查集的特点：A和B关联，B和C关联，则认为A和C关联。这道题是符合的。
如果不引入这种非线性的数据结构，而采用向量、集合的话，写判断是会很麻烦的。
2.并查集在近三年的考题里就出现过这一次，最有效率的方式是能熟练运用两个并查集算法的函数：
int Findfather(int v){//这个递归写法最简单，而且包含路径压缩
return v==father[v] ? v : father[v] = Findfather(v);
}
void Union(int a,int b){
int faA=Findfather(a);
int faB=Findfather(b);
if(faA faB){
father[faB]=faA;
}
}
满分代码
#include
#include
using namespace std;
const int maxn=1005;
int n,m,k;
int father[maxn],G[maxn][maxn],visit[maxn];
vector gang;
int findfather(int v){
return v==father[v] ? v : father[v] = findfather(v);
}
void u(int a,int b){
int faA=findfather(a);
int faB=findfather(b);
if(faA faB){
father[faB]=faA;
}
}
int main(){
scanf("%d %d %d",&k,&n,&m);
fill(G[0],G[0]+maxn*maxn,0);
fill(visit,visit+maxn,0);
for(int i=1;i<=n;i++){
father[i]=i;
}
int a,b,c;
for(int i=0;i<m;i++){
scanf("%d %d %d",&a,&b,&c);
G[a][b]+=c;
}
for(int i=1;i<=n;i++){
int sc=0,bc=0;
for(int j=1;j0 && G[i][j]0){
bc++;
}
}
}
if(sc>k && bc*5<=sc){
gang.push_back(i);
}
}
for(int i=0;i<gang.size();i++){
for(int j=0;j<gang.size();j++){
if(i==j)continue;
int x=gang[i],y=gang[j];
if(G[x][y]!=0 && G[y][x]!=0){
u(x,y);
}
}
}
for(int i=0;i<gang.size();i++){
int x=gang[i];
if(visit[x]==1)continue;
visit[x]=1;
printf("%d",x);
for(int j=i+1;j<gang.size();j++){
int y=gang[j];
if(visit[y]==0 && findfather(x)==findfather(y)){
visit[y]=1;
printf(" %d",y);
}
}
printf("\n");
}
if(gang.size()==0)printf("None\n");
return 0;
}
感谢观看！
作者：qiiingc