题解 | Head of a Gang(BFS)

#include <iostream>
#include <cstdio>
#include <stdlib.h>
#include <map>
#include <set>
#include <cstring>
#include <vector>
#include <list>
#include <algorithm>
#define x first
#define y second
using namespace std;

const int N=1010;
typedef pair<string,int> PSI;

map<string,vector<PSI>> G;//bian

map<string,bool> st;
int n,k;
int ans;
vector<pair<string,int>> toumu;
map<string,int> ca;//meigezimu
set<string> q;

void BFS(string s){
    long long all=0;
    list<string> Q;
    list<string> Q1;
    Q.push_back(s);
    Q1.push_back(s);
    st[s]=true;

    while(Q.size()){
        string t=Q.front();
        Q.pop_front();

        for(PSI i:G[t]){
            all+=i.y;
            ca[i.x]+=i.y;
            ca[t]+=i.y;
            if(st[i.x])continue;
            st[i.x]=true;
            Q.push_back(i.x);
            Q1.push_back(i.x);
        }
    }

    all/=2;
    for(string i:Q1)ca[i]/=2;

    if(Q1.size()>2&&all>k){
        ans++;
        string s1=Q1.front();
        for(string i:Q1){
            if(ca[i]>ca[s1]){
                s1=i;
            }
        }
        toumu.push_back({s1,Q1.size()});
    }
}

bool cmp(PSI a,PSI b){
    if(a.x<b.x)return true;
    return false;
}

int main(){
    while(cin>>n>>k){
        st.clear();
        toumu.clear();
        q.clear();
        ca.clear();
        G.clear();
        ans=0;
        
        string s1,s2;
        int t;
        for(int i=0;i<n;i++){
            cin>>s1>>s2>>t;
            G[s1].push_back({s2,t});
            G[s2].push_back({s1,t});
            st[s1]=false;
            st[s2]=false;
            q.insert(s1);
            q.insert(s2);
        }

        for(string s:q){
            if(!st[s])st[s]=true,BFS(s);
        }

        cout<<ans<<endl;
        sort(toumu.begin(),toumu.end(),cmp);
        for(PSI i:toumu){
            cout<<i.x<<' '<<i.y<<endl;
        }
    }

    return 0;
}