L2-007. 家庭房产
给定每个人的家庭成员和其自己名下的房产,请你统计出每个家庭的人口数、人均房产面积及房产套数。
输入格式:
输入第一行给出一个正整数N(<=1000),随后N行,每行按下列格式给出一个人的房产:
编号 父 母 k 孩子 ... 孩子 房产套数 总面积
其中 编号 是每个人独有的一个4位数的编号;父 和 母 分别是该编号对应的这个人的父母的编号(如果已经过世,则显示-1);k(0<=k<=5)是该人的子女的个数;孩子是其子女的编号。
输出格式:
首先在第一行输出家庭个数(所有有亲属关系的人都属于同一个家庭)。随后按下列格式输出每个家庭的信息:
家庭成员的最小编号 家庭人口数 人均房产套数 人均房产面积
其中人均值要求保留小数点后3位。家庭信息首先按人均面积降序输出,若有并列,则按成员编号的升序输出。
做题思路:
1、观察最后两行会发现,2222和2333有相同的孩子——他们的关系没法通过父母的关系网连接到一块;
所以输入孩子也应该连接进关系网中,如果在网中,孩子的父母也指向孩子的根节点;
否则,孩子指向他的该行的父或者母。
2/最后并查集记得进行再次全体进行寻根一次!
3、每次新开一个b【】数组时,记得立即初始化一次!!
4.还出了一个段错误! 您的程序发生段错误,可能是数组越界,堆栈溢出(比如,递归调用层数太多)等情况引起!
后来造了一组无厘头的数据:
3
1222 0 23 0 3 300
0 3 -1 0 1 0
3 0 -1 0 1 0
然后程序就炸了,接着仔细想想——搞了半天我没用上并查集的基本操作add()!!
AC程序:(附注释)
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<vector>
#include<map>
#define maxn 400000
#define inf 0x3f3f3f3f
using namespace std;
#define N 10018
struct node{
int mo,fa;
int k;//从0开始的
int kids[];
int suit;
int area;
}a[N];
struct family{
int root;//记录根的id
int minn_id;
int pnum;//人口总数
int suit;double avesuit;
int area;double avearea;
}b[N];
int tree[N];//建立一棵并查集,tree[i]=x,x表示i的父节点
int vis[N];//记录i是否记录进了人数
int getfa(int x){
if(x==tree[x])
return x;
return tree[x]=getfa(tree[x]);
}
void add(int x,int y){
int fa=getfa(x);
int fb=getfa(y);
if(fa!=fb){
tree[fa]=fb;
}
}
void init(family &x){
x.area=;x.suit=;
x.minn_id=;x.pnum=;
}
int fact1id(int i){
int num=i;
if(a[i].mo!=-)
num=min(a[i].mo,num);
if(a[i].fa!=-)
num=min(a[i].fa,num);
for(int j=;j<=a[i].k;j++){
num=min(a[i].kids[j],num);
}
return num;
}
int fact2(int i){
int num=;
if(vis[i]==){//别把自己也忘了!
num++;vis[i]=;
}
if(a[i].mo!=-&&vis[a[i].mo]==){
num++;vis[a[i].mo]=;
} if(a[i].fa!=-&&vis[a[i].fa]==){
num++;vis[a[i].fa]=;
}
for(int j=;j<=a[i].k;j++){
if(vis[a[i].kids[j] ]==)continue;
num++;
vis[a[i].kids[j] ]=;
}
return num;
}
bool cmp(family x,family y){
if(fabs(x.avearea-y.avearea)<1e-)
return x.minn_id<y.minn_id;
return x.avearea>y.avearea;
}
int main(){
int i,j,n;
scanf("%d",&n);
memset(vis,,sizeof(vis));
for(int i=;i<=;i++){
tree[i]=i;
a[i].area=-;
}
while(n--){
int id;
scanf("%d",&id);
scanf("%d%d",&a[id].fa,&a[id].mo);//确认并查集树上的父子关系
if(a[id].fa!=-){
add(id,a[id].fa);
}
if(a[id].mo!=-){
add(id,a[id].mo);
}
getfa(id); scanf("%d",&a[id].k);
for(int i=;i<=a[id].k;i++){//读入他的k个孩子的ID
scanf("%d",&a[id].kids[i]);
add(id,a[id].kids[i]);
}
scanf("%d%d",&a[id].suit,&a[id].area);
}
for(int i=;i<=;i++)//并查集重新调整一次!
getfa(i); int cnt=;//统计家庭数
set<int>s;//记录根节点
for(int i=;i<=;i++){
if(a[i].area==-){//不存在
continue;
}
int fa=tree[i];
int k;//表示开的family数组的序号
if(s.count(fa)>){
for(int j=;j<=cnt;j++){
if(b[j].root==fa){
k=j;break;
}
}
}else{
s.insert(fa);
++cnt;
k=cnt;
b[cnt].root=fa;//需要添加,别忘记了
init(b[k]);
}
//将a[i]数组的内容转移到b[k]中 b[k].area+=a[i].area;
b[k].minn_id=min(b[k].minn_id,fact1id(i) );
b[k].pnum+=fact2(i);
b[k].suit+=a[i].suit;
}
for(int i=;i<=cnt;i++){
b[i].avearea=b[i].area*1.0/(1.0*b[i].pnum);
b[i].avesuit=b[i].suit*1.0/(1.0*b[i].pnum);
}
sort(b+,b++cnt,cmp); printf("%d\n",cnt);
for(int i=;i<=cnt;i++){
printf("%04d %d %.3lf %.3lf\n",b[i].minn_id,b[i].pnum,b[i].avesuit,b[i].avearea);
} return ;
}