1034 Head of a Gang (30分)

/*
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:
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:
0
 */
#include<iostream>
#include<map>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>

using namespace std;
const int maxN = 2010;
int G[maxN][maxN], weight[maxN];
bool vis[maxN];
map<string, int> stringToInt;
map<int, string> intToString;
map<string, int> ans;
int idNumber = 1, N, K, w;

void dfs(int u, int &head, int &numMember, int &totalWeight) {
    vis[u] = true;
    numMember++;
    if (weight[u] > weight[head])
        head = u;
    for (int v = 1; v < idNumber; v++) {
        if (G[u][v] > 0) {
            totalWeight += G[u][v];
            G[u][v] = G[v][u] = 0;
            if (!vis[v])
                dfs(v, head, numMember, totalWeight);
        }
    }
}

void dfsTrave() {
    for (int i = 1; i < idNumber; i++) {
        if (!vis[i]) {//如果i站点未访问
            int head = i, numMember = 0, totalWeight = 0;
            dfs(i, head, numMember, totalWeight);
            if (numMember > 2 && totalWeight > K)
                ans[intToString[head]] = numMember;
        }
    }
}

int stoifunc(string s) {
    if (stringToInt[s] == 0) {
        stringToInt[s] = idNumber;
        intToString[idNumber] = s;
        return idNumber++;
    } else
        return stringToInt[s];
}

int main() {
    cin >> N >> K;
    string S1, S2;
    for (int i = 0; i < N; i++) {
        cin >> S1 >> S2 >> w;
        int id1 = stoifunc(S1);
        int id2 = stoifunc(S2);
        // cout << id1 << id2;
        weight[id1] += w;
        weight[id2] += w;
        G[id1][id2] += w;
        G[id2][id1] += w;
    }
    dfsTrave();
    cout << ans.size() << endl;
    for (auto &an : ans)   //for (auto it = ans.begin(); it != ans.end(); it++)
        cout << an.first << " " << an.second << endl;
    return 0;
}