题解 | Head of a Gang

#include<iostream>
#include<unordered_map>
#include<string>
#include<map>
#include<vector>
using namespace std;
const int N = 1010;
unordered_map<string, string>p;
unordered_map<string, int>gtime;
unordered_map<string, int>visit;
typedef pair<string, string> PSS;
string find(string str) {
	if (p[str] != str)p[str] = find(p[str]);
	return p[str];
}

void Union(string str1, string str2) {
	if (find(str1) != find(str2)) {
		//因为每个黑帮的头目是通话时间最长的
		//这里比较大小要比较根的大小，不然一下左插入，一下右插入会出错
		//这里要比较根的大小，一直让根的大小是最大的元素值，最后就是黑帮头目
		//若不用合并，则是同一个集合的，那么根结点和另外一个结点的权值都要加，所以肯定还是根结点是头目
		//只有要合并时才有可能更换头目
		if (gtime[find(str1)] < gtime[find(str2)])p[find(str1)] = find(str2);
		else p[find(str2)] = find(str1);
	}
}
int main() {
	int n, k;
	while (cin >> n >> k) {
		vector<PSS> v;
		while (n--) {
			string str1, str2;
			int weight;
			cin >> str1 >> str2 >> weight;
			if (visit.count(str1) == 0) {
				p[str1] = str1;
				visit[str1] = 1;
			}
			if (visit.count(str2) == 0) {
				p[str2] = str2;
				visit[str2] = 1;
			}
			
			gtime[str1] += weight;
			gtime[str2] += weight;
			v.push_back(make_pair(str1, str2));
			//由于要找黑帮头目，得知道所有人的童话时间才能合并
			/*Union(str1, str2);*/
		}
		for (auto it = v.begin(); it != v.end(); it++) {
			Union(it->first, it->second);
		}
		//这里用map就默认字典序了
		map<string, int>sum;
		map<string, int>count;
		for (auto it = p.begin(); it != p.end(); it++) {
			string root = find(it->first);
			sum[root] = sum[root] + gtime[it->first];
			count[root]++;
		}
		//由于本题还要先提前输出有几个帮派，只能把结果保存下来
		//由于将所有时间都加起来，相当于通话时间乘了两倍
		map<string, int>res;
		for (auto it = sum.begin(); it != sum.end(); it++) {
			if (sum[it->first] > k*2 && count[it->first] > 2) {
				res[it->first] = count[it->first];
			}
		}
		cout << res.size() << endl;
		for (auto it = res.begin(); it != res.end(); it++) {
			cout << it->first << ' ' << it->second << endl;
		}
		//新的一组要清空数据
		p.clear();
		gtime.clear();
		visit.clear();
	}
	
	return 0;
}
//题目有难读懂，还容易错，好烦啊