7-11 家庭房産(25 分)
給定每個人的家庭成員和其自己名下的房産,請你統計出每個家庭的人口數、人均房産面積及房産套數。
輸入格式:
輸入第一行給出一個正整數N(≤1000),随後N行,每行按下列格式給出一個人的房産:
編号 父母 k 孩子1 ... 孩子k 房産套數 總面積
其中
編号
是每個人獨有的一個4位數的編号;
父
和
母
分别是該編号對應的這個人的父母的編号(如果已經過世,則顯示
-1
);
k
(0≤
k
≤5)是該人的子女的個數;
孩子i
是其子女的編号。
輸出格式:
首先在第一行輸出家庭個數(所有有親屬關系的人都屬于同一個家庭)。随後按下列格式輸出每個家庭的資訊:
家庭成員的最小編号 家庭人口數 人均房産套數 人均房産面積
其中人均值要求保留小數點後3位。家庭資訊首先按人均面積降序輸出,若有并列,則按成員編号的升序輸出。
輸入樣例:
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
輸出樣例:
3
8888 1 1.000 1000.000
0001 15 0.600 100.000
5551 4 0.750 100.000
【題意】
RT
【思路】
這道題相當于讓我們對有關系的人進行合并,然後輸出所有種族的資訊,很容易想到利用并查集
對于有家庭關系的,利用join函數把他們合并起來,并在join中把num,tao,area進行傳遞,由于題目要求了輸出時輸出該家庭編号最小的那個,是以在傳遞的時候往小的方向傳遞即可
有一個問題需要注意,在加某個人a的套數和面積數的時候,不應該直接加在a自己上面,應該加在find(a)上,因為後續在更新傳遞a的時候,用到的也是find後的結果,如果放在a上面,就傳不到祖先上面了
最後輸出的時候隻要輸出find(i)==i且出現過的人的資訊就好了
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mst(a,b) memset((a),(b),sizeof(a))
const int maxn=10005;
int n,m;
int vis[maxn];
int pre[maxn],num[maxn];
int tao[maxn],area[maxn];
struct node
{
int id,num,tao,area;
}a[maxn];
bool cmp(node a,node b){
if(a.num*b.area==a.area*b.num) return a.id<b.id;
return a.area*b.num>a.num*b.area;
}
void init(){
for(int i=0;i<maxn;i++){
pre[i]=i;
num[i]=1;
}
}
int find(int x){
int t,r=x;
while(x!=pre[x]){
x=pre[x];
}
while(r!=x){
t=pre[r];
pre[r]=x;
r=t;
}
return x;
}
void join(int a,int b){
vis[a]=vis[b]=1;
int A=find(a);
int B=find(b);
if(A==B) return;
if(A<B){
pre[B]=A;
num[A]+=num[B];
tao[A]+=tao[B];
area[A]+=area[B];
//num[B]=tao[B]=area[B]=0;
} else{
pre[A]=B;
num[B]+=num[A];
tao[B]+=tao[A];
area[B]+=area[A];
//num[A]=tao[A]=area[A]=0;
}
}
int main(){
init();
scanf("%d",&n);
for(int i=0;i<n;i++){
int tmp[10];
int a,b,c,k;
scanf("%d%d%d%d",&a,&b,&c,&k);
vis[a]=1;
for(int j=0;j<k;j++) scanf("%d",&tmp[j]);
int x,y;
scanf("%d%d",&x,&y);
tao[find(a)]+=x,area[find(a)]+=y;
if(b!=-1)join(a,b);
if(c!=-1)join(a,c);
for(int j=0;j<k;j++) join(a,tmp[j]);
}
int cnt=0;
for(int i=0;i<maxn;i++){
if(find(i)==i&&vis[i]){
a[cnt].id=i;
a[cnt].num=num[i];
a[cnt].tao=tao[i];
a[cnt++].area=area[i];
}
}
sort(a,a+cnt,cmp);
printf("%d\n",cnt);
for(int i=0;i<cnt;i++){
printf("%04d %d %.3f %.3f\n",a[i].id,a[i].num,a[i].tao*1.0/a[i].num,a[i].area*1.0/a[i].num);
}
}