题目描述

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

问题分析

该题输入n个通话记录和一个阈值k，一个通话记录是由通话双方两个节点组成，定义通话双方的通话时长为每一次的通话之和，比如A->B 10，B->A 20，A和B的通话时长=10+20=30，所以n个通话记录组成了一个通话图，由上述定义可知，该图是无向图，题目要求从该图中找出所有的符合条件的连通图里的节点个数和head节点，要求该连通图的节点数大于2，并且该连通图的边权和大于阈值k，head节点是一个连通图中相邻边权值最大的节点，比如A---B 30, A---C 40，那么A-B-C形成了一个Gang，并且head的点权=30+40=70，B的点权=30，C的点权=40，因此A节点是该Gang里的head。

根据以上分析，我们要解决的问题：

• 图的定义：由于通话记录少于1000条，因此节点不超过2000个，定义图的边权为通话双方通话记录之和。
• 点权的定义：为了找到一个Gang里的head，定义点权为该节点邻接所有节点的边权之和。
• 姓名和编号的映射：由于输出的是姓名字符串，我们需要将姓名映射到节点编号，使用map<string,int>,map<int,string>。
• 求解符合条件的连通图 ：可以使用BFS或者DFS遍历，注意在每次遍历时，记录边权和，更新head节点。此外，由于在计算边权和的时候，出现一个节点邻接一个已访问的环，会重复计算边权，这里使用删除策略，在对边权累加结束后，删除该边，再进行DFS或者BFS遍历。

参考代码

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

using namespace std;

const int maxn = 2010;
const int INF = 100000000;

map<int,string> intToString; //编号和姓名对应
map<string,int> stringToInt; //姓名和编号对应
map<string,int> Gang; //head->人数

//使用邻接矩阵存储
//weight:是每一个点的点权，为其邻接点的边权之和
int graph[maxn][maxn] = {0},weight[maxn] = {0};
int n,k,numPerson = 0;
bool vis[maxn] = {false};

//DFS访问连通块
//nowVisit是现在访问节点，head是当前的头目，numMember是当前的人数，totalValue是当前的总边权
void DFS(int nowVisit,int& head,int& numMember,int& totalValue)
{
    //人数+1
    numMember ++;
    //设置访问标志
    vis[nowVisit] = true;
    //更新头目
    if(weight[nowVisit] > weight[head])
    {
        head = nowVisit;
    }
    //访问当前节点的所有的邻接点
    for(int i=0;i<numPerson;i++) //枚举所有人
    {
        //如果当前节点， 能够到达i节点
        if(graph[nowVisit][i]>0)
        {
            //累加边权
            totalValue += graph[nowVisit][i];
            //为了防止走回头路，边权的重复累加，删除该条边
            graph[nowVisit][i] = graph[i][nowVisit] = 0;
            //如果节点i未被访问， 则DFS访问其临界点
            if(vis[i] == false)
            {
                DFS(i,head,numMember,totalValue);
            }
        }
    }
}

//遍历整个图，获取每个连通块的信息
void DFSTravel()
{
    for(int i=0;i<numPerson;i++)
    {
        if(vis[i] == false)
        {
            //初始化头目，连通图成员数，总边权
            int head = i,numMember = 0,totalValue = 0;
            DFS(i,head,numMember,totalValue);
            //判断是否满足题目要求，成员数大于2，并且总边权要大于k
            if(numMember>2 && totalValue >k)
            {
                //记录Gang信息
                Gang[intToString[head]] = numMember;
            }
        }
    }
}

//定义change函数，表示int和str的对应关系
int change(string str)
{
    if(stringToInt.find(str) != stringToInt.end())
    {
        //如果该姓名出现过，那么返回该节点编号
        return stringToInt[str];
    }
    else
    {
        //若没出现过，那么新增该姓名
        stringToInt[str] = numPerson;
        intToString[numPerson] = str;
        //返回编号，这里使用给变量numPerson来控制节点的增加，需要学习
        return numPerson++;

    }
}

int main()
{
    int w;
    string str1,str2;
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        cin>>str1>>str2>>w;
        //找到或者赋给str1和str2的编号
         int id1= change(str1);
         int id2 = change(str2);
         //图的边权赋值,由于是无向图，双向增加
         graph[id1][id2] += w;
         graph[id2][id1] +=w;
         //点权赋值
         weight[id1] += w;
         weight[id2] += w;
    }
    //遍历所有连通块
    DFSTravel();
    //打印Gang的个数
    cout<<Gang.size()<<endl;
    //打印Gang
    map<string,int>::iterator it;
    for(it = Gang.begin();it != Gang.end();it++)
        cout<<it->first<<" "<<it->second<<endl;
    return 0;
}