AcWing 1518. 团伙头目(邻接矩阵DFS)
原题链接
中等
作者:
麦克斯韦妖_7
,
2021-08-30 16:38:14
,
所有人可见
,
阅读 230
#include <iostream>
#include <string>
#include <map>
using namespace std;
const int maxn = 2010;
int n, k;
int G[maxn][maxn] = {0}, weight[maxn] = {0};
bool vis[maxn] = {false};
int numPerson = 0;
map<string, int> stringToInt;
map<int, string> intToString;
map<string, int> Gang;
void DFS(int nowVisit, int &head, int &numMember, int &totalValue){
numMember ++;
vis[nowVisit] = true;
if(weight[nowVisit] > weight[head]){
head = nowVisit;
}
for(int i = 0; i < numPerson; i ++){
if(G[nowVisit][i] > 0){ //存在从nowVisit到i的边
totalValue += G[nowVisit][i]; //更新总权
G[nowVisit][i] = G[i][nowVisit] = 0; //删除该边,防止回头
if(vis[i] == false){ //i未被访问过
DFS(i, head, numMember, totalValue);
}
}
}
}
void DFSTrave(){
for(int i = 0; i < numPerson; i ++){
if(vis[i] == false){ //i点所在的连通块未被访问过
int head = i, numMember = 0, totalValue = 0;
DFS(i, head, numMember, totalValue);
// cout << totalValue << endl;
if(numMember > 2 && totalValue > k){ //满足条件的连通块存入map
Gang[intToString[head]] = numMember;
}
}
}
}
int change(string str){
if(stringToInt.find(str) != stringToInt.end()){
return stringToInt[str];
}else{
stringToInt[str] = numPerson;
intToString[numPerson] = str;
return numPerson ++;
}
}
int main(){
cin >> n >> k;
string str1, str2;
int w;
for(int i = 0; i < n; i ++){
cin >> str1 >> str2 >> w;
int id1 = change(str1);
int id2 = change(str2);
G[id1][id2] += w;
G[id2][id1] += w;
weight[id1] += w;
weight[id2] += w;
}
DFSTrave();
cout << Gang.size() << endl;
for(auto item : Gang){
cout << item.first << ' ' << item.second << endl;
}
return 0;
}