link :https://pintia.cn/problem-sets/994805046380707840/problems/994805068539215872


subject :

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(≤), 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 

among Number It's a unique one for everyone 4 Number of digits ; Father and mother They are the numbers of the parents of the corresponding person ( If you have passed away , Is displayed -1);k(0k≤) 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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm> using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf=0x3f3f3f3f;
const int maxn=1e4+;
int n,p1,p2,k,d;
int fa[maxn],vis[maxn]; struct node{
int id;
double ans,sum;
}kk[maxn]; struct he{
int id,num,ans,sum;
double avgans,avgsum;
}final[maxn]; void init(){
for(int i=;i<;i++){
fa[i]=i;
final[i].id=;
final[i].num=;
final[i].ans=;
final[i].sum=;
final[i].avgans=;
final[i].avgsum=;
}
} int cmp(he a,he b){
if(a.avgsum==b.avgsum) return a.id<b.id;
else return a.avgsum>b.avgsum;
} int find(int x){
if(fa[x]==x) return x;
else return fa[x]=find(fa[x]);
} void unite(int x,int y){
x=find(x);
y=find(y);
if(x==y) return;
else fa[y]=x;
} int main(){
init();
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d%d%d",&kk[i].id,&p1,&p2);
vis[kk[i].id]=;
if(p1!=-){
unite(kk[i].id,p1);
vis[p1]=;
}
if(p2!=-){
unite(kk[i].id,p2);
vis[p2]=;
}
scanf("%d",&k);
for(int j=;j<=k;j++){
scanf("%d",&d);
unite(kk[i].id,d);
vis[d]=;
}
scanf("%lf%lf",&kk[i].ans,&kk[i].sum);
}
for(int i=;i<=n;i++){
int tmp=find(kk[i].id);
final[tmp].ans+=kk[i].ans;
final[tmp].sum+=kk[i].sum;
}
for(int i=;i<;i++){
if(vis[i]){
fa[i]=find(i);
if(!final[fa[i]].num)
final[fa[i]].id=i;
final[fa[i]].num++;
final[fa[i]].avgans=final[fa[i]].ans*1.0/final[fa[i]].num;
final[fa[i]].avgsum=final[fa[i]].sum*1.0/final[fa[i]].num;
}
}
int ans=;
sort(final,final+,cmp);
for(int i=;i<;i++){
if(final[i].num) ans++;
else break;
}
printf("%d\n",ans);
for(int i=;i<ans;i++){
printf("%04d %d %.3f %.3f\n",final[i].id,final[i].num,final[i].avgans,final[i].avgsum);
}
return ;
}

0001 15 0.600 100.000
5551 4 0.750 100.000

 Ideas :
The point is to find every family Use and search to connect all of a family to an ancestor Every time you read in, parents and children do it and look it up
The trouble is that you have to deal with a lot of data More complicated
First, connect the parents and children in the same family And then recycle it Update the total number of rooms and total area of the family I'm going to go through the loop again and find the average Then output it

 Code :

