题解 | #Head of a Gang#

超级无敌复杂的并查集，先将所有输入保存排序，再合并已实现权值最大为根节点
#include<iostream>
#include<vector>
#include<map>
using namespace std;

int father[27]; //用1到26代表所有的帮派
int wei[27];
struct input {
	int a, b;
	int weight;
};

struct gang {
	int name;
	int weight =0;

};


void Init() 
{
	for (int i = 1; i <= 26; i++) 
	{
		father[i] = i;
		wei[i] = 0;
	}

}

int Find(int x) {
	if (father[x] != x) {
		father[x] = Find(father[x]);
	}
	return father[x];
}

void Union(int x, int y,gang g[]) {
	x = Find(x);
	y = Find(y);
	if (x != y) {

		if(g[x].weight > g[y].weight)
			father[y] = x;
		else {
			father[x] = y;
		}
	}

}

int main() {
	int n, m;
	while (cin >> n >> m) 
	{
		Init();
		vector<input> vec1; 
		gang g[27];
		int length;
		for (int i = 0; i < n; i++) {  //将所有帮派输入
			
			string str1, str2; 
			int weight;
			cin >> str1 >> str2 >> weight;
			length = str1.size();
			int a = str1[0] - 'A'+1, b = str2[0] - 'A'+1;
			input temp1; temp1.a = a; temp1.b = b; temp1.weight = weight;
			vec1.push_back(temp1);

			g[a].name = a;  g[a].weight += weight;
			g[b].name = b;	g[b].weight += weight;  //记录所有的权值
		}

		for(int i=0;i<vec1.size();i++){
			Union(vec1[i].a, vec1[i].b,g);
		}
		map<int, int> mymap1,mymap2;

		for (int i = 1; i <= 26; i++) {
			mymap1[Find(i)] ++;  //找到所有的帮派
			mymap2[Find(i)] += g[i].weight;
		}
		int index=0;

		for (int i = 1; i <= 26; i++) if (mymap1[i] > 2 && mymap2[i] > m*2) index++;
		cout << index << endl;

		for (int i = 1; i <= 26; i++) {
			if (mymap1[i] > 2&& mymap2[i] > m*2 ) {
				char temp = 'A' + i - 1;
				for (int index = 0; index < length; index++) {
					cout << temp;
				}
				cout << ' ' << mymap1[i] << endl;

			}
		}

		
	}
}