题意:给出每个人的家庭成员信息和自己的房产个数与房产总面积,让你统计出每个家庭的人口数、人均房产个数和人均房产面积。第一行输出家庭个数,随后每行输出家庭成员的最小编号、家庭人口数、人均房产个数、人均房产面积。

并查集,合并的时候编号小的作为父亲节点,最后父亲节点一样的即属于一个家庭,其它都是细节处理没啥好说了。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
using namespace std;
/*
并查集
*/
const int maxn=+;
int vis[maxn];
struct UF{
int father[maxn];
void init(){
for(int i=;i<maxn;i++){
father[i]=i;
}
}
int find_root(int x){
if(father[x]!=x){
father[x]=find_root(father[x]);
}
return father[x];
}
void Union(int a,int b){
int fa=find_root(a);
int fb=find_root(b);
if(fa!=fb){
father[max(fa,fb)]=min(fa,fb); //最小编号的作为祖先
}
}
}uf; struct Person{
int id;
int dad,mom;
int k;
int child[];
int m_estate;
int area;
}person[maxn]; struct Family{
int minid; //家庭成员最小编号
int m=; //家庭人口数
int m_estate=; //总房产数目
int totarea=; //总房产面积
float AVG_sets; //人均房产个数
float AVG_area; //人均房产面积
bool operator<(const Family tmp)const{
if(AVG_area==tmp.AVG_area){
return minid<tmp.minid;
}
else{
return AVG_area>tmp.AVG_area;
}
}
}family[maxn]; int main()
{
int n,id;
scanf("%d",&n);
uf.init();
memset(vis,,sizeof(vis));
for(int i=;i<maxn;i++)
person[i].id=-;
for(int i=;i<n;i++){
scanf("%d",&id);
person[id].id=id;
scanf("%d %d %d",&person[id].dad,&person[id].mom,&person[id].k);
vis[person[id].id]=; //标记出现过的编号
if(person[id].dad!=-){
uf.Union(id,person[id].dad);
vis[person[id].dad]=;
}
if(person[id].mom!=-){
uf.Union(id,person[id].mom);
vis[person[id].mom]=;
}
for(int j=;j<person[id].k;j++){
scanf("%d",&person[id].child[j]);
uf.Union(id,person[id].child[j]);
vis[person[id].child[j]]=;
}
scanf("%d %d",&person[id].m_estate,&person[id].area);
}
int idArray[maxn];
int cnt=;
for(int i=;i<maxn;i++){
if(vis[i]==){
idArray[cnt++]=i; //出现过的编号存起来
}
}
memset(vis,,sizeof(vis));
int u,fa;
for(int i=;i<cnt;i++){
u=idArray[i];
fa=uf.find_root(idArray[i]);
vis[fa]=; //标记父亲节点
family[fa].minid=fa;
family[fa].m++;
if(person[u].id!=-){
family[fa].totarea+=person[u].area;
family[fa].m_estate+=person[u].m_estate;
}
}
int familyNum=;
for(int i=;i<maxn;i++){
if(vis[i]){
familyNum++;
family[i].AVG_sets=family[i].m_estate*1.0f/family[i].m;
family[i].AVG_area=family[i].totarea*1.0f/family[i].m;
}
}
sort(family,family+maxn);
printf("%d\n",familyNum);
for(int i=;i<familyNum;i++){
printf("%04d %d %.3f %.3f\n",family[i].minid,family[i].m,family[i].AVG_sets,family[i].AVG_area);
}
return ;
}

最新文章

  1. tomcat linux下的部署安装
  2. db2look导出ddl 详细用法(转)
  3. VS2012 Unit Test —— 我对接口进行单元测试使用的技巧
  4. iOS开源项目、框架资源
  5. 解决VMware“该虚拟机似乎正在使用中”问题
  6. ☆ fragment和fragmentactivity解析 (转)
  7. C# 32位md5
  8. 1350. Canteen(map)
  9. Scala-逻辑判断
  10. poj3258 二分 最小值最大化问题
  11. hdu_5925_Coconuts(离散化+dfs)
  12. Entity Framework技巧系列之二 - Tip 6 - 8
  13. meta 常用标签总结
  14. IFieldEdit Interface 接口
  15. 永久关闭selinux | 防火墙
  16. 【Alpha阶段】第四次 Scrum Meeting
  17. Android相关面试题---面试官常问问题
  18. mysql数据库导入与导出
  19. CAD2007_DWG转PDF
  20. HTML 常用小技巧 【标题图标】【锚点】【插入音乐,视频】【滚动效果】【嵌入网页】

热门文章

  1. JSR规范
  2. 开通博客啦 Let‘s Go!
  3. 探索C#字符串
  4. ntp时间服务器--Linux配置
  5. css图片替换方法
  6. [部署]VM11下CentOS7mini安装及配置
  7. 对比flash与ajax哪个好?
  8. JVM系列三:JVM参数设置
  9. 20165302 程上杰 Exp1 PC平台逆向破解
  10. QGIS里的编程模型