L2-007 Family property (25 branch ) ( Union checking set ) More articles about

  1. L2-007 Family property (25 branch ) Union checking set

    Topic link Answer key : And look up the collection of a family together , The special point is to number the big one and go to the small one . There is a hole in this question. The number may be 0000, Wrong data 3 and 5. 1 #include<bits/stdc++.h> 2 usin ...

  2. L2-013 Red Alert (25 branch ) And look up the complexity

    Code : 1 /* 2 This problem is also simple and easy to collect , And look up the complexity : 3 The space complexity is O(N), The time complexity of building a set is O(1),N The merger M The time complexity of the search is O(M Alpha(N)), 4 here Alpha yes ...

  3. PAT-1021 Deepest Root (25 branch ) And check the set to judge the ring and connection + Find the depth of the tree

    A graph which is connected and acyclic can be considered a tree. The height of the tree depends on t ...

  4. PAT Answer to question a -1114. Family Property (25)-( And look up the template questions )

    The question : Give each person's family members information and their own number of real estate and the total area of real estate , Let's count the population of each family . The number of real estate per capita and the area of real estate per capita . The first line outputs the number of families , Then each line outputs the minimum number of the family member . The number of families . The number of houses per capita . Per capita housing ...

  5. PAT-1107 Social Clusters (30 branch ) And look up the template

    1107 Social Clusters (30 branch ) When register on a social network, you are always asked to specify your ...

  6. PAT A 1118. Birds in Forest (25)【 Union checking set 】

    And look up the set and merge #include<iostream> using namespace std; const int MAX = 10010; int father[MAX],root[MAX] ...

  7. PAT Answer to question a -1021. Deepest Root (25)-dfs+ Union checking set

    dfs Find the maximum number of layers and look up the set to find the number of connected #include <iostream> #include <cstdio> #include <algorithm> #inclu ...

  8. PAT Answer key -1118. Birds in Forest (25)-( And look up the template questions )

    As the title ... #include <iostream> #include <cstdio> #include <algorithm> #include <stri ...

  9. PAT Answer to question a -1126. Eulerian Path (25)- Euler circuit + And look up the set to judge the connectivity of the graph

    The topic has already told us how to judge the Euler circuit , There's one thing to note about the rest , Maybe the graph itself is not connected . So we use union search to judge the connectivity of graphs . #include <iostream> #include <cstdio ...

  10. 1021. Deepest Root (25)——DFS+ Union checking set

    http://pat.zju.edu.cn/contests/pat-a-practise/1021 An acyclic connected graph can also be regarded as a tree , Select any point in the graph as the root , If the depth of the whole tree is the largest at this time , It's called deep ...

Random recommendation

  1. Fiddler Set the notebook as a proxy , Grab the mobile network request package

    First step : download fiddler, Download address :http://www.telerik.com/download/fiddler The second step : install fiddler, skip ... The third step : start-up fiddler, After startup, the interface is as follows ...

  2. SQL Server Common basic operations

    1. Common operations for tables ( Additions and deletions ) --1. Create Table USE [MVC_000] CREATE TABLE T_TableName ( ID ,) PRIMARY KEY, Name ...

  3. Linux Platform boost Install the full solution

    @import url(http://i.cnblogs.com/Load.ashx?type=style&file=SyntaxHighlighter.css); @import url(/ ...

  4. maven Suggest solutions to errors

    import perhaps new One of them maven project When , Note the following error Description    Resource    Path    Location    TypeCannot read ...

  5. Learn from examples js Object oriented encapsulation and inheritance

    1. Object oriented features Compared with the previous process style , Object oriented has the following characteristics ; 1. abstract : Get to the core , That is to put many methods on one object . Objects consist of properties and methods , Properties are variables that we define , It's static : The method is behavioral manipulation , ...

  6. iOS Performance WebP

    Today's Internet , Whether it's a web page or APP, The biggest traffic , Most of it's because of the pictures , The better the user experience , The more dependent you are on images . But the picture is a double-edged sword , Brings the user experience , Attracted users' attention , But it affects performance , Because the network request time will be relatively short ...

  7. Using pseudo class before and after

    .content { padding: 20px } .content::before { content: " I am a before Added content "; font-weight: bold ...

  8. Data pump expdp stay rac In the environment paralle Treatment method

    In fact, this is a very common problem , Write it down as a souvenir . explain : And in the 11GR2 after EXPDP and IMDP Of WORKER The process is setting parallel Parameter will be in multiple INSTANCE start-up , therefore DIRECTORY Must be on shared disk ...

  9. Android Wear Create a notification

    establish Android Wear It's actually no different from creating a notification on a mobile phone , The main reason is that there are several new classes , As long as you are familiar with it, everything will be easy .( If it's just a test notification , It runs directly wear app You can see the effect ) Create a simple wear Notification points ...

  10. day76

    Look back yesterday :  1 ajax What is? ajax: Asynchronous JavaScript and xml  2 characteristic : asynchronous , Partial refresh   3 Simple interaction with the background :( Carrying data : You can spell url On ----> from GET To take ,)   ...