L2-007. 家庭房产
时间限制
400 ms
内存限制
65536 kB
代码长度限制
8000 B
给定每个人的家庭成员和其自己名下的房产,请你统计出每个家庭的人口数、人均房产面积及房产套数。
输入格式:
输入第一行给出一个正整数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
题目链接:https://www.patest.cn/contests/gplt/L2-007
题解
第一眼看题目就知道是并查集,不过,这么多属性用数组来做的话我一定会弄得稀里糊涂的,参观了zyyyyy的代码之后才发现结构体并查集大法好啊!
初始时,每个人都是独立的Famliy,通过find函数来确定两个人是否属于一个家庭,在find中,如果f[x] == -1则f[x]=x;
join的时候,永远都把id大的合并到id小的家庭中去(这里重载了Famlily的+运算);
接下来就是变输入边合并咯,每个家庭成员都和f[me]合并,最后输入suit和area之前再次find(f[me]),确保是家庭中的最小成员;
最后把f[i] == i的Family找出来,vector排序输出就好。排序重载了Famlily的<运算,由于保留三位小数,把area*1000后再进行比较可以防止浮点数误差,注意比较的是均值不是总值,最后输出的suit和area也都是均值。
//#include <bits/stdc++.h>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
#include<string.h>
#include<string>
#include<stack>
#include<queue>
#include<set>
#include<sstream>
#include<iostream>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn = ;
int f[maxn];
struct Family{
int id, num, suit;
double area;
Family(){
num = ;
suit = ;
area = ;
}
Family operator + (const Family &b){
num += b.num;
suit += b.suit;
area += b.area;
return *this;
}
bool operator < (const Family &b){
double x = area*/num;
double y = b.area*/b.num;
if(x != y) return x>y;
else return id<b.id;
}
}fm[maxn];
int find(int x){
if (f[x] == -) return f[x] = x;
if(f[x] == x) return x;
else return f[x] = find(f[x]);
}
int join(int x, int y){
x = find(x);
y = find(y);
if(x == y) return ;
if(x<y){
f[y] = x;
fm[x] = fm[x] + fm[y];
}
else{
f[x] = y;
fm[y] = fm[y] + fm[x];
}
return ;
}
int main(){
int n;
while(scanf("%d", &n) == && n){
for(int i=; i<maxn; i++){
f[i] = -;
fm[i].id = i;
}
for(int i=; i<n; i++){
int me, fa, ma, k;
scanf("%d%d%d%d", &me, &fa, &ma, &k);
f[me] = find(me);
if(fa != -)
join(fa, f[me]);
if(ma != -)
join(ma, f[me]);
while(k--){
int ch;
scanf("%d", &ch);
join(ch, f[me]);
}
f[me] = find(f[me]);
int suit; double area;
scanf("%d%lf", &suit, &area);
fm[f[me]].suit += suit;
fm[f[me]].area += area;
}
vector<Family> v;
for(int i=; i<maxn; i++){
if(f[i] == i){
v.push_back(fm[i]);
}
}
sort(v.begin(), v.end());
printf("%d\n", v.size());
for(int i=; i<v.size(); i++){
printf("%04d %d %.3lf %.3lf\n", v[i].id, v[i].num, (double)v[i].suit/(double)v[i].num, v[i].area/v[i].num);
}
}
return ;
}