PAT A1114 Family Property

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

• 思路 1：并查集（带计数版）见A1118 Birds and Forest

1. 输入数据：三个数组input、f_num、f_erea：inputId[i]代表：第i组家庭的首ID；f_num[i]代表：第i组家庭的房产个数；f_area[i]代表：第i组家庭的房产面积
2. 整合数据：从头遍历这几组数据：
     2-1 将每个小家庭的房产数和房产面积累加如大家庭上（大家庭的id为find(inputId[i])；因为Union函数中每次都选id小的做为根：rx<ry，所以这个id一定是整个家庭里最小的）
     2-2 写入家庭总人数，即-father[find(id)]
     2-3 把这个大家庭标记上fam[id].flag = true；
3. 先按flag位排序将无效数据筛选掉，再进行下一步处理
4. 处理数据：求出每个大家庭的平均房产、平均房产面积
5. 然后按题目要求：房产面积降序，id升序 排序、输出即可

• code 1:

#include <bits/stdc++.h> 
using namespace std;
const int maxn = 10100;
int father[maxn];
struct family{
	int id, memNum, num, area;
	double avNum, avArea;
	bool flag;
	family(){id=maxn;}
}fam[maxn]; 
int find(int x){
	while(father[x] >= 0){
		x = father[x];
	}
	return x;
}
void Union(int x, int y){
	int rx = find(x);
	int ry = find(y);
	if(rx != ry){
		if(rx > ry){
			father[ry]+=father[rx];
			father[rx]=ry;
		}
		else{
			father[rx]+=father[ry];
			father[ry]=rx;
		}	
	}
}
bool cmp(family a, family b){
	return a.flag > b.flag;
}
bool cmp1(family a, family b){
	return a.avArea != b.avArea ? a.avArea > b.avArea : a.id < b.id; 
}
int inputId[maxn], f_num[maxn], f_area[maxn];
int main(){
	int n; 
	scanf("%d", &n);
	fill(father, father+maxn, -1);
	for(int i = 0; i < n; ++i){	//1
		int fa, ma, nc, tmpc;
		scanf("%d %d %d %d", &inputId[i], &fa, &ma, &nc);
		if(fa != -1) Union(inputId[i], fa);
		if(ma != -1) Union(inputId[i], ma);
		for(int j = 0; j < nc; ++j){
			scanf("%d", &tmpc);
			Union(inputId[i], tmpc);
		}
		scanf("%d %d", &f_num[i], &f_area[i]);
	}
	for(int i = 0; i < n; ++i){	//2
		int id = find(inputId[i]);
		fam[id].id = id;
		fam[id].num += f_num[i];
		fam[id].area += f_area[i];
		fam[id].memNum = -father[id];
		fam[id].flag = true;
	}
	sort(fam, fam+maxn, cmp);	//3
 	int cnt = 0;	
	for(int i = 0; i < n && fam[i].flag; ++i){	//4 
		fam[i].avNum = (double)fam[i].num / fam[i].memNum;
		fam[i].avArea = (double)fam[i].area / fam[i].memNum;
		cnt++;
	}
	sort(fam, fam+maxn, cmp1); //5 
	printf("%d\n", cnt);
	for(int i = 0; i < cnt; ++i){
		printf("%04d %d %.3f %.3f\n", fam[i].id, fam[i].memNum, fam[i].avNum, fam[i].avArea);
	}
	return 0;
}