【1114】Family Property (25分)【并查集】

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<math.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<algorithm> 
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<queue> 
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     

      struct DATA{
     
    
   

    

     

    
    

     
	int id,fid,mid,num,area;
     
    
   

    

     

    
    

     
	int cid[10];//这个人node的孩子数组cid[]
     
    
   

    

     

    
    

     

      }data[1005];
     
    
   

    

     

    
    

     

      struct node{
     
    
   

    

     

    
    

     
	int id,people;//people为家庭总人数
     
    
   

    

     

    
    

     
	double num,area;
     
    
   

    

     

    
    

     
	bool flag;
     
    
   

    

     

    
    

     

      }ans[10000];
     
    
   

    

     

    
    

     

      int father[10000];
     
    
   

    

     

    
    

     

      bool visit[10000];
     
    
   

    

     

    
    

     

      int findfather(int x){
     
    
   

    

     

    
    

     
	while(x!=father[x])//如果不是根结点，继续循环
     
    
   

    

     

    
    

     

      		x=father[x];//获得自己的父亲结点
     
    
   

    

     

    
    

     
	return x;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void Union(int a,int b){
     
    
   

    

     

    
    

     
	int faA=findfather(a);//查找a的根结点
     
    
   

    

     

    
    

     
	int faB=findfather(b);//查找b的根结点
     
    
   

    

     

    
    

     
	//if(faA!=faB){//如果不属于同一个集合
     
    
   

    

     

    
    

     
	// father[faA]=faB;//合并
     
    
   

    

     

    
    

     
	if(faA>faB)
     
    
   

    

     

    
    

     

      		father[faA]=faB;
     
    
   

    

     

    
    

     
	else if(faA<faB)
     
    
   

    

     

    
    

     

      		father[faB]=faA;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int cmp1(node a,node b){
     
    
   

    

     

    
    

     
	if(a.area!=b.area)
     
    
   

    

     

    
    

     
		return a.area>b.area;//按人均地面积降序
     
    
   

    

     

    
    

     
	else
     
    
   

    

     

    
    

     
		return a.id<b.id;//按姓名编号的升序
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
   
     
    
   

    

     

    
    

     

      int main(){   
     
    
   

    

     

    
    

     
	int n,k,cnt=0;
     
    
   

    

     

    
    

     
	scanf("%d",&n);//n行的数据需要读入
     
    
   

    

     

    
    

     
	for(int i=0;i<10000;i++)
     
    
   

    

     

    
    

     

      		father[i]=i;//初始化并查集
     
    
   

    

     

    
    

     
	for(int i=0;i<n;i++){//以下n行读取
     
    
   

    

     

    
    

     
		scanf("%d %d %d %d",&data[i].id,&data[i].fid,
     
    
   

    

     

    
    

     

      			&data[i].mid,&k);
     
    
   

    

     

    
    

     

      		visit[data[i].id]=true;//标记出现的人
     
    
   

    

     

    
    

     
		if(data[i].fid!=-1){//如果老爸还没挂
     
    
   

    

     

    
    

     

      			visit[data[i].fid]=true;
     
    
   

    

     

    
    

     
			Union(data[i].fid,data[i].id);
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		if(data[i].mid!=-1){//如果老妈还没挂
     
    
   

    

     

    
    

     

      			visit[data[i].mid]=true;
     
    
   

    

     

    
    

     
			Union(data[i].mid,data[i].id);
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

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

    

     

    
    

     
			scanf("%d",&data[i].cid[j]);
     
    
   

    

     

    
    

     

      			visit[data[i].cid[j]]=true;
     
    
   

    

     

    
    

     
			Union(data[i].cid[j],data[i].id);
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		scanf("%d %d",&data[i].num,&data[i].area);
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

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

    

     

    
    

     
		int id=findfather(data[i].id);
     
    
   

    

     

    
    

     

      		ans[id].id=id;
     
    
   

    

     

    
    

     

      		ans[id].num+=data[i].num;//奇妙的累加
     
    
   

    

     

    
    

     

      		ans[id].area+=data[i].area;
     
    
   

    

     

    
    

     

      		ans[id].flag=true;//不可删，代表该个家庭存在
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	for(int i=0;i<10000;i++){
     
    
   

    

     

    
    

     
		if(visit[i])
     
    
   

    

     

    
    

     
			//如果有该人，注意不能再上面的for(n行)里统计
     
    
   

    

     

    
    

     
			//因为每行可能还有多个人
     
    
   

    

     

    
    

     

      			ans[findfather(i)].people++;
     
    
   

    

     

    
    

     
		if(ans[i].flag)
     
    
   

    

     

    
    

     

      			cnt++;//统计家庭数
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	for(int i=0;i<10000;i++){
     
    
   

    

     

    
    

     
		if(ans[i].flag){
     
    
   

    

     

    
    

     
			//ans[i].num=(double)(ans[i].num*1.0/ans[i].people);
     
    
   

    

     

    
    

     

                          ans[i].num=(ans[i].num*1.0/ans[i].people);
     
    
   

    

     

    
    

     
			//把double去掉也是可以的
     
    
   

    

     

    
    

     
			//ans[i].area=(double)(ans[i].area*1.0/ans[i].people);
     
    
   

    

     

    
    

     

                          ans[i].area=(ans[i].area*1.0/ans[i].people);
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	sort(ans,ans+10000,cmp1);
     
    
   

    

     

    
    

     
	printf("%d\n",cnt);
     
    
   

    

     

    
    

     
	for(int i=0;i<cnt;i++)
     
    
   

    

     

    
    

     
		printf("%04d %d %.3f %.3f\n",ans[i].id,ans[i].people,ans[i].num,ans[i].area);
     
    
   

    

     

    
    

     
	system("pause");
     
    
   

    

     

    
    

     
    return 0;   
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/103941463