C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <unordered_map>
using namespace std;

const int N = 2010;
struct Edge {
    string a, b;
    int c;
} e[N];
vector<string> a;                       // a用来实现离散化
int v[N];                               // v用来录每一个人的通话总时间
unordered_map<string, int> mp;          // 结合a实现离散化
int n, k;
// p实现并查集
// sz维护集合的人数
// amount维护集合总通话时间的两倍
// maxm维护当前集合电话时间最大的人的下标
int p[N], sz[N], amount[N], maxm[N];    

int find(int x) {
    if (x != p[x]) p[x] = find(p[x]);
    return p[x];
}

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> e[i].a >> e[i].b >> e[i].c;
        a.push_back(e[i].a);
        a.push_back(e[i].b);
    }
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());   // 去重
    for (int i = 0; i < (int)a.size(); i++) mp[a[i]] = i, p[i] = i, sz[i] = 1, maxm[i] = i;
    for (int i = 0; i < n; i++) {
        int ia = mp[e[i].a], ib = mp[e[i].b];
        amount[ia] += e[i].c, v[ia] += e[i].c;;
        amount[ib] += e[i].c, v[ib] += e[i].c;;
    }
    for (int i = 0; i < n; i++) {
        int ia = mp[e[i].a], ib = mp[e[i].b];
        if (find(ia) != find(ib)) {
            maxm[find(ib)] = v[maxm[find(ia)]] > v[maxm[find(ib)]] ? maxm[find(ia)] : maxm[find(ib)];
            sz[find(ib)] += sz[find(ia)];
            amount[find(ib)] += amount[find(ia)];
            p[find(ia)] = find(ib);
        }
    }
    // 注意amount[i]维护的是两倍的电话总时长
    vector<pair<string, int>> res;
    for (int i = 0; i < (int)a.size(); i++) {
        if (i == p[i] && amount[i] / 2 > k && sz[i] > 2) res.push_back({a[maxm[i]], sz[i]});
    }
    sort(res.begin(), res.end());
    cout << (int)res.size() << endl;
    for (auto& r : res) cout << r.first << ' ' << r.second << endl;


    return 0;
}