作者: CHEN, Yue 单位: 浙江大学 时间限制: 400 ms 内存限制: 64 MB 代码长度限制: 16 KB 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 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
题目大意：
（英语能力有限，有些翻译可能不是特别准确） 警方找到一个团伙头目的一个方法是检测人们的通话纪录。如果A和B之间有通话纪录我们就说A和B有关系。一个关系的权重定义为这两人之间总的通话时长。一个团伙是他们之间的关系总权重（即总的通话时长）大于给定的K且人数大于2的一群人。每一个团伙中总权重最大（即通话时长最长）的那个人就是头目。现在给出一个通话列表，要求你找出其中的团伙和头目们。 输入 每一个输入文件包含一个测试样例。每一个测试样例的第一行有两个正数N和K（都小于等于1000），分别代表通话数和给定的权重。接下来有N行，每一行以如下的格式： Name1 Name2 Time Name1和Name2是通话的两个人的名字。Time是通话时长。每一个名字是从A-Z中选取的三个字母组成的字符串。时长是不大于1000分钟的正整数。 输出 对每一个测试样例，第一行输出总的团伙数。接下来对每一个团伙，在一行中输出团伙头目的名字和团伙的人数。每一个团伙的头目保证独一无二。输出必须以团伙头目名字的字母顺序排列。
int G[N][N] = { 0 }; //用整型二维数组存储图值为通话时间 int vertex[N] = { 0 }; //顶点数组值为这个人总的通话时间 int totalName = 1; //记录总的名字数目用于把名字和整型变量相映射以便建图 int visited[N] = { 0 }; //访问标记数组用于DFS int head; //用于记录头目 int totalMember; //用于记录成员总数 int totalNumber = 1; //用于记录总的团伙数目，因为快排需要使用第一个位置即0做哨兵，所以初值从1开始 int weight; //权值
/*结果结构体数组，每一个结果包含头目的名字（用数字代替，输出时映射为名字）和成员数量*/ structresult { int head; int totalMember; }results[N];
/*改进后的深度优先搜索*/ voidDFS(int G[][N], int v) { visited[v] = 1; totalMember++; //访问一个顶点成员数量+1 if (vertex[v]>vertex[head]) //如果该成员的通话时长大于之前记录的头目的时长，更新头目为此顶点 { head = v; } for (int w = 1; w < totalName; w++) { if (G[v][w]) //改进后的DFS先判断是否有边 { weight += G[v][w]; //权值+=边的值 G[v][w] = G[w][v] = 0; //访问结束后把边删除 if (!visited[w]) { DFS(G, w); } } } }
/*快速排序，对结果数字按字母序排序*/ intpartition(int low, int high) { results[0] = results[low];
string key = intToString[results[low].head];
while (low<high) { while (low<high&&intToString[results[high].head] >= key) { high--; } results[low] = results[high]; while (low<high&&intToString[results[low].head] <= key) { low++; } results[high] = results[low]; } results[low] = results[0]; return low; }
voidQSort(int low, int high) { if (low<high) { int loc = partition(low, high); QSort(low, loc - 1); QSort(loc + 1, high); } }
voidQuickSort(int n) { QSort(1, n); }
intmain(void) { int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) { string name1, name2; int time;