(PAT 1114) Family Property (并查集)

刺骨的言语ヽ痛彻心扉 2022-04-23 09:16 153阅读 0赞

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 Child1⋯Childk 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; Childi'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.

### 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` AVGsets AVGarea

where `ID` is the smallest ID in the family; `M` is the total number of family members; AVGsets is the average number of sets of their real estate; and AVGarea 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.

### 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

解题思路:

给定每个人的家庭成员和其自己名下的房产，请你统计出每个家庭的人口数、人均房产面积及房产套数。首先在第一行输出家庭个数（所有有亲属关系的人都属于同一个家庭）。随后按下列格式输出每个家庭的信息：家庭成员的最小编号 家庭人口数 人均房产套数 人均房产面积。其中人均值要求保留小数点后3位。家庭信息首先按人均面积降序输出，若有并列，则按成员编号的升序输出。  
有几个家庭用并查集来做,先把并查集建立好,然后建立3张哈希表,把每个用户的财产,面积读入到哈希表中,然后遍历并查集,把每个成员的财产面积值加到根结点哈希表中的财产面积值

### 最后根节点的数目就是家庭的数目,输出根节点财产面积值/家庭成员人数 ###

#include <iostream>
    #include <algorithm>
    #include <set>
    #include <vector>
    using namespace std;
    const int MAXN = 10000;
    int FFather[MAXN];
    //哈希表,用来存储财产
    double Fstates[MAXN];
    double Fareas[MAXN];
    int Fmembers[MAXN];
    bool cmp(int a, int b) {
    	if (Fareas[a] / Fmembers[a] != Fareas[b] / Fmembers[b]) return Fareas[a] / Fmembers[a] > Fareas[b] / Fmembers[b];
    	else {
    		return a < b;
    	}
    }
    int Ffind_set(int node) {
    	if (FFather[node] != node) {
    		FFather[node] = Ffind_set(FFather[node]);
    	}
    	return FFather[node];
    }
    void FMerge(int a, int b) {
    	int ancestorA = Ffind_set(a);
    	int ancestorB = Ffind_set(b);
    	if (ancestorA != ancestorB) {
    		if (ancestorA < ancestorB) {
    			FFather[ancestorB] = ancestorA;
    		}
    		else {
    			FFather[ancestorA] = ancestorB;
    		}
    	}
    }
    int main() {
    	set<int> family,members;
    	vector<int> familyvec;
    	for (int i = 0; i < MAXN; ++i) {
    		FFather[i] = i;
    		Fareas[i] = 0;
    		Fstates[i] = 0;
    		Fmembers[i] = 1;
    	}
    	int N;
    	cin >> N;
    	for (int i = 0; i < N; ++i) {
    		int mroot, mfather, mmother,K,mstate,marea;
    		cin >> mroot >> mfather >> mmother >> K;
    		members.insert(mroot);
    		if (mfather != -1) { FMerge(mroot, mfather); members.insert(mfather); }
    		if (mmother != -1) { FMerge(mroot, mmother); members.insert(mmother); }
    		for (int j = 0; j < K; ++j) {
    			int sons;
    			cin >> sons;
    			FMerge(mroot, sons);
    			members.insert(sons);
    		}
    		cin >> mstate >> marea;
    		Fstates[mroot] = (double)mstate;
    		Fareas[mroot] = (double)marea;
    	}
    	for (auto itr = members.begin(); itr != members.end(); ++itr) {
    		int fHead = Ffind_set(*itr);
    		family.insert(fHead);
    		if (*itr != fHead) {
    			Fstates[fHead] += Fstates[*itr];
    			Fareas[fHead] += Fareas[*itr];
    			Fmembers[fHead]++;
    		}
    	}
    	for (auto itr = family.begin(); itr != family.end(); ++itr) {
    		familyvec.push_back(*itr);
    	}
    	sort(familyvec.begin(), familyvec.end(), cmp);
    	cout << familyvec.size() << endl;
    	for (auto itr = familyvec.begin(); itr != familyvec.end(); ++itr) {
    		printf("%04d %d %.3f %.3f\n", *itr, Fmembers[*itr], Fstates[*itr] / Fmembers[*itr], Fareas[*itr] / Fmembers[*itr]);
    	}
    	system("PAUSE");
    	return 0;
    }