这道题的难点在于确定嫌疑人的的组别, 一开始理解错了, 以为一个诈骗团伙中任两个人都互相打过电话, 但其实是只要嫌疑人n跟诈骗团伙内的任意一个人互相打过电话, n就可以归为这个团伙内的人.
图的存储及嫌疑人判定
这部分较为简单, 直接上完整代码
//有向图矩阵, CallTime[a][b]表示a 给 b 打电话的总时长
int CallTime[MaxN][MaxN];
//判断n是否为嫌疑人
inline bool IsSuspect(int n){
int outNum = 0, inNum = 0;
for(int i=1; i<=N; i++){
if(CallTime[n][i] && CallTime[n][i] <= 5){
outNum++;
if(CallTime[i][n])
inNum++;
}
}
if(outNum <= K || outNum < inNum*5)
return false;
return true;
}
嫌疑人归类
用一个数组来保存嫌疑人的组别.
team[n] = 0时代表n的组别未确定
int team[MaxN];
这里很显然是图的遍历问题, 我们定义一个计数器int teamNum = 1;
.
首先我们在所有嫌疑人中找到一个未确定组别的嫌疑人n, 从n开始进行遍历, 这里我用的是BFS, 所有与n相互通话的嫌疑人都归为当前组别, 然后对这些嫌疑人进行遍历.BFS结束后, 计数器加一
最后所有的嫌疑人都确定了组别, 我们按teamNum从小到大依次输出各团伙即可
完整代码
//
// Created by trudbot on 2022/6/23.
//
#include <bits/stdc++.h>
#define MaxN 1001
using namespace std;
int N, K;
//有向图矩阵, CallTime[a][b]表示a 给 b 打电话的总时长
int CallTime[MaxN][MaxN];
int team[MaxN];
int teamNum = 1;
//判断n是否未嫌疑人
inline bool IsSuspect(int n){
int outNum = 0, inNum = 0;
for(int i=1; i<=N; i++){
if(CallTime[n][i] && CallTime[n][i] <= 5){
outNum++;
if(CallTime[i][n])
inNum++;
}
}
if(outNum <= K || outNum < inNum*5)
return false;
return true;
}
int main() {
int M;
cin >> K >> N >> M;
int a, b, time;
while(M--){
cin >> a >> b >> time;
CallTime[a][b] += time;
}
vector<int> suspect;
for(int i=1; i<=N; i++){
if(IsSuspect(i)){
suspect.push_back(i);
}
}
if(suspect.empty()){
cout << "None" << endl;
return 0;
}
int temp;
for(int i : suspect){
if(team[i] == 0){//找一个为确定组别的顶点作为起点
queue<int> q;
q.push(i);
while(!q.empty()){
temp = q.front();
q.pop();
//这个判断的意义在于, 一个顶点可能被多个与它双向连通的顶点加入队列
if(team[temp] != 0) continue;
team[temp] = teamNum;
for(int j : suspect){
if(team[j] == 0 && CallTime[temp][j] && CallTime[j][temp])
q.push(j);
}
}
teamNum++;
}
}
//输出
for(int i=1; i<teamNum; i++){
for(int j=1; j<=N; j++)
if(team[j] == i)
cout << j << " ";
cout << endl;
}
return 0;
}
有些地方处理得比较粗暴, 存在优化空间
作者:trudbot 结果: Accepted 通过了 11/11个数据 运行时间: 484 ms 运行空间: 5084 KB