PAT 1034 Head of a Gang [图的遍历] [DFS] [map处理string和int的互相转化]

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 threthold 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

---------------------------------------这是题目和解题的分割线---------------------------------------

参考的书上代码，这道题有好几个点需要注意，就写在注释里吧。

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

//由于通话记录最多1000，那么人数最多可能是1000*2 
#define maxN 2019
 
using namespace std;

int N,K,num = 0,memberNum,totalValue,head;
//要求权值最大的点位该连通块的头头，所以可以在输入时边用weight记录 
int G[maxN][maxN] = {},vis[maxN] = {},weight[maxN] = {};
//由于输入输出是字符串，中间处理又要转换为整型，所以不妨开两个map，用来相互转换。
map<string,int> stringToInt;
map<int,string> intToString;
//输出要求字典序，用map可以自动排序 
map<string,int> out;

//string转int，便于图的遍历 
int FxToInt(string str)
{
	//如果该字符串没出现过（用==end来判断 
	if(stringToInt.find(str)==stringToInt.end())
	{ 
		stringToInt[str] = num; //字符串转整型 
		intToString[num] = str; //整型转字符串 
		return num++; //返回时顺便自增 
	}
	else return stringToInt[str]; //出现过直接返回 
}

//遍历连通块 
void dfs(int index)
{
	memberNum++; //成员人数+1 
	vis[index] = 1; //进来了就代表上一层通过考核，要标记为访问过了 
	//更新头头 
	if(weight[index]>weight[head])
		head = index;
	//枚举所有人 
	for(int i=0;i<num;i++)
	{ 
		//寻找有关联的边 
		if(G[index][i])
		{
			//由于存在环的情况，必须先累加再判断是否访问，否则会漏边
			//又由于这样做回导致重复累加，所以在累加后直接将这条边删除，即置为0 
			totalValue += G[index][i];
			G[index][i] = G[i][index] = 0; //删除该边	
			if(!vis[i]) dfs(i); //如果没访问过，访问 
		}
	}
}

//图的遍历 
void DFSTravel()
{
	for(int i=0;i<num;i++)
	{
		//如果该结点没有访问过 
		if(!vis[i])
		{
			//每次循环置总权值为0,成员人数为0，头头为当前结点 
			totalValue = 0,memberNum = 0,head = i;
			//遍历连通块
			dfs(i); 
			//如果该连通块的总权值大于K，成员超过2人，记录该连通块 
			if(totalValue>K&&memberNum>2)
			//将该连通块的头头head转换为整型 
				out[intToString[head]] = memberNum;	
		}			
	}
}

int main()
{
	int i,j,v;
	cin>>N>>K;
	for(i=0;i<N;i++)
	{
		string str1,str2;
		cin>>str1>>str2>>v;
		int x1 = FxToInt(str1);
		int x2 = FxToInt(str2);
		weight[x1] += v; //读入点的权值 
		weight[x2] += v;
		G[x1][x2] += v; //读入边的权值（无向图 
		G[x2][x1] += v;
	}
	DFSTravel(); //图的遍历
	//输出满足要求的连通块数量 
	cout<<out.size()<<endl; 
	//输出连通块的头头和成员人数 
	for(map<string,int>::iterator it=out.begin();it!=out.end();it++)
	{
		cout<<it->first<<" "<<it->second;
		cout<<endl;
	}
	return 0;
}