题目：https://pintia.cn/problem-sets/994805342720868352/problems/994805456881434624

明天再写一遍。。完了再写心得感受

代码

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<string>
  4. #include<map>
  5. using namespace std;
  6. const int maxn = 2100;
  7. const int INF = 1000000000;
  8. //初始化参数
  9. map<int, string> intToString;// 终于明白为什么要使用int映射了，因为数组的索引用string不太方便
  10. map<string, int> stringToInt;
  11. map<string, int> Gang;
  12. int G[maxn][maxn] = {0}, weight[maxn] = {0};
  13. int n, k, numPerson = 0;
  14. bool vis[maxn] = {false};
  16. void DFS(int nowVisit, int& head, int& numMember, int& totalValue){
  17.     numMember++;//人数加一
  18.     vis[nowVisit] = true;//标记已经访问
  19.     if(weight[nowVisit] > weight[head]) head = nowVisit;//更新头领
  20.     for(int i = 0; i < numPerson; i++){
  21.         if(G[nowVisit][i] > 0){
  22.             totalValue += G[nowVisit][i];
  23.             G[nowVisit][i] = G[i][nowVisit] = 0;//删除这条边
  24.             if(vis[i] == false) DFS(i, head, numMember, totalValue);
  25.         }
  26.     }
  27. }
  29. void DFSTrave(){
  30.     for(int i = 0; i < numPerson; i++){
  31.         if(vis[i] == false){//如果还没被访问
  32.             int head = i, numMember = 0, totalValue = 0;//置初始值
  33.             DFS(i, head, numMember, totalValue);
  34.             if(numMember > 2 && totalValue > k){//如果成员大于两个，且权值大于k，那么就是头目
  35.                 Gang[intToString[head]] = numMember;
  36.             }
  37.         }
  38.     }
  39. }
  41. int change(string str){
  42.     if(stringToInt.find(str) != stringToInt.end()){
  43.         return stringToInt[str];//如果找到那么就返回数字，否则
  44.     } else {
  45.         stringToInt[str] = numPerson;//新建一对映射关系
  46.         intToString[numPerson] = str;
  47.         return numPerson++;
  48.     }
  49. }
  51. int main(){            
  52.     int w;
  53.     string str1, str2;
  54.     cin>> n >> k;
  55.     for(int i = 0; i < n; i++){
  56.         cin >> str1 >> str2 >> w;
  57.         int id1 = change(str1);
  58.         int id2 = change(str2);
  59.         weight[id1] += w;
  60.         weight[id2] += w;
  61.         G[id1][id2] += w;//联系是相互的，因此是累加的
  62.         G[id2][id1] += w;
  63.     }
  64.     DFSTrave();
  65.     cout << Gang.size() << endl;
  66.     for(auto it = Gang.begin(); it != Gang.end(); it++){
  67.         cout << it->first <<" " <<it->second << endl;
  68.     }
  69.     return 0;
  70. }