PAT 找电话诈骗团伙

满分

/**
题意:
判断一个id是否是诈骗人,首先看短通话数量中回电话少于20%的 (可以利用除法)
在判断是否是一个团伙

QES:
为啥5算是诈骗人呢?
就是1-5 多条数据,只算最大的一条,最大的一条有用

核心:different 和 short phone

*/
#include <iostream>
#include <cstring>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
const int N = 1010;
int g[N][N];
int p[N];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int main()
{
    int k, m, n;
    cin >> k >> m >> n;
    while (n --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] += c; // 这一步应该是累加的
    }
    vector<int> vc;
    for(int i = 1; i <= m; i++)
    {
        int cnt = 0, back = 0;
        for(int j = 1; j <= m; j++)
        {
            // 这里g[i][j]是<= 5 不是 k
            if (g[i][j] && g[i][j] <= 5)
            {
                cnt++;
                if (g[j][i]) back++;
            }

        }
        if ((double) back / cnt <= 0.2 && cnt > k) vc.push_back(i);
    }
    unordered_map<int, vector<int>> res;
    // 处理是否一个gang
    if (vc.empty()) puts("None");
    else
    {
        for(int i = 0; i < vc.size(); i++) p[vc[i]] = vc[i];
        for(int i = 0; i < vc.size(); i++)
        {
            // 这里是最难想的
            for(int j = i + 1; j < vc.size(); j++)
            {
                int a = vc[i], b = vc[j];
                if (g[a][b] && g[b][a]) p[find(b)] = find(a);
            }
        }
        for(int i = 0; i < vc.size(); i++)
        {
            // p[vc[i]] 与 find(vc[i]) 区别
            // 必须是找最顶上的数据
            res[find(vc[i])].push_back(vc[i]);
        }
        vector<vector<int>> ve;
        for(auto &t : res)
        {
            ve.push_back(t.second);
        }
        sort(ve.begin(), ve.end());
        for(auto &t : ve)
        {
            bool flag = true;
            for(auto &k : t)
            {
                if (flag) flag = false;
                else printf(" ");
                printf("%d", k);
            }
            printf("\n");
        }
    }

}

19分 三个错误

#include <iostream>
#include <cstring>
#include <vector>
#include <unordered_set>
using namespace std;

const int N = 1010, time = 5, day = 1441;
int g[N][N];
int m, n, k;
bool visit[N];
void check(vector<int> &res)
{

    for(int i = 1; i <= n; i++)
    {
        unordered_set<int> hset;
        vector<int> dur(n + 2);
        //memset(dur, 6, sizeof dur);

        unordered_set<int> back;
        for(int j = 1; j <= n; j++)
        {
            if (g[i][j] <= time)
            {
                dur[j] += g[i][j];

                if (g[j][i] < day) back.insert(j);
            }

        }
        // total duration 一定要谨慎,不然又错了
        for(int j = 1; j <= n; j++){
            if (dur[j] > 0 && dur[j] <= time){
                hset.insert(j);
            }
        }
        // 判断是否超过20%, 不同人是否超过m
        if (hset.size() > m)
        {
            int x =  0.2 * hset.size();
            if (back.size() <= x) res.push_back(i);
        }
    }
}
int main()
{
    memset(g, 0x3f, sizeof g);

    cin >> m >> n >> k;
    while (k --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = c;

    }
    // 遍历图找到 嫌疑犯
    vector<int> res;
    check(res);

    // 判断res团伙
    vector<int> vc[res.size()];
    for(int i = 0; i < res.size(); i++)
    {
        int x = res[i];
        if (!visit[x])
        {
            vc[i].push_back(x);
        }
        visit[x] = true;
        for(int j = i + 1; j < res.size(); j++)
        {
            int y = res[j];
            if (g[x][y] < day && visit[y] == false) {
                visit[y] = true;
                vc[i].push_back(y);
            }
        }

    }
    for(int i = 0;i < res.size(); i++) {
        for(int j = 0; j < vc[i].size(); j++)
        {
            printf("%d", vc[i][j]);
            if (j != vc[i].size() - 1) printf(" ");
        }
        if (vc[i].size() > 0) printf("\n");
    }
}