题目
分析
推荐：经典
dfs经典题 : 可直接用作同类型的模板
要点
- 字符串 和 整型的映射
- travel中还有一个条件判断
- dfs中用别名来实现数值的累加
知识点
题解
#include <iostream>
#include <map>
using namespace std;
map<string, int> stringToInt;
map<int, string> intToString;
map<string, int> ans; ///人民，权重
int idNumber = 1, k;
int stoifunc(string s) { ///将字符串转换成数字，以便后面做图搜索
if(stringToInt[s] == 0) { ///如果没有
stringToInt[s] = idNumber;
intToString[idNumber] = s;
return idNumber++;
} else {
return stringToInt[s];
}
}
int G[2010][2010], weight[2010]; ///给的范围要根据题意来
bool vis[2010];
void dfs(int u, int &head, int &numMember, int &totalweight) { ///三个别名
vis[u] = true; ///已查
numMember++; ///人数++
if(weight[u] > weight[head]) ///边界条件的处理
head = u;
for(int v = 1; v < idNumber; v++) {
if(G[u][v] > 0) { ///有路可去
totalweight += G[u][v];
G[u][v] = G[v][u] = 0; ///为什么要置零呢
if(vis[v] == false) ///还未去过的点
dfs(v, head, numMember, totalweight);
}
}
}
void dfsTrave() {
for(int i = 1; i < idNumber; i++) {
if(vis[i] == false) { ///开始搜索
int head = i, numMember = 0, totalweight = 0;
dfs(i, head, numMember, totalweight);
if(numMember > 2 && totalweight > k) ///如果人数大于2且过阈值
ans[intToString[head]] = numMember;
}
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("data.txt", "r", stdin);
#endif // ONLINE_JUDGE
int n, w;
cin >> n >> k;
string s1, s2;
for(int i = 0; i < n; i++) {
cin >> s1 >> s2 >> w;
int id1 = stoifunc(s1);
int id2 = stoifunc(s2);
weight[id1] += w; ///每个点的总权重
weight[id2] += w;
G[id1][id2] += w; /// A->B + B->A == A-B
G[id2][id1] += w;
}
dfsTrave();
cout << ans.size() << endl;
for(auto it = ans.begin(); it != ans.end(); it++)
cout << it->first << " " << it->second << endl;
return 0;
}