题意

警察通过检查一群人之间的通话记录来找到一个犯罪团伙的头目，如果A和B（两顶点）之间有通话记录，那么我们就说他们之间是有关系（无向边）的（这样就把所有的人分成了几个连通块）。
一个边的权重就是两个人之间通话时间的总和，点权则是一个人参与的总通话时间。
一个犯罪团伙是指人数超过两个人的一个圈子，圈内所有人进行的通话时间（所有边权之和）超过给定的K，团伙的头目就是进行通话时间最多（点权最大）的那个人。
现在给定一系列的通话记录（由两个名字和一个数字组成），要求找出所有的犯罪团伙，输出他们的头目姓名和成员数目。

思路

我们要输出的是头目姓名和成员数目，用一个map来保存每一组犯罪团伙的头目姓名和成员数目，这样可以依靠map按键值自动排序的特点简化输出过程；
题目给的是一堆边权，我们要依靠边权总和来计算一个连通块的总边权，也就是说进行dfs遍历一个连通块的时候，需要访问边权，那么边权需要保存下来；
当一个连通块的总边权大于K的时候，这个连通块就是一个犯罪团伙，我们要计算并比较其中每个人的点权，找出头目并保存姓名，当然，还要保存犯罪团伙的人数。

代码问题

1.姓名和编号的对应关系：一是建立map<string,int>和map<int,string>（两个map很好用），二是使用字符串hash。
2.图建立时需要被保存的数据有：顶点编号，他们之间的边权（可以用0表示不存在边）。然后点权可以通过dfs的时候累计，但不如在读入的时候用一个数组单独保存点权。
3.之后进行连通块的dfs遍历，获取每一个连通块的总边权，然后判断是否保存这个连通块（保存头目的string，因为要依靠map结构的自动排序）。
4.图的遍历由dfs组合。

注意点

1.通话记录最多有1000条，那么不同的人最多会有2000个。
2.用map<string,int>存犯罪团伙，因为map会根据键值自动排序。
3.图中环的问题：存在环ABC，当访问A的时候，BC会被同级访问，然后累加两次边权，

#include <iostream>
#include <map>
#include <string>

using namespace std;

const int MAXV = 2000;
const int INF = 10000000;

map<string,int> stringToInt; // 姓名->编号
map<int,string> intToString; // 编号->姓名

map<string,int> Gang; // 保存的连通块

int G[MAXV][MAXV] = { {0} }; // 邻接矩阵
int weight[MAXV] = {0}; // 点权
int n,k,totalPerson = 0;
bool vis[MAXV] = {0};


// dfs函数访问单个连通块，curVis当前访问的编号
// head表示头目，member成员数目，sumEdgeWeight总边权
// 这三个变量在dfs的过程中需要更新，因为dfs结束之后需要这三个数据

void dfs( int curVis, int &head, int &sumMember, int &sumEdgeWeight )
{
    ++sumMember; // 更新连通块成员数
    vis[curVis] = true;
    if( weight[head] < weight[curVis] ) // 更新头目
        head = curVis;
    // 接下来计算累加边权，并把访问过的边权设为0
    // 这样不会破坏图，因为被删掉的边的端点都已经访问，不会在从他们出发，也不会再有别的顶点到达他们
    // 这里可以看出，这个算法把起始点看做重心，然后无条件累加边权，删掉这个边
    // 画图可以发现，一次dfs就是累加一个顶点的所有边权然后“剪掉”这个点和与它相连的这些边
    // 这样做的理由是：我们要计算的边权已经累加，头目和成员数都已经更新，这个点和这个边已经失去价值
    for(int i = 0;i<totalPerson;++i)
    {
        if( G[curVis][i] > 0 ) // 判断有没有边
        {
            sumEdgeWeight += G[curVis][i];
            G[curVis][i] = G[i][curVis] = 0;
            if(vis[i]==false)
                dfs(i,head,sumMember,sumEdgeWeight);
        }
    }
}

void dfsGraph()
{
    for(int i = 0;i<totalPerson;++i)
    {
        if(vis[i]==false)
        {
            int head = i;
            int sumMember = 0; // 是1还是0看编程习惯
            int sumEdgeWeight = 0;
            dfs(i,head,sumMember,sumEdgeWeight);
            if( sumEdgeWeight>k && sumMember>2 )
                Gang[ intToString[head] ] = sumMember; // 注意，保存的是head，不是i
        }
    }
}

int change(string str)
{
    if( stringToInt.find(str)==stringToInt.end() )
    {
        stringToInt[str] = totalPerson;
        intToString[totalPerson] = str;
        return totalPerson++;
    }
    else
    {
        return stringToInt[str];
    }
}
int main(void)
{
    cin >> n >> k;
    int w;
    string str1,str2;
    while(n--)
    {
        cin >> str1 >> str2 >> w;
        int id1 = change(str1);
        int id2 = change(str2);
        weight[id1] += w;
        weight[id2] += w;
        G[id1][id2] += w;
        G[id2][id1] += w;
    }
    dfsGraph();
    cout << Gang.size() << endl;
    map<string,int>::iterator it;
    for(it = Gang.begin();it!=Gang.end();++it)
        cout << it->first << " " << it->second << endl;

    return 0;
}

总结

由题目建立邻接矩阵图，由题目要求：

• 在这个题目的背景下，图本身已经是由连通块组成的图，不同连通块之间没有任何关系，在一次dfs之后一个连通块里的所有顶点都被标记为visited，而dfs一个连通块的时候是依靠边来递归的，所以dfs自然而然就只是遍历一个连通块。这样在进行编程的时候就只需要把目光聚焦在一个连通块的处理上，而dfsGraph就是用来合并执行这些单次遍历的。

• dfs单个连通块：从当前处理的顶点，携带上一级传下的sumMember（累计深度）和sumEdgeWeight（累计-总边权），开始处理与这个顶点相连的边，刷新数据，并向这些边的另一端传递数据，进入递归。边均被剪掉，最后的端点无路可走，递归结束。获取到连通块中点权最大顶点编号head，连通块中顶点的数量sumMember，总边权sumEdgeWeight

• 当前处理的顶点是基本参数，sumMember和sumEdgeWeight与dfs模板中的depth对应。