A1158 TelefraudDetection（25 points）

模拟

1. 原文

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 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

2. 解析思路

判断电话诈骗分子，当一个人与>k个不同的人打短时间【<= 5分钟】通话，且这些人中只有不超过20%的人给回了电话，那么这个人就是诈骗犯；

当相互有通话的诈骗犯是认为同一组；

输出按组内升序，组间按第一个组员升序的格式输出。　

使用邻接矩阵记录通过时间【累计通话时间】，然后分别记录每个人满足要求的打出的电话人数以及回电话的人数，最后将相互通话的嫌疑犯视为一组。

3. AC代码

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn = 1010;
int graph[maxn][maxn];
int call[maxn]={};
int back[maxn]={};
int suspect[maxn]={};
int team[maxn]={};
vector<int> ans[maxn];
bool cmp(int a,int b){
	return a<b;
}
int main(){
	fill(graph[0],graph[0]+maxn*maxn,0);
	int k,n,m;
	scanf("%d%d%d",&k,&n,&m);
	for (int i = 0; i < m; ++i)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		graph[a][b]+=c;
	}
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= n; ++j)
		{
			if (graph[i][j]>0&&graph[i][j]<=5)
			{
				call[i]++;
				if (graph[j][i]>0)
				{
					back[i]++;
				}
			}
		}
	}
	int idx = 0;
	for (int i = 1; i <= n; ++i)
	{
		if (call[i]>k&&call[i]>=back[i]*5)
		{
			team[i]=i;
			suspect[idx++]=i;
		}
	}
	//printf("%d\n", idx);
	for (int i = 0; i < idx; ++i)
	{
		for (int j = i+1; j < idx; ++j)
		{
			if (graph[suspect[i]][suspect[j]]>0
				&&graph[suspect[j]][suspect[i]]>0)
			{
				team[suspect[j]]=team[suspect[i]];
			}
		}
	}
	for (int i = 1; i <= n; ++i)
	{
		if (team[i]>0)
		{
			ans[team[i]].push_back(i);
		}
	}
	if (idx==0)
	{
		printf("None\n");
	}else{
		for (int i = 1; i <= n; ++i)
		{
			if (ans[i].size()>0)
			{
				sort(ans[i].begin(),ans[i].end(),cmp);
				for (int j = 0; j < ans[i].size(); ++j)
				{
					printf("%d",ans[i][j]);
					if (j<ans[i].size()-1)
					{
						printf(" ");
					}else{
						printf("\n");
					}
				}
			}
		}

	}
	
	return 0;
}