7-3 Telefraud Detection (25分)
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 durationwhere 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 311 4 21 5 21 5 41 7 51 8 31 9 11 6 51 15 21 15 53 2 23 5 153 13 13 12 13 14 13 10 23 11 55 2 15 3 105 1 15 7 25 6 15 13 45 15 111 10 512 14 16 1 16 9 26 10 56 11 26 12 16 13 1Sample Output 1:
3 56Note: 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 81 2 11 3 11 4 11 5 11 6 11 7 12 1 13 1 1Sample Output 2:
None题目限度：
题目粗心：
- 一个人给不同的K个以上的人打电话，其中给每个人的通话总和不超过5分钟的，称为短通话，短通话中只有不超过20%的人给他回电；
- 满足1的两个人相互通话，就是同一个团伙。
- 要依据通话记录，剖析出团伙的成员，依照从小到大的序号输入成员编号。
算法思路：
这个题目的本意就是在所有嫌疑人组成的网络中找到每一个帮派的成员，而每一个帮派能够认为是一个连通重量，这样就能够应用DFS来进行求解，同时也能够认为是一个汇合，这样就能够应用并查集的形式来求解，这里给出两种不同的实现办法。
预处理：
DFS和并查集的预处理都是一样的，次要目标就是找出所有的嫌疑人，这样才不便在所有嫌疑人所形成的网络中进行查找和合并。首先咱们应用二维数组G保留该图的边权，并留神到此图是一个有向图，边权在输出的时候得累计，应用frequency和callback数组别离示意每一个人打电话不超过5分钟的次数和每一个嫌疑人在打的不超过5分种通话中，接管方回电话的人数，最初并用suspecters数组保留所有的嫌疑人。有了以上的容器后，接下来就是获取所有的嫌疑人了，间接遍历二维数组G，应用i示意caller，j示意receiver，只有G[i][j]!=0&&G[i][j]<=5，阐明以后caller打了一次短电话，累计++frequency[i]，在此基础上，如果G[j][i]!=0，阐明receiver回电话了，累计++callback[i]，在遍历完所有caller打的电话记录后，判断是否frequency[i]>K&&callback[i]<=floor(0.2*frequency[i])如果是，阐明i是嫌疑人，将其退出到suspecters。
DFS解法：
应用visited数组标记每一个嫌疑人是否被拜访，set<int> gang保留每一个帮派的人(一次DFS保留一个)，bool hasGang标记是否有帮派，初始为false,而后就应用DFS遍历整个图，每一次DFS遍历一个gang，遍历之前得清空gang汇合的内容，外围代码如下：
void DFS(int root,int K){ visited[root] = true; gang.insert(root); for (int suspecter : suspecters) { if(!visited[suspecter]&&G[root][suspecter]!=0&&G[suspecter][root]!=0){ //拜访每一个没有被拜访并且与以后root互相打电话的嫌疑人 DFS(suspecter,K); } }}bool hasGang = false;for (int suspecter : suspecters) { if(!visited[suspecter]){ gang.clear(); DFS(suspecter,K); int num = 0; for(auto &item:gang){ hasGang = true;// 有gang存在 printf("%d",item); if(num<gang.size()-1) printf(" "); ++num; } printf("\n"); }}并查集解法：
在预处理实现之后，就要将所有属于一个gang的嫌疑人进行合并，合并操作应用Union函数来实现，因为嫌疑人是从小到大退出的汇合，咱们就能够间接从第一个没有被拜访的嫌疑人开始，将他和其同属于一个gang的其余嫌疑人一并进行输入即可，这样就省去了排序的麻烦，其外围代码如下：
int father[1005];void init(){ for(int i=0;i<1005;++i){ father[i] = i; }}int getFather(int a){ while(a!=father[a]){ a = father[a]; } return a;}void Union(int a,int b){ int fa = getFather(a); int fb = getFather(b); if(fa!=fb){ father[fb] = fa; }}// 合并所有的嫌疑人for(int i:suspecters){ for(int j:suspecters){ if(i!=j&&G[i][j]!=0&&G[j][i]!=0){ // i和j是一个gang Union(i,j); } }}// 嫌疑人是从小到大退出的汇合，从小到大间接输入即可for(int i=0;i<suspecters.size();++i){ if(!visited[suspecters[i]]){ visited[suspecters[i]] = true; printf("%d",suspecters[i]); for(int j=i+1;j<suspecters.size();++j){ if(!visited[suspecters[j]]&&getFather(suspecters[i])==getFather(suspecters[j])){ visited[suspecters[j]] = true; printf(" %d",suspecters[j]); } } printf("\n"); }}留神点：
- 1、嫌疑人的断定中须要不超过20%的人回电话，这个20%如果是做的乘法运算得向下取整，也能够应用回电话的人数乘以5来代替。
- 2、嫌疑人之间得相互打电话才算是属于一个gang。
提交后果：
AC代码1：
#include <string>#include <cmath>#include <set>#include <vector>using namespace std;int G[1005][1005];int frequency[1005];// 统计每一个人打电话不超过5分钟的次数int callback[1005];// 每一个嫌疑人被回电话的人数vector<int> suspecters;// 所有的嫌疑人bool visited[1005];// 标记每一个嫌疑人是否被拜访set<int> gang;// 每一个帮派的嫌疑人void DFS(int root,int K){ visited[root] = true; gang.insert(root); for (int suspecter : suspecters) { if(!visited[suspecter]&&G[root][suspecter]!=0&&G[suspecter][root]!=0){ DFS(suspecter,K); } }}int main(){ int K,N,M;//阈值，顶点数目，边数目 scanf("%d %d %d",&K,&N,&M); for (int i = 0; i < M; ++i) { int a,b,time; scanf("%d %d %d",&a,&b,&time); G[a][b] += time; } for(int i=1;i<=N;++i){ for (int j = 1; j <=N ; ++j) { if(G[i][j]!=0&&G[i][j]<=5){ ++frequency[i]; if(G[j][i]!=0){ // j给i回电话了 ++callback[i]; } } } if(frequency[i]>K&&callback[i]<=floor(0.2*frequency[i])){ // 打不超过5分钟的电话的次数超过了阈值,并且回电话的人数不超过20% suspecters.push_back(i); } } bool hasGang = false; for (int suspecter : suspecters) { if(!visited[suspecter]){ gang.clear(); DFS(suspecter,K); int num = 0; for(auto &item:gang){ hasGang = true; printf("%d",item); if(num<gang.size()-1) printf(" "); ++num; } printf("\n"); } } if(!hasGang){ printf("None"); } return 0;}AC代码2：
#include<cstdio>#include <cmath>#include <vector>using namespace std;int G[1005][1005];int frequency[1005];// 统计每一个人打电话不超过5分钟的次数int callback[1005];// 每一个嫌疑人被回电话的人数vector<int> suspecters;// 所有的嫌疑人bool visited[1005];// 标记每一个嫌疑人是否被拜访int father[1005];void init(){ for(int i=0;i<1005;++i){ father[i] = i; }}int getFather(int a){ while(a!=father[a]){ a = father[a]; } return a;}void Union(int a,int b){ int fa = getFather(a); int fb = getFather(b); if(fa!=fb){ father[fb] = fa; }}int main(){ init(); int K,N,M;//阈值，顶点数目，边数目 scanf("%d %d %d",&K,&N,&M); for (int i = 0; i < M; ++i) { int a,b,time; scanf("%d %d %d",&a,&b,&time); G[a][b] += time; } for(int i=1;i<=N;++i){ for (int j = 1; j <=N ; ++j) { if(G[i][j]!=0&&G[i][j]<=5){ ++frequency[i]; if(G[j][i]!=0){ // j给i回电话了 ++callback[i]; } } } if(frequency[i]>K&&callback[i]<=floor(0.2*frequency[i])){ // 打不超过5分钟的电话的次数超过了阈值,并且回电话的人数不超过20% suspecters.push_back(i); } } // 合并所有的嫌疑人 for(int i:suspecters){ for(int j:suspecters){ if(i!=j&&G[i][j]!=0&&G[j][i]!=0){ // i和j是一个gang Union(i,j); } } } // 嫌疑人是从小到大退出的汇合，从小到大间接输入即可 for(int i=0;i<suspecters.size();++i){ if(!visited[suspecters[i]]){ visited[suspecters[i]] = true; printf("%d",suspecters[i]); for(int j=i+1;j<suspecters.size();++j){ if(!visited[suspecters[j]]&&getFather(suspecters[i])==getFather(suspecters[j])){ visited[suspecters[j]] = true; printf(" %d",suspecters[j]); } } printf("\n"); } } if(suspecters.empty()){ printf("None"); } return 0;}