PTA A_1034 Head of a Gang

798236606

传送门：https://pintia.cn/problem-sets/9 ... /994805456881434624

解：
图的DFS +求边和

1. #include <iostream>
   
2. #include <string>
   
3. #include <map>
   
4. 
   
5. using namespace std;
   
6. 
   
7. const int maxn = 2010;
   
8. 
   
9. int G[maxn][maxn], k, num, m, total, max_id;
   
10. int weight[maxn];
    
11. bool vis[maxn];
    
12. map<string, int> s2i, gang;
    
13. map<int, string> i2s;
    
14. 
    
15. int add_name(string s)
    
16. {
    
17.     int id = s2i[s];
    
18. 
    
19.     if (!id)
    
20.     {
    
21.         s2i[s] = ++num;
    
22.         i2s[num] = s;
    
23.         return num;
    
24.     }
    
25. 
    
26.     return id;
    
27. }
    
28. 
    
29. void DFS(int id)
    
30. {
    
31.     if (!vis[id]) m++;//计算同伙人数
    
32.     if (weight[id] > weight[max_id]) max_id = id;//查找头目
    
33. 
    
34.     vis[id] = true;
    
35.     // cout << i2s[id] << weight[id] << endl;
    
36.     for (int i = 1; i <= num; i++)
    
37.         if (G[id][i])
    
38.         {
    
39.             // cout << i2s[id] << "--" << i2s[i] << "=" << G[id][i] << endl;
    
40.             total += G[id][i];//一个团伙的总通话时间
    
41.             G[id][i] = G[i][id] = 0;//切断已经计算过的边
    
42.             DFS(i);
    
43.         }
    
44. }
    
45. 
    
46. int DFS_traverse(void)
    
47. {
    
48.     int n = 0;
    
49. 
    
50.     for (int i = 1; i <= num; i++)
    
51.     {
    
52.         if (!vis[i])
    
53.         {
    
54.             m = total = 0;
    
55.             max_id = i;
    
56. 
    
57.             DFS(i);
    
58. 
    
59.             if (m > 2 && total > k && ++n) gang[i2s[max_id]] = m;
    
60.             // cout << "max_id = " << i2s[max_id] << "total = " << total << "n = " << n << endl;
    
61.         }
    
62.     }
    
63. 
    
64.     return n;
    
65. }
    
66. 
    
67. int main() {
    
68.     // freopen("input.txt", "r", stdin);
    
69.     int n;
    
70. 
    
71.     cin >> n >> k;
    
72. 
    
73.     while (n--)
    
74.     {
    
75.         string s1, s2;
    
76.         int w;
    
77. 
    
78.         cin >> s1 >> s2 >> w;
    
79.         
    
80.         int n1 = add_name(s1);
    
81.         int n2 = add_name(s2);
    
82.         weight[n1] += w;
    
83.         weight[n2] += w;
    
84.         G[n1][n2] += w;
    
85.         G[n2][n1] += w;
    
86.     }
    
87. 
    
88.     printf("%d\n", DFS_traverse());
    
89. 
    
90.     for (map<string, int>::iterator it = gang.begin(); it != gang.end(); ++it)
    
91.         cout << it->first << " " << it->second << endl;
    
92. 
    
93.     return 0;
    
94. }

复制代码