AcWing 1518. 团伙头目
原题链接
中等
作者:
RainSure
,
2022-02-28 15:30:01
,
所有人可见
,
阅读 149
这得把STL用到多熟练啊
#include<iostream>
#include<cstring>
#include<vector>
#include<unordered_map>
#include<algorithm>
using namespace std;
#define x first
#define y second
unordered_map<string, vector<pair<string, int>>> v;
unordered_map<string, int> total;
unordered_map<string, bool> st;
int n, m;
int dfs(string ver, vector<string> &nodes)
{
int sum = 0;
st[ver] = true;
nodes.push_back(ver);
for(auto item : v[ver]){
sum += item.y;
string cur = item.x;
if(!st[cur]) sum += dfs(cur, nodes);
}
return sum;
}
int main()
{
cin >> n >> m;
while(n --)
{
string a, b;
cin >> a >> b;
int c; cin >> c;
v[a].push_back({b, c});
v[b].push_back({a, c});
total[a] += c;
total[b] += c;
}
vector<pair<string, int>> res;
for(auto item : total){
vector<string> nodes;
string ver = item.x;
int sum = dfs(ver, nodes) / 2;
if(nodes.size() > 2 && sum > m){
string boss = nodes[0];
for(auto node : nodes){
if(total[node] > total[boss]){
boss = node;
}
}
res.push_back({boss, (int)nodes.size()});
}
}
sort(res.begin(), res.end());
cout << res.size() << endl;
for(auto item : res){
cout << item.x << " " << item.y << endl;
}
return 0;
}