[并查集 维护大小 全局输入]L2-007 家庭房产

[并查集]L2-007 家庭房产

​​题目链接​​

思路

显然的并查集题目，感觉要维护挺多东西的
维护集合最小编号，集合大小，集合房产套数，集合房产面积（人均的到时候除以下大小就完事了）
输入比较恶心，我选择先全部读取后再处理

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10,M=1E5+10;
struct input
{
  int id,fid,mid,k;
  int child[7];
  double num,siz;
}in[N];
struct mySet
{
  int fa,minid,pnum;
  double hnum,siz;
}f[M];
bool query[M];//看是否实际存在这个人
int find(int x)
{
  if(f[x].fa!=x)f[x].fa=find(f[x].fa);
  return f[x].fa;
}
void set_merge(int x,int y)
{
  int fx=find(x),fy=find(y);
  if(fx!=fy)
  {
    f[fy].siz+=f[fx].siz;
    f[fy].hnum+=f[fx].hnum;
    f[fy].pnum+=f[fx].pnum;
    f[fy].minid=min(f[fy].minid,f[fx].minid);
    f[fx].fa=fy;
  }
}

bool cmp(const mySet& A,const mySet& B)
{
  double pa=A.siz/A.pnum,pb=B.siz/B.pnum;
  if(fabs(pa-pb)>1e-6)return pa>pb;
  return A.minid<B.minid;
}
int main()
{
  //输入
  int n;cin>>n;
  for(int i=1;i<=n;i++)
  {
    cin>>in[i].id>>in[i].fid>>in[i].mid>>in[i].k;
    for(int j=1;j<=in[i].k;j++)cin>>in[i].child[j];
    cin>>in[i].num>>in[i].siz;
  }

  //初始化
  for(int i=0;i<=9999;i++)f[i].fa=i,f[i].minid=i,f[i].pnum=1;
  for(int i=1;i<=n;i++)
  {
    int ID=in[i].id;
    double Hnum=in[i].num,Hsiz=in[i].siz;
    f[ID].hnum=Hnum,f[ID].siz=Hsiz;
  }
  
  //合并
  for(int i=1;i<=n;i++)
  {
    int ID=in[i].id,FID=in[i].fid,MID=in[i].mid,K=in[i].k;;
    query[ID]=1;
    if(FID!=-1)query[FID]=1,set_merge(ID,FID);
    if(MID!=-1)query[MID]=1,set_merge(ID,MID);
    for(int j=1;j<=K;j++)
    {
      query[in[i].child[j]]=1;
      set_merge(ID,in[i].child[j]);
    }
  }
  int cnt=0;
  vector<mySet>v;
  for(int i=0;i<=9999;i++)
  {
    if(query[i]&&f[i].fa==i)
    {
      ++cnt;
      v.push_back(f[i]);
    }
  }
  sort(v.begin(),v.end(),cmp);
  printf("%d\n",cnt);
  for(int i=0;i<cnt;i++)
    printf("%04d %d %.3lf %.3lf\n",v[i].minid,v[i].pnum,v[i].hnum/v[i].pnum,v[i].siz/v[i].pnum);
  
}