家庭房产L2-007

较为麻烦的并查集

主要是我的模板是错的检查了好久。。。。

先是输入 把每个家庭连在一起

输出的家庭编号为该家庭所有编号的最小值  在并查集里面完成

第一次 0~n-1遍历储存好 家庭编号 和房子面积和数量

第二次0~N遍历 遍历家庭人数

第三遍 处理人均面积和家庭数量和人均数量

#include<bits/stdc++.h>

using namespace std;

int f[];

int find1(int x)

{

    int j=x;

    while(j!=f[j])

        j=f[j];

    int cur=x;

    if(cur!=j)

    {

        int t=f[cur];

        f[cur]=j;

        cur=t;

    }

    return j;

}

void union1(int x,int y)

{

        int x1=find1(x);

        int y1=find1(y);

        if(x1<y1)f[y1]=x1;

        else  f[x1]=y1;

    return ;

}

struct peo

{

    int id;

    double n,s;

    int num;

    int flag;

    peo()

    {

        id=n=s=flag=num=;

    }

}s[],ans[];

int vis[]={};

bool cmp(struct peo a,struct peo b)

{

    if(a.s!=b.s)return a.s>b.s;

    else

        return  a.id<b.id;

}

int main()

{

    for(int i=;i<;i++)f[i]=i;

    int k,q;

    scanf("%d",&k);

    int a,b,c;

    for(int i=;i<k;i++)

    {

      scanf("%d%d%d",&a,&b,&c);

        s[i].id=a;

        vis[a]=;

        if(b!=-)

          {union1(a,b);vis[b]=;}

        if(c!=-)

           {union1(a,c);vis[c]=;}

        scanf("%d",&q);

        while(q--)

        {

            scanf("%d",&b);

            if(b!=-)

                {union1(b,a);vis[b]=;}

        }

        scanf("%lf%lf",&s[i].n,&s[i].s);

    }

    for(int i=;i<k;i++)

    {

       int a=find1( s[i].id );

       ans[ a ].id=a;

       ans[ a ].s+=s[i].s;

       ans[ a ].n+=s[i].n;

       ans[ a ].flag=;

    }

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

   {

       if(vis[i])

       {

           int a=find1( i );

           ans[a].num+=;

       }

   }

   int cnt=;

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

   {

       if(ans[i].flag)

       {    cnt++;

           ans[i].s=(double)ans[i].s/ans[i].num;

           ans[i].n=(double)ans[i].n/ans[i].num;

       }

   }

   sort(ans,ans+,cmp);

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

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

    printf("%04d %d %.3lf %.3lf\n",ans[i].id,ans[i].num,ans[i].n,ans[i].s);

}