PAT 1034. Head of a Gang

题目：http://pat.zju.edu.cn/contests/pat-a-practise/1034

题意：给你N个通话记录，k值。问你有几个“Gang”，每个"Gang"中成员数量，以及关系权值和（relation weight）最大的成员。每个“Gang”是一个满足特定条件的连通分量，即最少有3个成员，且边上的权值和大于K。关于计算AAA的relation weight，通话记录中AAA每出现一次，就要累加上那个通话记录的权值(也是边权)。

思路：并查集的应用。计算无向图连通分量个数，以及每个成员属于哪个连通分量。

代码：

#include<cstdio>
#include<cstring> 
#include<map>
#include<algorithm>
using namespace std;
int f[26*26*26+10],tmp[26*26*26+10];
struct node
{
   int id,count;
}p[1001];
struct link
{
   int s,e,w;
}l[1001];
bool cmpp(node a,node b)
{
   if(a.id<b.id) return true;
   return false;
}
int find(int x)
{
   if(f[x]==x) return x;
   return f[x]=find(f[x]);    //该句可压缩查找路径，相比较return find(f[x])。
}
void Union(int a,int b)
{
        int x=find(a);
	int y=find(b);
	if(x!=y) f[y]=x;
}
int main()
{
	int i,n,k,w;
	char name1[5],name2[5];
	while(scanf("%d%d",&n,&k)!=EOF)
	{
		map<int,int> mapp;
	        for(i=0;i<n;i++)
		{
		  scanf("%s%s%d",name1,name2,&w);
		  int num1=(name1[0]-‘A‘)*26*26+(name1[1]-‘A‘)*26+name1[2]-‘A‘;
		  int num2=(name2[0]-‘A‘)*26*26+(name2[1]-‘A‘)*26+name2[2]-‘A‘;
		  if(mapp[num1]==0) f[num1]=num1;
		  if(mapp[num2]==0) f[num2]=num2;
		  Union(num1,num2);
		  mapp[num1]+=w;
		  mapp[num2]+=w;
		  l[i].s=num1;l[i].e=num2;
		  l[i].w=w;
		}
		map<int,int>::iterator it;
		int kk=0;
		for(it=mapp.begin();it!=mapp.end();it++)
		{
			f[it->first]=find(it->first);    //这句不能遗忘，Union过程后每个F[i]只是中间过程产生的祖先。最终祖先要find。
			if(f[it->first]==it->first) tmp[kk++]=it->first;
		}
		int ans=0,j;
		for(i=0;i<kk;i++)
		{
			int max=0,maxi,totallweight=0,count=0;
			for(j=0;j<n;j++)
				    if(f[l[j].s]==tmp[i]||f[l[j].e]==tmp[i]) totallweight+=l[j].w;
			if(totallweight<=k) continue;
			for(it=mapp.begin();it!=mapp.end();it++)
			      if(f[it->first]==tmp[i]) 
				  {		 
					 count++;
				        if(it->second>max)
					 {
					     max=it->second;
					     maxi=it->first;
					 }
				  }
			if(count>2)
			{
			   p[ans].id=maxi;
			   p[ans++].count=count;
			}
		}
		sort(p,p+ans,cmpp);
		printf("%d\n",ans);
		for(i=0;i<ans;i++)	
		   printf("%c%c%c %d\n",p[i].id/(26*26)+‘A‘,(p[i].id/26)%26+‘A‘,p[i].id%26+‘A‘,p[i].count);	
	}
	return 0;
}

PAT 1034. Head of a Gang,布布扣,bubuko.com

PAT 1034. Head of a Gang

原文：http://blog.csdn.net/zqh_1991/article/details/21175699