Pat grade a A1034 head of a gang

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.

Sample Input 1:

8 59
AAA BBB 10
BBB AAA 20
AAA CCC 40
DDD EEE 5
EEE DDD 70
FFF GGG 30
GGG HHH 20
HHH FFF 10

Sample Output 1:

2
AAA 3
GGG 3

Sample Input 2:

8 70
AAA BBB 10
BBB AAA 20
AAA CCC 40
DDD EEE 5
EEE DDD 70
FFF GGG 30
GGG HHH 20
HHH FFF 10

Sample Output 2:

0

The question （ Sample analysis ）：

give 8 A call log , Give a threshold 59, And then down 8 A call log , The first and second strings are the names of the two people who made the call , trailing 10 It refers to the talk time , Find out how many criminal gangs there are （ That is, find the number of connected blocks , I made a phone call with the members of the Group , What matters is in a connected block ）, The name of the leader of each criminal gang and the number of people in the gang （ The leader is the one with the longest talk time in the Unicom block ）.

Ideas ：
Use a two-dimensional array to store graphs , Edge right is the talk time , It depends on how long this person has been talking , After building the map , Traverse the connected blocks in the graph , Depth first search to find the members in the connected graph , A connecting block is a criminal gang , The leader who has the greatest power to find a point is , The number of vertices in the connected block is the number of people in the Group , Use one Map Store the name of the gang leader and the number of people in the gang , because map It can sort automatically , So as to meet the requirements of the topic, according to the dictionary order of names, from small To large arrangement .

Code ：

#include<iostream>
#include<map>
using namespace std ;
const int maxn = 2010;// most 1000 Group call records , At most 2000 Personal call ;
int G[maxn][maxn] = {0};// Border right  
int weight[maxn] = {0};// Point right ;
int n, k, w, numPerson = 0;
bool vis[maxn] = {false};

map<string, int > stringToNum; // name -> Number ; 
map<int, string > numToString;// Number -> name  
map<string ,int > Gang;// Store the name of the leader and the number of groups ; 


int create(string s) {// Create mapping , Number all vertices in the graph ; 
	if(stringToNum.find(s) != stringToNum.end( )) { 
		return stringToNum[s];
	} else {
		stringToNum[s] = numPerson;
		numToString[numPerson] = s;
		return numPerson++;// Count the number of people participating in the call , Call record n != numPerson; 
	}
}

// Dig out the connecting block ;
void DFS(int nowVistor, int& head,int& numMember, int& totalValue) {// Call stacks interact , So as to calculate the final three values ; 
	vis[nowVistor] = true;
	numMember++;
	if(weight[nowVistor] > weight[head]) head = nowVistor;	
	for(int i = 0; i < numPerson; i++) {// Traverse all vertices ; 
		if(G[nowVistor][i] > 0) {// These vertices are directly connected ;
		totalValue += G[nowVistor][i];//totalValue Calculate the edge weight of the connected block ; 
		G[nowVistor][i] = 0;// Delete the edge after it has been calculated ; 
		G[i][nowVistor] = 0; 
			if(vis[i] == false) {// Ensure to traverse each edge , Each vertex , No weight, no leakage ; 
				DFS(i, head, numMember, totalValue); 
			} 
		}
	}
}

// Find connected blocks ;
void DFSTravel( ) {
	for(int i = 0; i < numPerson; i++) {// Traverse all vertices ; 
		if(vis[i] == false) {
			int nowVistor, head = i, numMember = 0, totalValue = 0;// Connected block initialization ;
			 
			DFS(i, head, numMember, totalValue);// After traversal, judge the number and total edge weight ; 
			if(numMember > 2 && totalValue > k) {
				Gang[numToString[head] ] = numMember;//map Automatically arrange from small to large ; 
			}
		}
	}
} 
int main() {
	scanf("%d %d", &n, &k);
	string str1, str2;
	for(int i = 0; i < n; i++) {
		cin >> str1 >> str2 >> w;// Enter the caller's name and , Talk time ;
		int id1 = create(str1);
		int id2 = create(str2);
		G[id1][id2] += w;// Edge weights are cumulative , There may be call records of the same people ; 
		G[id2][id1] += w;
		weight[id1] += w;
		weight[id2] += w;
	}
	DFSTravel( );// Ergodic graph ;
	printf("%d\n",Gang.size( ));// Number of gang groups ;
	for(map<string, int > :: iterator it = Gang.begin( ); it != Gang.end( ); it++) {
		cout<< it->first << " " << it->second << "\n";
	}
	return 0; 
}