关于算法-数据结构:PAT甲级2019年春季考试-73-Telefraud-Detection

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.

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.

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.

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.

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。

#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;
}

#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;
}

关于算法-数据结构:PAT甲级2019年春季考试-73-Telefraud-Detection

7-3 Telefraud Detection (25 分)

Input Specification:

Output Specification:

Sample Input 1:

Sample Output 1:

Sample Input 2:

Sample Output 2:

题目限度：

题目粗心：

算法思路：

预处理：

DFS 解法：

并查集解法：

留神点：

提交后果：

AC 代码 1：

AC 代码 2：