1034. Head of a Gang (30)

清疚 2022-05-31 11:46 98阅读 0赞

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 threshold, 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:**

--------------------

题目大意：

警方锁定犯罪团伙头目的一种方法是检查人们的电话。如果A和B之间有通话，我们就说A和B是相关的。关系的重要程度视两人之间的所有通话时间长度而定。一个团伙是指超过两个人的群体，他们之间关系总权重大于给定的阈值。在每个团伙中，总重量最大的是头目。现在给你一份电话，你的任务是找出团伙的头目。  
输入规范：  
每个输入文件包含一个测试用例。对于每个测试案例，第一行包含两个正整数N和K（小于或等于1000），分别代表电话号码和权重阈值。然后是N行，每一行格式如下：  
Name1 Name2 Time  
在电话的两端，Name1和Name2是人员的名称，时间是通话长度。名称是在A-Z中选择的三个大写字母组成的字符串。时间长度是一个正整数，不超过1000分钟。  
输出规范：  
对于每个测试用例，在第一行打印团伙的总数。然后对于每一个团伙，打印出他的头目名称和成员总数。可以保证每个团伙的头目是独一无二的。输出必须按头目名称的字母顺序进行排序。

代码：

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<string>
    #include<vector>
    #include<map>
    using namespace std;
    map<string,vector<string> > userlist;
    map<string,int> userweight;
    map<string,int> visited;
    map<string,int> result;
    int cnt,total;
    string head;
    void DFS(string h)
    {
        cnt++;
        total+=userweight[h];
        visited[h]=1;
        if(userweight[head]<userweight[h])
            head=h;
        vector<string>::iterator it;
        for(it=userlist[h].begin();it!=userlist[h].end();it++)
        {
            if(visited[*it]==0)
            {
                DFS(*it);
            }
        }
    
    }
    int main()
    {
        int i,j,n,m,k,t;
        string a,b;
        map<string,int>::iterator it;
        scanf("%d %d",&n,&k);
        for(i=0;i<n;i++)
        {
            cin>>a>>b>>m;
            userlist[a].push_back(b);
            userlist[b].push_back(a);
            userweight[a]+=m;
            userweight[b]+=m;
            visited[a]=0;
            visited[b]=0;
        }
        for(it=visited.begin();it!=visited.end();it++)
        {
            if(it->second==0)
            {
                head=it->first;
                total=0;
                cnt=0;
                DFS(head);
                if(cnt>2&&total/2>k)
                   result[head]=cnt;
            }
        }
        printf("%d\n",result.size());
        for(it=result.begin();it!=result.end();it++)
        {
            cout<<it->first<<" "<<it->second<<endl;
        }
        return 0;
    }

参考：[点击打开链接][Link 1]

[Link 1]: http://blog.csdn.net/iaccepted/article/details/20161235