【PAT】1114. Family Property (25)【并查集、结构体排序】

本文主要是介绍【PAT】1114. Family Property (25)【并查集、结构体排序】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

This time, you are supposed to help us collect the data for family-owned property. Given each person’s family members, and the estate（房产）info under his/her own name, we need to know the size of each family, and the average area and number of sets of their real estate.

翻译：这一次，你需要帮助我们收集一个家族拥有的财产数据。给定每个家庭成员和在他/她的名义下的房地产(房产)信息，我们需要知道每个家庭的人口数，房产个数以及平均面积。

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤1000). Then N lines follow, each gives the infomation of a person who owns estate in the format:
ID Father Mother k Child₁⋯Child_k Mestate Area

where ID is a unique 4-digit identification number for each person; Father and Mother are the ID’s of this person’s parents (if a parent has passed away, -1 will be given instead); k (0≤k≤5) is the number of children of this person; Child_i’s are the ID’s of his/her children; Mestate
is the total number of sets of the real estate under his/her name; and Area is the total area of his/her estate.

翻译：每个输入文件包含一组测试数据。对于每组输入数据，第一行给出一个正整数N(≤1000)。接下来N行，每行按照以下格式给出一个人的拥有房产情况的信息：
ID Father Mother k Child₁⋯Child_k Mestate Area

ID为一个特定的4位数字标识一个人员，Father 和 Mother代表这个人的父母（如果父母一方去世，则用-1来代替）；k(0≤k≤5)代表这个人拥有的孩子总数；Child_i代表孩子的ID；Mestate代表在他名下的实际房产总数，Area代表他的房产的总面积。

Output Specification:

For each case, first print in a line the number of families (all the people that are related directly or indirectly are considered in the same family). Then output the family info in the format:

ID M AVG_sets AVG_area

where ID is the smallest ID in the family; M is the total number of family members; AVG_sets is the average number of sets of their real estate; and AVG_area is the average area. The average numbers must be accurate up to 3 decimal places. The families must be given in descending order of their average areas, and in ascending order of the ID’s if there is a tie.

翻译：对于每组输入数据，输出一行家族的个数(所有有直接或间接关系的人都被认为是同一家庭)。接着按照以下格式输出一个家族的情况：
ID M AVG_sets AVG_area
ID代表家族成员的最小ID;M 代表家族成员的总人数；AVG_sets代表他们平均拥有的实际房产数。 AVG_area 代表他们平均拥有的房产面积。平均数需要保留3位小数。家族必须按照它们的平均拥有房产面积大小降序排序，如果相同则按照ID大小升序排序。

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
0001 15 0.600 100.000
5551 4 0.750 100.000

解题思路

定义一个成员类，然后编写并查集，通过并查集将相同家族的成员合并在一起。然后对成员进行扫描，如果该成员在一个家族内且该家族的最小ID不是他则把他的数据加给该家族的最小ID。最后对家族排序。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<vector>
#include<algorithm>
#define INF 99999999
#define bug puts("Hello\n")
using namespace std;
int N;
int num[10000];//用于记录该id对应的家族人数 
struct Peo{int id;double mestate;double area;Peo():id(0),mestate(0),area(0.0){}Peo(int ID,int Mestate,double Area):id(ID),mestate(Mestate),area(Area){}Peo operator+(const Peo &a)const{double tmpmestate=mestate+a.mestate;double tmparea=area+a.area;return Peo(id,tmpmestate,tmparea);}bool operator<(const Peo &a)const{double averArea=area/num[id];double a_averArea=a.area/num[a.id];return averArea==a_averArea?id<a.id:averArea>a_averArea;}
};
Peo peo[10000];
int people[10000];//并查集 
int ans[10000];//保存该家族的最小编号 
Peo ansPeo[10000]; //将财产累计过后的该家族成员加入数组 
int anscount=0;
void init(){for(int i=0;i<10000;i++){peo[i].id=i;people[i]=i;} 
}
int find(int a){if(people[a]==a)return a;else return people[a]=find(people[a]);
}
void Union(int a,int b){int fa=find(a);int fb=find(b);if(fa<fb)people[fb]=fa;else people[fa]=fb;
}int main(){scanf("%d",&N);init();int pid,fa,mo,k;for(int i=0;i<N;i++){scanf("%d%d%d%d",&pid,&fa,&mo,&k);num[pid]=1;if(fa>=0)Union(pid,fa),num[fa]=1;if(mo>=0)Union(pid,mo),num[mo]=1;int cid;for(int i=0;i<k;i++){scanf("%d",&cid);num[cid]=1;Union(cid,pid);}double Mstate;double Area;scanf("%lf%lf",&Mstate,&Area);peo[pid].mestate=Mstate;peo[pid].area=Area;}for(int i=0;i<10000;i++){int tmp=find(people[i]);if(tmp==i&&num[i]){ans[anscount++]=tmp;}else if(num[i]){peo[tmp]=peo[tmp]+peo[i];num[tmp]++;}}for(int i=0;i<anscount;i++){ansPeo[i]=peo[ans[i]];}sort(ansPeo,ansPeo+anscount);printf("%d\n",anscount);for(int i=0;i<anscount;i++){int tmpID=ansPeo[i].id;printf("%04d %d %.3lf %.3lf\n",tmpID,num[tmpID],ansPeo[i].mestate/num[tmpID],ansPeo[i].area/num[tmpID]);}return 0;
}

这篇关于【PAT】1114. Family Property (25)【并查集、结构体排序】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！