【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;   
}