【PAT甲级】1034 Head of a Gang (30 分)

题意：

输入两个正整数N和K（<=1000），接下来输入N行数据，每行包括两个人由三个大写字母组成的ID，以及两人通话的时间。输出团伙的个数（相互间通过电话的人数>=3），以及按照字典序输出团伙老大的ID和团伙的人数（团伙中通话时长最长的人视为老大，数据保证一个团伙仅有一名老大）。

AAAAAccepted code：

 #define HAVE_STRUCT_TIMESPEC

 #include<bits/stdc++.h>

 using namespace std;

 string s,s2;

 int x[],y[];

 vector<pair<int,int> >edge[];

 bool vis[];

 int val[];

 int mx=;

 int pos=;

 int ans[];

 int num[];

 int cnt=;

 int c[];

 bool visedge[];

 int sum2=;

 void dfs(int x){

     if(!vis[x])

         ++cnt;

     vis[x]=;

     for(auto it:edge[x]){

         if(visedge[it.second])

             continue;

         visedge[it.second]=;

         if(!vis[it.first]){

             ++cnt;

             vis[it.first]=;

         }

         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=;i<=n;++i){

         cin>>s>>s2>>c[i];

         x[i]=(s[]-'A')**+(s[]-'A')*+s[]-'A';

         y[i]=(s2[]-'A')**+(s2[]-'A')*+s2[]-'A';

         edge[x[i]].push_back({y[i],i});

         edge[y[i]].push_back({x[i],i});

     }

     int sum=;

     for(int i=;i<=n;++i){

         sum2=;

         mx=;

         pos=;

         cnt=;

         if(!vis[x[i]])

             dfs(x[i]);

         if(cnt>&&sum2>k){

             ans[pos]=sum2;

             num[pos]=cnt;

             ++sum;

         }

     }

     cout<<sum<<"\n";

     for(int i=;i<**;++i)

         if(ans[i]){

             char alp[];

             int tmp=i;

             alp[]=tmp//;

             tmp%=*;

             alp[]=tmp/;

             tmp%=;

             alp[]=tmp;

             for(int j=;j<=;++j){

                 alp[j]+='A';

                 cout<<alp[j];

             }

             cout<<" "<<num[i]<<"\n";

         }

     return ;

 }