repeat_ L2-007 family property_ set

repeat_PTA_7-11 Family property

//
7-11  Family property  (25  branch )
 Give everyone's family members and their own properties , Please count the population of each family 、 Per capita real estate area and number of real estate units .
 
 Input format ：
 The first line of input gives a positive integer N（≤1000）, And then N That's ok , Each line gives a person's property in the following format ：
 
 Number   Father   mother  k  children 1 ...  children k  Number of real estate units   Total area 
 The number is unique to everyone 4 Number of digits ; The parent and the parent are the number of the parent corresponding to the number （ If you have passed away , Is displayed -1）;k（0≤k≤5） It's the number of children of the person ; children i Is the number of their child .
 
 Output format ：
 First, output the number of families in the first line （ All relatives belong to the same family ）. Then output the information of each family in the following format ：
 
 Minimum number of family members   The number of families   Per capita number of real estate units   Per capita real estate area 
 The per capita value shall be kept after the decimal point 3 position . Family information is first output in descending order of per capita area , If there is juxtaposition , Then output... In ascending order of member number .
 
 sample input ：
10
6666 5551 5552 1 7777 1 100
1234 5678 9012 1 0002 2 300
8888 -1 -1 0 1 1000
2468 0001 0004 1 2222 1 500
7777 6666 -1 0 2 300
3721 -1 -1 1 2333 2 150
9012 -1 -1 3 1236 1235 1234 1 100
1235 5678 9012 0 1 50
2222 1236 2468 2 6661 6662 1 300
2333 -1 3721 3 6661 6662 6663 1 100
 sample output ：
3
8888 1 1.000 1000.000
0001 15 0.600 100.000
5551 4 0.750 100.000

// L2-007  Family property 
#include<bits/stdc++.h>
using namespace std;

// max == 1e3*8 < 2e4+5
const int N=2e4+5;
const int ID=1e4+5;

int father[N];
double sum[N];

set<int> s1,s2;

typedef struct home{ int cnt; double s; }H; H in[N];
typedef struct family{ int id,cnt1,cnt2; double p,s; }F; F ans[N];

int my_find( int x )
{
    return father[x]==x ? x : father[x]=my_find( father[x] );
}

void my_link( int a,int b )
{
    int ra=my_find(a),rb=my_find(b);

    if( ra>rb )         father[ra]=rb;
    else if( rb>ra )    father[rb]=ra;
}

bool cmp( F a,F b )
{   
    return ( a.s==b.s ) ? ( a.id<b.id ) : ( a.s>b.s ) ;
}

void init()
{
    for( int i=0;i<ID;i++ ) father[i]=i;

    memset( sum,0,sizeof( sum ) );
    memset( in,0,sizeof( in ) );
    memset( ans,0,sizeof( ans ) );
    
    s1.clear(); s2.clear();
}

int main()
{
    int n,a,b,c,k,x,root;

    while( ~scanf("%d",&n) )
    {
    	init();				// id  initialization  
        while( n-- )
        {
            scanf("%d%d%d%d",&a,&b,&c,&k); s1.insert( a );

            if( b!=-1 ) { s1.insert( b ); my_link( a,b ); }
            if( c!=-1 ) { s1.insert( c ); my_link( a,c ); }

            while( k-- ) { scanf("%d",&x); s1.insert(x); my_link( a,x ); }
            
            scanf("%d%lf",&in[a].cnt,&in[a].s );
        }
        for( auto i:s1 )
        {
            root=my_find(i); s2.insert(root);

            sum[root]+=in[i].s;				//  The cumulative  i  The data of   No  root 

            ans[root].id=root;
            ans[root].cnt1++;
            ans[root].cnt2+=in[i].cnt;
        }
        for( auto i:s2 )
        {
            ans[i].p=(double) ans[i].cnt2 / ans[i].cnt1;
            ans[i].s=sum[i] / ans[i].cnt1;
        }
        sort( ans,ans+ID,cmp );

        printf("%d\n",s2.size() );

        for( int i=0; i<s2.size() ;i++ )
        {
            printf("%04d %d %.3lf %.3lf\n", ans[i].id, ans[i].cnt1, ans[i].p, ans[i].s );
        }
    }
    return 0;
}