题意：
输入两个正整数N和K（<=1000），接下来输入N行数据，每行包括两个人由三个大写字母组成的ID，以及两人通话的时间。输出团伙的个数（相互间通过电话的人数>=3），以及按照字典序输出团伙老大的ID和团伙的人数（团伙中通话时长最长的人视为老大，数据保证一个团伙仅有一名老大）。
代码：
#define HAVE_STRUCT_TIMESPEC
#include<bits/stdc++.h>
using namespace std;
string s,s2;
int x[1007],y[1007];
vector<pair<int,int> >edge[20007];
bool vis[20007];
int val[20007];
int mx=0;
int pos=0;
int ans[20007];
int num[20007];
int cnt=0;
int c[1007];
bool visedge[1007];
int sum2=0;
void dfs(int x){
if(!vis[x])
++cnt;
vis[x]=1;
for(auto it:edge[x]){
if(visedge[it.second])
continue;
visedge[it.second]=1;
if(!vis[it.first]){
++cnt;
vis[it.first]=1;
}
val[x]+=c[it.second];
val[it.first]+=c[it.second];
sum2+=c[it.second];
if(val[x]>mx){
mx=val[x];
pos=x;
}
dfs(it.first);
}
}
int main(){
int n,k;
cin>>n>>k;
for(int i=1;i<=n;++i){
cin>>s>>s2>>c[i];
x[i]=(s[0]-‘A‘)*26*26+(s[1]-‘A‘)*26+s[2]-‘A‘;
y[i]=(s2[0]-‘A‘)*26*26+(s2[1]-‘A‘)*26+s2[2]-‘A‘;
edge[x[i]].push_back({y[i],i});
edge[y[i]].push_back({x[i],i});
}
int sum=0;
for(int i=1;i<=n;++i){
sum2=0;
mx=0;
pos=0;
cnt=0;
if(!vis[x[i]])
dfs(x[i]);
if(cnt>2&&sum2>k){
ans[pos]=sum2;
num[pos]=cnt;
++sum;
}
}
cout<<sum<<"\n";
for(int i=0;i<26*26*26;++i){
if(ans[i]){
char alp[3];
int tmp=i;
alp[0]=tmp/26/26;
tmp%=26*26;
alp[1]=tmp/26;
tmp%=26;
alp[2]=tmp;
for(int j=0;j<=2;++j){
alp[j]+=‘A‘;
cout<<alp[j];
}
cout<<" "<<num[i]<<"\n";
}
}
return 0;
}
【PAT甲级】1034 Head of a Gang (30 分)
原文：https://www.cnblogs.com/ldudxy/p/11521016.html