2012年第4题
题目地址：http://pat.zju.edu.cn/contests/pat-a-practise/1034
C语言源码：
#include<stdio.h>#include<string.h>#include<limits.h>#include<stdlib.h>#define maxsize 2000int e[maxsize][maxsize];char name[maxsize][5];int visited[maxsize];typedef struct people{char name[6];int num;}people;people p[maxsize];int findname(char s[],int n){int i;i=0;while(i<n&&strcmp(name[i],s)!=0)i++;return i;}int num,gang,fmax,max;void dfs(int i,int n){int j;visited[i]=1;num++;for(j=0;j<n;j++)if(e[i][j]!=INT_MAX)gang+=e[i][j];for(j=0;j<n;j++)if(visited[j]==0&&e[i][j]!=INT_MAX)dfs(j,n);}int cmp(const void *a,const void *b){people *aa=(people *)a;people *bb=(people *)b;return strcmp(aa->name,bb->name);}void findmax(int i,int n){int j,sum;sum=0;visited[i]=1;for(j=0;j<n;j++)if(e[i][j]!=INT_MAX)sum+=e[i][j];if(sum>max){max=sum;fmax=i;}for(j=0;j<n;j++)if(visited[j]==0&&e[i][j]!=INT_MAX)findmax(j,n);}int main(){int n,k,i,j,point,time,a,b,gangnum,top,stack[maxsize][2],tops;char s1[5],s2[5];scanf("%d %d",&n,&k);for(i=0;i<maxsize;i++)for(j=0;j<maxsize;j++)e[i][j]=INT_MAX;point=0;for(i=0;i<n;i++){scanf("%s %s %d",s1,s2,&time);a=findname(s1,point);if(a==point)strcpy(name[point++],s1);b=findname(s2,point);if(b==point)strcpy(name[point++],s2);if(e[a][b]!=INT_MAX)e[a][b]+=time;elsee[a][b]=time;e[b][a]=e[a][b];}gangnum=0;top=0;tops=0;for(j=0;j<point;j++)visited[j]=0;for(i=0;i<point;i++){if(visited[i]==0){num=0;gang=0;dfs(i,point);gang=gang/2;if(num>2&&gang>k){gangnum++;stack[tops][0]=i;stack[tops++][1]=num;}}}for(j=0;j<point;j++)visited[j]=0;for(i=0;i<tops;i++){if(visited[stack[i][0]]==0){max=-1;findmax(stack[i][0],point);strcpy(p[top].name,name[fmax]);p[top++].num=stack[i][1];}}qsort(p,top,sizeof(p[0]),cmp);printf("%d\n",gangnum);for(i=0;i<top;i++)printf("%s %d\n",p[i].name,p[i].num);return 0;}