【一只蒟蒻的刷题历程】【PAT】 A1034 团伙头（dfs）-白红宇的个人博客

发布日期：2021-05-04 19:23:13 浏览次数：43 分类：技术文章

本文共 3393 字，大约阅读时间需要 11 分钟。

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 59AAA BBB 10BBB AAA 20AAA CCC 40DDD EEE 5EEE DDD 70FFF GGG 30GGG HHH 20HHH FFF 10

Sample Output 1:

2AAA 3GGG 3

Sample Input 2:

8 70AAA BBB 10BBB AAA 20AAA CCC 40DDD EEE 5EEE DDD 70FFF GGG 30GGG HHH 20HHH FFF 10

Sample Output 2:

题意：

警察找到团伙头的一种方法是检查人们的电话。如果A和B之间有电话，我们说A和B是相关的。关系的权重定义为两个人之间进行的所有电话呼叫的总时间长度。 “帮派”是由两个以上彼此相关的人员组成的集群，总关系权重大于给定的阈值K。在每个帮派中，总权重最大的是头。现在给出电话列表，您应该找到帮派和团长。

输入规格：

每个输入文件包含一个测试用例。对于每种情况，第一行都包含两个正数N和K（均小于或等于1000），电话数量和权重阈值。然后N行，每行采用以下格式：

名称1 名称2 时间

其中Name1和Name2是通话两端的人员名称，Time是通话时间。名称是从A-Z中选择的三个大写字母的字符串。时间长度是一个不超过1000分钟的正整数。

输出规格：

对于每个测试用例，首先在一行中打印帮派总数。然后，对于每个团伙，在一行中打印头的名称和成员总数。可以确保每个帮派头都是唯一的。必须根据标题名称的字母顺序对输出进行排序。

样本输入1：

8 59AAA BBB 10BBB AAA 20AAA CCC 40DDD EEE 5EEE DDD 70FFF GGG 30GGG HHH 20HHH FFF 10

样本输出1：

2AAA 3GGG 3

样本输入2：

8 70AAA BBB 10BBB AAA 20AAA CCC 40DDD EEE 5EEE DDD 70FFF GGG 30GGG HHH 20HHH FFF 10

样本输出2：

代码：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            using namespace std; const int maxn=2050;int n,k,T[maxn]; //通话记录，阈值int g[maxn][maxn]={ 0}; //存图 bool vis[maxn]={ false}; //标记是否被访问 map
             
               m1; //名字-编号map
              
                m2; //编号-名字 map
               
                 ans; //头目-团伙数量int num=0; //总人数int zhuan(string s){ if(m1.find(s) != m1.end()) //这个名称已经被换成编号了 return m1[s]; //返回编号 else { m1[s] = num; //s对应编号num m2[num] = s; //编号num对应s return num++; //给编号 } } void dfs(int u,int &head,int &member,int &numk) //遍历连通块{ vis[u]=1; //标记访问过 member++; //该团伙成员数量++ if(T[u] > T[head]) //找最大电话时间的是头头 head = u; for(int i=0;i
                
                 0) //走得通（有电话交流） { numk += g[u][i]; //总边权增加 g[u][i] = g[i][u]=0; //让这条边走不通，防止后面再走 if(vis[i]==false) //没访问过，就去访问 dfs(i,head,member,numk); } }}int main() { int n,k; cin>>n>>k; string a,b; int t; while(n--) { cin>>a>>b>>t; int x=zhuan(a),y=zhuan(b); g[x][y] += t; //无向图 g[y][x] += t; T[x] += t; //累加个人时间 T[y] += t; } for(int i=0;i
                 
                  k && member>2) //总边权大于阈值k，成员大于2个为团伙 ans[m2[head]] = member; //更新 } } cout<
                  
                   <
                   
                    first<<" "<
                    
                     second<

上一篇：【一只蒟蒻的刷题历程】【PAT】A1015 德才论

下一篇：【一只蒟蒻的刷题历程】【PAT】 A1031 Hello World for U

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！