首先并查集模版要先写上，hash肯定要用
设置times数组记录每个人的通话总时长，并且把所有人合并集合
设置一个长度为N结构体，集合父亲对应位置存储此集合的一些信息，比如集合中所有人的通话总时长，通话最长的人，成员数
遍历所有的人，把每个集合的信息存入结构体对应项
为了方便下次找到所有集合的父亲，可以开一个集合（set）存储遍历出现的所有父亲
遍历所有父亲，筛选所有符合条件的集合，保存每个集合中最大的人和成员数；
输出
#include<iostream> #include<algorithm> #include<vector> #include<map> #include<string> #include<set> using namespace std; const int N = 26*26*26 + 1; int fa[N]; int times[N] = {0}; set<int> all_fa; struct headset{ int name; int sumt; int maxt; int memb; }allset[N]; struct heads{ int name; int memb; }; vector<heads> gangs; bool comp(heads a, heads b){ if(a.name < b.name) return true; else return false; } int name2n(string s){ return ( s[0] - 'A' ) * 26 * 26 + ( s[1] - 'A' ) * 26 + ( s[2] - 'A' ); } void initfa(){ for(int i = 0; i < N; i++){ fa[i] = i; } } int findfather(int x){ if(fa[x] == x) return x; else{ int F = findfather(fa[x]); fa[x] = F; return F; } } void Union(int a, int b){ int faA = findfather(a); int faB = findfather(b); if(faA != faB){ fa[faA] = faB; } } int main(){ initfa(); int n, k; cin>>n>>k; for(int i = 0; i < n; i++){ string s1, s2; int tempt; cin>>s1>>s2>>tempt; int a1 = name2n(s1); int a2 = name2n(s2); times[a1] += tempt; times[a2] += tempt; Union(a1,a2); // all_names.insert(a1); // all_names.insert(a2); } // for(set<int>::iterator it = all_names.begin(); it != all_names.end(); it++){ // int tempfa = findfather(*it); // sumtimes[tempfa] += times[*it]; // } for(int i = 0; i <= N; i++){ if(times[i] != 0){ int tempfa = findfather(i); // cout<<tempfa<<endl; all_fa.insert(tempfa); allset[tempfa].memb++; allset[tempfa].sumt += times[i]; if(allset[tempfa].maxt < times[i]){ allset[tempfa].maxt = times[i]; allset[tempfa].name = i; } } } for(set<int>::iterator it = all_fa.begin(); it != all_fa.end(); it++){ // cout<<*it<<" "<<allset[*it].sumt<<" "<<allset[*it].memb<<" "<<allset[*it].name<<" "<<allset[*it].maxt<<endl; if(allset[*it].sumt > 2 * k && allset[*it].memb > 2){ heads a; a.name = allset[*it].name; a.memb = allset[*it].memb; gangs.push_back(a); } } sort(gangs.begin(),gangs.end(),comp); cout<<gangs.size()<<endl; for(int i = 0; i < gangs.size(); i++){ int tname = gangs[i].name; printf("%c%c%c",tname/26/26 + 'A',tname/26& + 'A',tname& + 'A'); printf(" %d\n",gangs[i].memb); } return 0; }