1034. Head of a Gang (30)

One way that the police finds the head of a gang is to check people's phone calls. If there is a phone call between A and B, we say that A and B is related. The weight of a relation is defined to be the total time length of all the phone calls made between the two persons. A "Gang" is a cluster of more than 2 persons who are related to each other with total relation weight being greater than a given threshold K. In each gang, the one with maximum total weight is the head. Now given a list of phone calls, you are supposed to find the gangs and the heads.

Input Specification:

Each input file contains one test case. For each case, the first line contains two positive numbers N and K (both less than or equal to 1000), the number of phone calls and the weight threthold, respectively. Then N lines follow, each in the following format:

Name1 Name2 Time

where Name1 and Name2 are the names of people at the two ends of the call, and Time is the length of the call. A name is a string of three capital letters chosen from A-Z. A time length is a positive integer which is no more than 1000 minutes.

Output Specification:

For each test case, first PRint in a line the total number of gangs. Then for each gang, print in a line the name of the head and the total number of the members. It is guaranteed that the head is unique for each gang. The output must be sorted according to the alphabetical order of the names of the heads.

8 59AAA BBB 10BBB AAA 20AAA CCC 40DDD EEE 5EEE DDD 70FFF GGG 30GGG HHH 20HHH FFF 10Sample Output 1:
2AAA 3GGG 3Sample Input 2:
8 70AAA BBB 10BBB AAA 20AAA CCC 40DDD EEE 5EEE DDD 70FFF GGG 30GGG HHH 20HHH FFF 10Sample Output 2:
0
/*#include<iostream>#include<cstdio>#include<vector>#include<string>#include<set>#include<algorithm>using namespace std;const int maxn = 26 * 26 * 26;set<int> V;int String2Int(string s){	int sum = 0;	for (int i = 0; i < 3; i++)	{		sum += (s[2-i] - 'A')*pow(26, i);	}	return sum;}string Int2String(int hash){	string s = "AAA";	for (int i = 0; i < 3; i++)	{		s[2-i] += hash % 26;		hash /= 26;	}	return s;}int G[maxn][maxn] = { 0 };bool vis[maxn] = { false };int gangmembers = 0;int personaltotalweight[maxn] = { 0 };int totalweight = 0;int maxtotalweight = 0;int head_gangmembers[maxn] = { 0 };int head;int N, K;vector<int> heads;void DFS(int u){	vis[u] = true; gangmembers++;	if (maxtotalweight <= personaltotalweight[u])	{		maxtotalweight = personaltotalweight[u];		head = u;	}	for (set<int>::iterator it = V.begin();		it!=V.end();it++)	{		if (G[u][*it]>0)//這里一定要注意無向圖的特性，若存儲還是按有向圖存儲，		//那么對無向圖遍歷時則注意使相鄰點只滿足弱連通即可		{			totalweight += G[u][*it];			G[u][*it] = G[*it][u] = 0;//防止回頭			if(!vis[*it])			DFS(*it);		}		//personaltotalweight[u] += G[u][*it] + G[*it][u];//統計時也要注意是否能放在if語句內	}}void DFSTrave(){	for (set<int>::iterator it = V.begin();		it != V.end(); it++)	{		gangmembers = 0;		totalweight = 0;		maxtotalweight = 0;//這樣的重置條件不能輕易放在if語句中		if (!vis[*it])		{			DFS(*it);			if (gangmembers > 2 && totalweight > K)			{				heads.push_back(head);				head_gangmembers[head] = gangmembers;			}		}	}}int main(){	scanf("%d %d", &N, &K);	string s1, s2; int weight;	for (int i = 0; i < N; i++)	{		cin >> s1 >> s2 >> weight;		int i1 = String2Int(s1);		int i2 = String2Int(s2);		G[i1][i2] += weight;//注意兩個相同的人可能不止是一次AAA BBB 10，下一個還可能是AAA BBB 20		G[i2][i1] += weight;		personaltotalweight[i1] += weight;		personaltotalweight[i2] += weight;		V.insert(i1);		V.insert(i2);	}	DFSTrave();	cout << heads.size()<<endl;	for (int i = 0; i < heads.size(); i++)	{		cout << Int2String(heads[i]) << " "			<< head_gangmembers[heads[i]] << endl;	}	return 0;}*//*這題不知道為什么，調了一晚上還調不好，就剩2號測試點過不了。最開始自己寫就是2號過不了然后對照別人AC的代碼改還是AC不了，不知道為啥。可能我用set的緣故，因為其他人都沒用set但我自己又感覺問題應該不是出現在set上。唉，DEBUG折壽啊，腦殼痛╭(╯^╰)╮。下面貼上別人ac的代碼*/#include<iostream>#include<string>#include<map>#include<vector>using namespace std;const int M = 26 * 26 * 26;	//結點最大數目vector<int> v[M];	//圖的鄰接表表示vector<int> node;	//存儲遍歷的起點int visited[M] = { 0 };int w[M] = { 0 };	//存儲每個人的通話時長int n, k;	//k是閾值int cnt = 0;//達標的幫派數目int pnum;	//一個幫派的成員數int maxtime;//成員中的最大通話時長int headtime;//頭目通話時長int headId;//頭目idint toId(string &s);//字符串名字轉換為數字編號string toName(int x);//編號轉換為名字，用于輸出void dfs(int start);//dfs算法int main(){	//freopen("in.txt", "r", stdin);	cin >> n >> k;	for (int i = 0; i < n; i++)//讀入數據，同時轉換成數字編號	{		string s1, s2;		int wgt;		cin >> s1 >> s2 >> wgt;		int d1 = toId(s1);		int d2 = toId(s2);		v[d1].push_back(d2);		v[d2].push_back(d1);		w[d1] += wgt;		w[d2] += wgt;		node.push_back(d1);//稀疏邊，存儲遍歷的起點。這樣不需要從0一個個遍歷了	}	map<string, int> h_map;//利用map的有序性，存儲頭目信息	vector<int>::iterator it;	for (it = node.begin(); it < node.end(); it++)	{		pnum = 0;		maxtime = 0;		headtime = 0;		if (visited[*it] == 0)			dfs(*it);		if (pnum > 2 && maxtime > 2 * k)//判斷是否符合條件的幫派		{			cnt++;			string name = toName(headId);			h_map[name] = pnum;		}	}	cout << cnt << endl;//輸出	if (cnt != 0)	{		map<string, int>::iterator it;		for (it = h_map.begin(); it != h_map.end(); it++)			cout << it->first << ' ' << it->second << endl;	}	return 0;}int toId(string &s)//字符串名字轉換為數字編號{	return ((s[0] - 'A') * 26 * 26 + (s[1] - 'A') * 26 + (s[2] - 'A'));}string toName(int x)//編號轉換為名字，用于輸出{	string s(3, 0);	s[2] = x % 26 + 'A';	s[1] = x / 26 % 26 + 'A';	s[0] = x / 26 / 26 + 'A';	return s;}void dfs(int start)//dfs算法, 里面用到的變量為便于遍歷，都設為全局變量{	visited[start] = 1;	pnum++;	maxtime += w[start];	if (w[start] > headtime)//更新頭目信息	{		headtime = w[start];		headId = start;	}	for (unsigned i = 0; i < v[start].size(); i++)//dfs遍歷鄰接點	{		if (visited[v[start][i]] == 0)			dfs(v[start][i]);	}	return;}