PAT A1158 Telefraud Detection (25point(s))

Scroll Down

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 (≤$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

解答

#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

vector<int> parent;
map<int, set<int>> tmpAns;
vector<set<int>> ans;

int Find(int a) {
	if (a != parent[a]) return parent[a] = Find(parent[a]);
	return a;
}

void Union(int a, int b) {
	int pa = Find(a), pb = Find(b);
	if (pa != pb) parent[pa] = pb;
	
}

int main()
{
	int k, n, m, c, r, d;
	scanf("%d %d %d", &k, &n, &m);
	map<int, bool> sus;
	vector<vector<int>> adj(n + 1, vector<int>(n + 1, 0));
	parent.resize(n + 1);
	for (int i = 1; i <= n; i++) parent[i] = i;
	for (int i = 0; i < m; i++) {
		scanf("%d %d %d", &c, &r, &d);
		 adj[c][r] += d;
	}

	for (int i = 1; i <= n; i++) {
		int callOutcount = 0, callBackcount = 0;
		for (int j = 1; j <= n; j++) {
			if (adj[i][j] > 0 && adj[i][j] <= 5) { //等号,测试点5
				callOutcount++;
				if (adj[j][i] != 0) callBackcount++;
			}
		}
		if (callOutcount > k && callBackcount <= 0.2*callOutcount) 
			// 坑点1 取等号 测试点3
			// 坑点2 callBackcount <= 0.2*k,这里k是阈值,所以不等式错误 测试点2
			sus[i] = true;
	}

	if (sus.empty()) {
		printf("None");
		return 0;
	}

	for (auto it1 = sus.begin(); it1 != sus.end(); it1++) {
		for (auto it2 = it1; it2 != sus.end(); it2++) {
			if (adj[it1->first][it2->first] && adj[it2->first][it1->first]) 
				Union(it1->first, it2->first);	
		}
	}

	for (int i = 1; i <= n; i++) {
		if (sus.find(i) != sus.end()) tmpAns[Find(i)].insert(i);
	}

	for (auto it = tmpAns.begin(); it != tmpAns.end(); it++) {
		set<int> gang = it->second;
		ans.push_back(gang);
	}
	sort(ans.begin(), ans.end(), [](set<int> s1, set<int> s2) {
		return *s1.begin() < *s2.begin();
	});

	for (auto it = ans.begin(); it != ans.end(); it++) {
		set<int> gang = *it;
		int i = 0;
		for (auto it2 = gang.begin(); it2 !=gang.end(); it2++, i++)
			printf("%d%s", *it2, i == gang.size() - 1 ? "\n" : " ");
	}
	return 0;
}