A1158 Telefraud Detection (25 分)

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

题目大意：

电信诈骗在我们的社会仍然是一个常见的和持续的问题。 有些案例，毫无戒心的受害者失去了一生的积蓄。 为了阻止这种犯罪，你应该编写一个程序，从大量的电话记录中发现这些嫌疑人。

判断一个认为嫌疑人的条件：

1. 一个人每一天要打的短电话次数超过 K 次（短电话:两个人的通话总时长<=5分钟的电话），
2. 并且在这些短电话中不超过20%的人回电话

诈骗嫌疑人判断好了之后还要判断嫌疑人是否为同伙(gang): 只有两个嫌疑人之间互相打电话(不用判断是否为短电话), 才会被判定为犯罪同伙.

(PS: 判断是否为同伙时, 必须要双方都打过电话才是, 不是单方面打电话.) 这里坑了我好久好久???, 感觉做好PAT只需把题目读仔细读清楚就行???

思路

hash + 并查集

1. 运用hash map unordered_map<int, int> phone统计电话时间和每个人打的短电话次数

   • hash映射函数为 phone[caller * 10000 + receiver] = time, 这里表示caller 与 receiver之间打电话的时间. (边输入就边累加时间)
   • 通过题目条件判断一个人是否为诈骗嫌疑人

2. 嫌疑人中用并查集记录团伙

   • 输出时要记得排序, 我这里用的是 map, set自动排序

AC代码：

#include<bits/stdc++.h>
using namespace std;

unordered_map<int, int> phone;
const int hashValue = 10000;
vector<int> father;

int findFather(int x) {
    int a = x;
    while (x != father[x]) {
        x = father[x];
    }
    int z;
    while (a != father[a]) {
        z = a;
        father[z] = x;
        a = father[a];
    }
    return x;
}

void Union(int x, int y) {
    int fx = findFather(x);
    int fy = findFather(y);
    if (fx != fy) {
        father[fx] = father[fy] = min(fx, fy);
    }
}

int main() {
    int k, n, m;
    scanf("%d%d%d", &k, &n, &m);
//     if (n == 1000) return -1;
    for (int i = 0; i <= n; ++i) {
        father.emplace_back(i);
    }
    int c, r, d;
    for (int i = 0; i < m; ++i) {
        cin >> c >> r >> d;
        phone[c * hashValue + r] += d;
    }
    // statistic short time call of everyone, then confirm suspect;
    unordered_map<int, vector<int> > callCount;
    for (auto &p : phone) {
        if (p.second <= 5) {
            c = p.first / hashValue;
            r = p.first % hashValue;
            callCount[c].emplace_back(r);
        }
    }
    vector<int> suspect;
    for (auto &p : callCount) {
        int cnt = p.second.size();
        if (cnt > k) {
            int times = 0;
            c = p.first;
            for (int &re : p.second) {
                if (phone.find(re * hashValue + c) != phone.end()) {
                    ++times;
                }
            }
            if (times <= int(cnt * 0.2)) suspect.emplace_back(c);
        }
    }
    int sz = suspect.size();
    if (sz == 0) {
        printf("None\n");
        return 0;
    }
    for (int i = 0; i < sz - 1; ++i) {
        for (int j = i + 1; j < sz; ++j) {
            if (phone.find(suspect[i] * hashValue + suspect[j]) != phone.end() &&  ///// each other!!!!! there is &&, not ||
                phone.find(suspect[j] * hashValue + suspect[i]) != phone.end()) { 
                Union(suspect[i], suspect[j]);
            }
        }
    }
    map<int, set<int> > res;
    unordered_set<int> isSuspect(suspect.begin(), suspect.end());
    for (int i = 1; i <= n; ++i) {
        if (isSuspect.find(i) != isSuspect.end()) {
            res[findFather(i)].insert(i);
        }
    }
    for (auto &st : res) {
        bool isblank = false;
        for (int t : st.second) {
            if (isblank) printf(" ");
            if (!isblank) isblank = true;
            printf("%d", t);
        }
        printf("\n");
    }
    return 0;
}