原题干：
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
题目大意：根据通话记录，找出犯罪团伙。第一行给定正整数N和K，接着给出N行数据，数据格式为"主叫人 被叫人 时长"
假设A给B打过电话，B给C也打过电话，那么ABC就是一个团伙。如果这个团伙的累计通话时长超过阈值K，则称他们是犯罪团伙。团伙中打电话时间最长的人称为犯罪头目。
输出犯罪团伙的个数，并按照字典序输出头目，以及头目对应犯罪团伙的人数
这道题可以使用图算法的思想来完成。给出的每一行数据是一条边，每一个人是一个点。该人的通话时长就是点权，该人与某个人的通话时长就是他与这个人的边权。
这里给出的每一个"点"都是字符串，不便于我们使用邻接矩阵存储。使用hash的思想，将string字符串与int数字在map容器中建立起映射关系，可以大大的减少代码的复杂程度；
这里要特别注意几点：
1、这道题要求的是累计边权，累计完边权后务必要删除这条边，否则按照DFS的思想会走回头路而造成重复
2、可以使用map容器存储犯罪团伙，map容器会给你自动排序成字典序。使用vector容器需要加上sort排序，否则第二个和第五个测试点通不过（别问我怎么知道的。两个测试点通不过去，我找了一上午的错）
3、题目中说了，给出的N和K小于等于1000，但是数组千万不能开1000多，而要开2000多。否则第三个测试点会提示段错误。这是因为通话是双方的。
4、如果你不知道如何判断团伙是不是犯罪团伙，考试又没时间思考，你可以直接把所有连通块（团伙）输出，至少第四个测试点的3分能到手......
好了不废话了，上代码：
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <string>
using namespace std;
//全局变量区
const int maxn = 2010, inf = 0x7fffffff;
//邻接矩阵、点权
int G[maxn][maxn], V[maxn] = {0};
//哈希表
map<string, int> str_id;
map<int, string> id_str;
int max_id = 1;
//存放头目的容器
typedef struct {
string name;
int sum;
} fucker;
vector<fucker> Gang;
//遍历时判断是否访问过的bool数组
bool visited[maxn] = {false};
//总时长、最大时长、头目的id，总人数
int total_time, max_time, Gang_id, total_sum;
//哈希映射
int GetHash(string str){
if(str_id[str]) return str_id[str];
else{
str_id[str] = max_id;
id_str[max_id] = str;
return max_id++;
}
}
//深度优先搜索（连通集）
void DFS(int s){
total_sum++;
total_time += V[s];
if(V[s] > max_time) max_time = V[s], Gang_id = s;
visited[s] = true;
for(int i = 1; i < max_id; i++)
if(!visited[i] && G[s][i] != inf)
DFS(i);
}
//深度优先搜索（图）
void DFSG(int k){
for(int i = 1; i < max_id; i++)
if(!visited[i]){
//清空上次的记录
total_time = max_time = total_sum = 0;
DFS(i);
//因为点权记录的是无向的，这里要除以2
if(total_time / 2 > k && total_sum > 2)
Gang.push_back({id_str[Gang_id], total_sum});
}
}
bool cmp(fucker a, fucker b){return a.name < b.name;}
int main(){
fill(G[0], G[0] + maxn * maxn, inf);
int cnt, k;
cin >> cnt >>k;
for(int i = 0; i < cnt; i++){
string a, b;
int time;
cin >> a >> b >> time;
int id_a = GetHash(a), id_b = GetHash(b);
//设置边权和点权
G[id_a][id_b] = time;
V[id_a] += time;
V[id_b] += time;
}
//深度优先搜索入口
DFSG(k);
//字母序排序
sort(Gang.begin(), Gang.end(), cmp);
cout << Gang.size() << endl;
for(auto it : Gang)
cout << it.name << ' ' << it.sum << endl;
return 0;
}