题解 | #Head of a Gang#

//土尔逊Torson 编写于2023/07/04
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <cstring>
#include <vector>
#include <map>

using namespace std;

map<string, string>BOSS;
map<string, int> weight;
map<string, int>gang_weight;

string Find13401(string name) {
	if (BOSS.find(name) != BOSS.end()) {
		if (BOSS[name] != name) {
			return Find13401(BOSS[name]);
		}
	}
	else {
		BOSS[name] = name;
	}
	return BOSS[name];
}

void Union13401(string x, string y) {
	x = Find13401(x);
	y = Find13401(y);
	BOSS[x] = y;
}

int main() {
	int n, k;
	while (scanf("%d%d", &n, &k) != EOF) {
		for (int i = 0; i < n; ++i) {
			string name1, name2;
			int time;
			cin >> name1 >> name2 >> time;
			Union13401(name1, name2);
			weight[name1] += time, weight[name2] += time;
		}

		vector<string> gang_leader;
		for (auto it = BOSS.begin(); it != BOSS.end(); ++it) {
			if (it->first == it->second) {
				gang_leader.push_back(it->second);
			}
		}

		int gangs = 0;
		vector<string> gang_name;
		vector<int> gang_member;
		for (int i = 0; i < gang_leader.size(); ++i) {
			int member = 0;
			int weight_sum = 0;
			int leader_weight = 0;
			string leader_name;
			for (auto it = BOSS.begin(); it != BOSS.end(); ++it) {
				if (Find13401(it->first) == gang_leader[i]) {
					if (weight[it->first] > leader_weight) {
						leader_weight = weight[it->first];
						leader_name = it->first;
					}
					weight_sum += weight[it->first];
					member++;
				}
			}

			if (member >= 3 && weight_sum > k * 2) {
				gangs++;
				gang_name.push_back(leader_name);
				gang_member.push_back(member);
			}
		}
		printf("%d\n", gangs);
		for (int i = 0; i < gangs; ++i) {
			printf("%s %d\n", gang_name[i].c_str(), gang_member[i]);
		}
		BOSS.clear();
		weight.clear();
	}
	system("pause");
	return EXIT_SUCCESS;
}
// 64 位输出请用 printf("%lld")