1034. Head of a Gang

考察并查集。发现并查集什么都不会呀。。。

查看了大神的代码感觉自己太弱了 http://blog.csdn.net/sunbaigui/article/details/8657148

代码照抄的 就是注释了下。留着当笔记吧。 学习了下map set 迭代器 的使用 还是有点不熟练，还要多练。。

感觉这里开始PAT题的类型突然变了。。

#include <iostream>#include <string>#include <vector>#include <map>#include <set>#include <algorithm>#define MAX 1010using namespace std;struct Call {	string p1, p2;	int time;};struct Node {	int weight, parent;};struct Gang {	int head, num, sum, maxw;	Gang() { head = -1; num = 0; sum = 0; maxw = -1; }};vector <Call> list;vector <Node> p; //并查集set <string> name;map <string, int> str2int;map <int, string> int2str;int NameNum;int N, threthold;void InitSet() {	p.resize(NameNum);	for (int i = 0; i < NameNum; i++) {		p[i].parent = i; p[i].weight = 0; //当父母为自己时为根节点	}}//结点压缩//		①					 ①//		|				   /   ///		②   压缩成		 ②		③//		|//		③void ComPRessSet(int top, int x) { //路径压缩    	if (top != p[x].parent) {//不是并查集的根结点		CompressSet(top, p[x].parent); //继续压缩		p[x].parent = top;	}}int FindSet(int x) {//查找根节点	if (x != p[x].parent) { //不是根结点		int top = FindSet(p[x].parent); //top为根结点		CompressSet(top, x); //压缩结点	}	return p[x].parent;//返回根节点}void UnionSet(int x, int y) {	int a = FindSet(x);	int b = FindSet(y);	p[a].parent = b;}bool cmp(Gang g1, Gang g2) {	return int2str[g1.head] < int2str[g2.head];}int main() {	cin >> N >> threthold;	Call temp;	for (int i = 0; i < N; i++) {		cin >> temp.p1 >> temp.p2 >> temp.time;		list.push_back(temp);		name.insert(temp.p1);		name.insert(temp.p2);	}	NameNum = name.size();	//名字转换为编号	set<string>::iterator it;	int id = 0;	for (it = name.begin(); it != name.end(); it++, id++) {		str2int[*it] = id;		int2str[id] = *it;	}	InitSet();	for(int i = 0; i < list.size(); i++){		int u = str2int[list[i].p1];		int v = str2int[list[i].p2];		p[u].weight += list[i].time;		p[v].weight += list[i].time;		UnionSet(u, v);	}#ifdef _DEBUG	for (int i = 0; i < p.size(); i++) {		cout << int2str[i] << " " << int2str[p[i].parent] << " " << int2str[FindSet(i)] << endl;	}#endif	map <int, Gang> allset; // fitst = int second = Gang	map <int, Gang>::iterator it2;	for (int i = 0; i < NameNum; i++) {		int top = FindSet(i);		it2 = allset.find(top);//查找根节点的帮会集合		if (it2 != allset.end()) {			allset[top].sum += p[i].weight;			allset[top].num++;			if (p[i].weight > allset[top].maxw) {				allset[top].maxw = p[i].weight;				allset[top].head = i;			}		}		else {//没有 新建帮会			Gang temp;			temp.head = i; temp.maxw = p[i].weight;			temp.num = 1; temp.sum = p[i].weight;			allset[top] = temp;		}	}	vector <Gang> gang;	for (it2 = allset.begin(); it2 != allset.end(); it2++) {		if (it2->second.sum > 2 * threthold && it2->second.num > 2)			gang.push_back(it2->second);	}	sort(gang.begin(), gang.end(), cmp);	cout << gang.size() << endl;	for (int i = 0; i < gang.size(); i++) {		cout << int2str[gang[i].head] << " " << gang[i].num << endl;	}	system("pause");	return 0;}