题解 | #Head of a Gang#

不断打补丁的做法，应该被丢到垃圾桶里面

#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <map>
#include <algorithm>
#include <vector>

using namespace std;

//思考一下：帮派的总权重存在根节点 个人权重可以另起一个map 

map<string, string> parent;
map<string, int> weight;

string Int2Str(int x){
	string ans;
	while(x){
		ans.push_back(x%10+'0');
		x/=10;
	}
	reverse(ans.begin(), ans.end());
	return ans;
}

int Str2Int(const string &s){
	int ans = 0;
	for(int i=0; i<s.size(); i++){
		ans *= 10;
		ans += s[i] - '0';
	}
	return ans;
}

string Find(const string &s){
	if(!parent.count(s)){//意味着是通过Find来建立这个新树 
		parent[s] = "0";
	}
	string stmp = parent[s];
	if(stmp[0] < 'A' || stmp[0] > 'Z'){//说明是根结点 
		return s;
	}else{
		return Find(stmp);
	}
}

void Union(string s1, string s2, int w){
	if(weight.count(s1)){
		weight[s1] += w;
	}else{
		weight[s1] = w;
	}
	if(weight.count(s2)){
		weight[s2] += w;
	}else{
		weight[s2] = w;
	}
	s1 = Find(s1);
	s2 = Find(s2);
	if(s1 != s2){
		int tmp1 = Str2Int(parent[s1]);
		int tmp2 = Str2Int(parent[s2]);
		parent[s1] = Int2Str(tmp1 + tmp2);
		parent[s2] = s1;
	}
	int tmp = Str2Int(parent[s1]);
	parent[s1] = Int2Str(tmp + w);
}

bool cmp(const string &s1, const string &s2){
	return weight[s1] > weight[s2];
}

bool cmp2(const vector<string> &v1, const vector<string> &v2){
	return v1[0] < v2[0];
}

int main(){
	int n, thresh;
	while(scanf("%d%d", &n, &thresh) != EOF){
		string s1, s2;
		int w;
		for(int i=0; i<n; i++){
			cin >> s1;
			cin >> s2;
			scanf("%d", &w);
			Union(s1, s2, w);
		}
		map<string, string>::iterator it;
		vector<string> gang;
		for(it=parent.begin(); it!=parent.end(); it++){
			string stmp = it->second;
			if(stmp[0] < 'A' || stmp[0] > 'Z'){
				if(Str2Int(parent[it->first]) > thresh){
					gang.push_back(it->first);
				}
			}
		}
		//暴力一点 
		int tag[gang.size()];
		int cnt = gang.size();
		memset(tag, 1, sizeof(tag)); 
		vector<string> g[gang.size()];
		for(int i=0; i<gang.size(); i++){
			for(it = parent.begin(); it != parent.end(); it++){
				if(Find(it->first) == gang[i]){
					g[i].push_back(it->first);
				}
			}
			sort(g[i].begin(), g[i].end(), cmp);
		}
		sort(g, g+gang.size(), cmp2);
		for(int i=0; i<gang.size(); i++){
			if(g[i].size() <= 2){
				cnt--;
				tag[i] = 0;
			}
		}
		printf("%d\n",cnt);
		for(int i=0; i<gang.size(); i++){
			if(!tag[i]){
				continue;
			}
			printf("%s %d\n", g[i][0].c_str(), g[i].size());
		}
		parent.clear();
		weight.clear();
	}
	return 0;
}