题目

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:

1	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:

1
2
3

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:

题解

思路

本质上还是求连通分量的题
所以DFS，BFS和并查集都可以做
偷懒就只放了DFS的解，也是最常用的解
题目比普通的求连通分量复杂一点，这里解释一下为什么。
首先下标都是用户名字，所以考虑用哈希表而不是数组来存储通讯记录
其次给的数据可能是这种

AAA BBB 10
BBB AAA 20
<!--hexoPostRenderEscape:<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line">+ 我们想要的结果是，AAA 到 BBB 的通讯量是30,反之也是30</span><br><span class="line"></span><br><span class="line">+ 这样就导向了一种新的数据结构，就是&#96;defaultdict(lambda: defaultdict(int))&#96;。这样就相当于，对每个人分配一个包含每个人的数组，值是分钟数。而且因为是defaultdict(int)，所以直接使用+&#x3D;号就行，非常方便</span><br><span class="line"></span><br><span class="line">+ 最后一点是不能使用传统的dfs再进行回溯，这样会导致计算团伙总人数出现重复计算。我建议的解决方法是判断人设一个visited，判断路径再设置一个visited。</span><br><span class="line"></span><br><span class="line">## 数据结构</span><br><span class="line"></span><br><span class="line">+ graph 记录所有通讯记录，是一个字典</span><br><span class="line"></span><br><span class="line">  + 键是用户姓名</span><br><span class="line">  + 值又是一个字典，表示这个用户对其他用户的通讯量。</span><br><span class="line">    + 键是打给的人的姓名</span><br><span class="line">    + 值是时间长度</span><br><span class="line">+ visited 是一个字典，表示这个用户有没有被访问过</span><br><span class="line"></span><br><span class="line">  + 键是用户姓名</span><br><span class="line">  + 值是布尔变量</span><br><span class="line">+ roads_visited 代表通讯录上的每一条路有没有被访问过。所以它和graph一样，只是最后的值并不是时间长度而是有没有被访问过。</span><br><span class="line">+ weight是一个字典，代表每个用户的权重</span><br><span class="line"></span><br><span class="line">  + 键是用户名</span><br><span class="line">  + 值是权重</span><br><span class="line">+ num，whole_weight，head，max_person_weight 表示这个团体的总人数，总权重，头头姓名和头头权重</span><br><span class="line">+ ans是一个列表，存放答案。每一项是一个列表，代表一行，也就是头头姓名和团体人数。</span><br><span class="line">+ 注意，只使用一个visited是不行的。</span><br><span class="line">+ 因为即便通过dfs完来回溯使visited为False，也可以保证每条路都访问到，但是这样计算num就出问题了。</span><br><span class="line">+ 你也可以设置两个visited都表示点有没有被访问过，其中一个回溯而另一个不回溯。算weight的时候，使用回溯的visited来判断要不要加，而算num的时候，使用不回溯的visited来确保不会重复访问。</span><br><span class="line"></span><br><span class="line">## 算法</span><br><span class="line"></span><br><span class="line">+ 读入数据，按照上述的数据结构存储（这种数据结构真的很方便很爽）。</span><br><span class="line">+ 计算每个人的权重（这里使用了列表生成式，真的很方便很爽）</span><br><span class="line">+ 对所有用户开始dfs</span><br><span class="line">  + 如果这个用户已经访问过，代表是一个已有团体，直接跳过</span><br><span class="line">  + 否则，说明是个新团体</span><br><span class="line">  + 初始化团队人数,总重量，并假定目前的头头就是他</span><br><span class="line">  + 开始dfs</span><br><span class="line">    + 如果这个人未访问过，那么团队数量加一，并且把他设为访问过。</span><br><span class="line">    + 对这个人的通讯录上的所有通讯记录</span><br><span class="line">      + 如果通讯记录没被调查过</span><br><span class="line">      + 那么总权重加上通讯时间</span><br><span class="line">      + 标记路线被访问过</span><br><span class="line">      + 如过通讯对象是头头，则更新头头</span><br><span class="line">      + dfs通讯对象</span><br><span class="line">  + 完了以后判断这个团体权重赔不配得上黑社会，并相应添加到答案中</span><br><span class="line">+ 排序并输出。</span><br><span class="line"></span><br><span class="line">##　代码</span><br><span class="line"></span><br><span class="line">由于使用Python能AC，因此只放了Python的代码。</span><br><span class="line"></span><br><span class="line">&#96;&#96;&#96;Python</span><br><span class="line">from collections import defaultdict</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">def dfs(name):</span><br><span class="line">    global head, whole_weight, graph, visited, max_person_weight, num</span><br><span class="line">    if not visited[name]:</span><br><span class="line">        num +&#x3D; 1</span><br><span class="line">    	visited[name] &#x3D; True</span><br><span class="line">    for person, time in graph[name].items():</span><br><span class="line">        if not roads_visited[name][person]:</span><br><span class="line">            whole_weight +&#x3D; time</span><br><span class="line">            roads_visited[name][person] &#x3D; True</span><br><span class="line">            roads_visited[person][name] &#x3D; True</span><br><span class="line">            if weight[person] &gt; max_person_weight:</span><br><span class="line">                max_person_weight &#x3D; weight[person]</span><br><span class="line">                head &#x3D; person</span><br><span class="line">            dfs(person)</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">num_calls, threshold &#x3D; list(map(int, input().split()))</span><br><span class="line">graph &#x3D; defaultdict(lambda: defaultdict(int))</span><br><span class="line">visited &#x3D; defaultdict(bool)</span><br><span class="line">roads_visited &#x3D; defaultdict(lambda: defaultdict(bool))</span><br><span class="line">ans &#x3D; []</span><br><span class="line">for _ in range(num_calls):</span><br><span class="line">    info &#x3D; input().split()</span><br><span class="line">    graph[info[0]][info[1]] +&#x3D; int(info[2])</span><br><span class="line">    graph[info[1]][info[0]] +&#x3D; int(info[2])</span><br><span class="line">weight &#x3D; &#123;i: sum(graph[i].values()) for i in graph.keys()&#125;</span><br><span class="line"></span><br><span class="line">for i in graph.keys():</span><br><span class="line">    if not visited[i]:</span><br><span class="line">        num &#x3D; 0</span><br><span class="line">        whole_weight &#x3D; 0</span><br><span class="line">        head &#x3D; i</span><br><span class="line">        max_person_weight &#x3D; weight[i]</span><br><span class="line">        dfs(i)</span><br><span class="line">        if whole_weight &gt;&#x3D; threshold and num &gt; 2:</span><br><span class="line">            ans.append([head, num])</span><br><span class="line"></span><br><span class="line">print(len(ans))</span><br><span class="line">ans.sort(key&#x3D;lambda x: x[0])</span><br><span class="line">for i, j in ans:</span><br><span class="line">    print(i, j)</span><br><span class="line"></span><br></pre></td></tr></table></figure>:hexoPostRenderEscape-->