题目
题目链接
题解
并查集。
注意坑点：帮派的人数必须大于2。
代码
#include<bits/stdc++.h>using namespace std;#define PSI pair<string,int>const int N = 1e5+10;int n, k, cnt;int fa[N];int gongw[N]; // 每个人对于帮派的贡献，同一个通话只用记录一个人的，因为如果两个人都修改gongw，最后累加的时候会变成两倍 int w[N]; // 每个人的通话时间，两个人都要加，为了找帮派首领 int num[N]; // num[i] 表示以i为代表的帮派的人数，注意，代表与首领的不同，代表是find(x)，而首领只是本题中的概念 int head[N]; // head[i] 表示以i为代表的帮派的首领 int teamw[N]; // teamw[i] 表示以i为代表的帮派的总权重，累加该帮派的gongw即可 map<string, int> nti; // name to int：将名字转为对应的索引 map<int, string> itn; // int to name：将索引转为对应的名字 set <int> s;vector <PSI> v;int find (int x) {return fa[x] == x ? x : fa[x] = find (fa[x]);}void join (int x, int y) {int rx = find (x), ry = find (y);if (rx != ry) fa[rx] = ry;}int main(){cin >> n >> k;for (int i = 0;i < N;i ++) fa[i] = i;for (int i = 0;i < n;i ++) {string aa, bb;int c, a, b;cin >> aa >> bb >> c;if (!nti[aa]) nti[aa] = ++ cnt, itn[cnt] = aa;a = nti[aa];if (!nti[bb]) nti[bb] = ++ cnt, itn[cnt] = bb;b = nti[bb];join (a, b);gongw[a] += c;w[a] += c;w[b] += c;}for (int i = 1;i <= cnt;i ++) {int rt = find (i);num[rt] ++;teamw[rt] += gongw[i];head[rt] = w[head[rt]] < w[i] ? i : head[rt]; // 看看是否要换首领 if (teamw[rt] > k) s.insert (rt);}for (int item : s) if (num[item] > 2) // !!!帮派人数必须大于2，题目要求的 v.push_back ({itn[head[item]], num[item]});sort (v.begin(), v.end());cout << v.size() << endl;for (int i = 0;i < v.size();i ++) cout << v[i].first << ' ' << v[i].second << endl;return 0;}
