题解 | Head of a Gang

详细题解在https://mp.weixin.qq.com/s/PK4gWeV4rvuixrPZ_hFQ0w

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <cstring> // 为了使用 memset

using namespace std;

const int MAXN = 2010;

// 全局变量
map<string, int> nameToId;
map<int, string> idToName;
int graph[MAXN][MAXN];
int personWeight[MAXN];
bool visited[MAXN];
int numPerson = 0;

// 初始化函数：每处理一组新数据前调用
void init() {
    numPerson = 0;
    nameToId.clear();
    idToName.clear();
    memset(graph, 0, sizeof(graph));
    memset(personWeight, 0, sizeof(personWeight));
    memset(visited, false, sizeof(visited));
}

int getID(string name) {
    if (nameToId.find(name) != nameToId.end()) {
        return nameToId[name];
    }
    nameToId[name] = numPerson;
    idToName[numPerson] = name;
    return numPerson++;
}

void dfs(int u, int &head, int &numMember, int &totalWeight) {
    visited[u] = true;
    numMember++;
    
    if (personWeight[u] > personWeight[head]) {
        head = u;
    }
    
    for (int v = 0; v < numPerson; ++v) {
        if (graph[u][v] > 0) {
            totalWeight += graph[u][v];
            graph[u][v] = graph[v][u] = 0; // 消除边防止重复计算
            
            if (!visited[v]) {
                dfs(v, head, numMember, totalWeight);
            }
        }
    }
}

int main() {
    int n, k;
    // 修改点：使用 while 循环持续读取输入，直到没有内容
    while (cin >> n >> k) {
        // 修改点：每次循环开始前清空上次的数据
        init();

        for (int i = 0; i < n; ++i) {
            string name1, name2;
            int time;
            cin >> name1 >> name2 >> time;
            int id1 = getID(name1);
            int id2 = getID(name2);
            
            graph[id1][id2] += time;
            graph[id2][id1] += time;
            personWeight[id1] += time;
            personWeight[id2] += time;
        }

        map<string, int> ans; 
        for (int i = 0; i < numPerson; ++i) {
            if (!visited[i]) {
                int head = i;
                int numMember = 0;
                int totalWeight = 0;
                
                dfs(i, head, numMember, totalWeight);
                
                if (numMember > 2 && totalWeight > k) {
                    ans[idToName[head]] = numMember;
                }
            }
        }

        cout << ans.size() << endl;
        for (auto it = ans.begin(); it != ans.end(); ++it) {
            cout << it->first << " " << it->second << endl;
        }
    }
    return 0;
}