PAT Advanced 1114 Family Property

Overview

PAT Advanced 1114 Family Property tests Union-Find algorithm and assoicates each Disjoint-set with real estate information and test to calculate average stats.

PAT Advenced 1114 Family Property

This time, you are supposed to help us collect the data for family-owned property. Given each person’s family memb, 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 M_estate 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; M_estate 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 AVG_sets AVG_area

where ID is the smallest ID in the family; M is the total number of family memb; 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.

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

PAT Advenced 1114 Family Property Solution

For each ID, we make the disjoint set based on its parents information and children information, assoicate each ID with it’s family member in a set, and real estate info as well, after finish reading, go through all the IDs and find each’s ID’s disjoint set, each disjoint set (Family) should have its memb total number of real estate and total area, and calclute the average stats based on that.

The following is the C++ source code that could be accepted by PAT OJ to pass this PAT Advenced 1114 Family Property:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <cstdio>     
#include <algorithm>    

using std::vector;
using std::set;
using std::map;
using std::cin;
using std::cout;
using std::fill;

struct FR {
	int minID;
	double ts;
	double ta;
	set<int> memb;

	bool operator<(const FR& rhs) const {
		if (ta * rhs.memb.size() == rhs.ta * memb.size()) {
			return minID < rhs.minID;
		}
		return ta / memb.size() > rhs.ta / rhs.memb.size();
	}
};

map<int, FR> results;

class DS {
private:
	vector<int> p; 
public:
	int find(int i) {
		return p[i] == i ? i : (p[i] = find(p[i]));
	}

	void setUnion(int i, int j) {
		p[find(i)] = p[find(j)];
	}

	bool isUnion(int i, int j) {
		return find(i) == find(j);
	}
	DS(int n) {
		p.resize(n);
		for (int i = 0; i < n; ++i) {
			p[i] = i;
		}
	}
};

vector<int> estateSets;
vector<long> estateArea;
vector<int> ids;
vector<set<int> > memb;

int main() {
	DS ds(10001);

	int n, id, f, m, k, c, s, a;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		set<int> mm;
		cin >> id >> f >> m >> k;
		mm.insert(id);
		if (f >= 0) {
			ds.setUnion(id, f);
			mm.insert(f);
		}
		if (m >= 0) {
			ds.setUnion(id, m);
			mm.insert(m);
		}
		for (int j = 0; j < k; ++j) {
			cin >> c;
			ds.setUnion(id, c);
			mm.insert(c);
		}
		cin >> s >> a;
		ids.push_back(id);
		estateSets.push_back(s);
		estateArea.push_back(a);
		memb.push_back(mm);
	}

	for (int i = 0; i < n; ++i) {
		int id = ids[i];
		int root = ds.find(id);

		if (results.find(root) == results.end()) {
			FR r;
			r.minID = *std::min_element(memb[i].begin(), memb[i].end());
			r.ta = estateArea[i];
			r.ts = estateSets[i];
			r.memb.insert(memb[i].begin(), memb[i].end());
			results[root] = r;
		} else {
			FR& ff = results[root];
			ff.minID = std::min(ff.minID, *std::min_element(memb[i].begin(), memb[i].end()));
			ff.memb.insert(memb[i].begin(), memb[i].end());
			ff.ta += estateArea[i];
			ff.ts += estateSets[i];
		}
	}

	vector<FR> list;
	for (const auto & ele : results) {
		list.push_back(ele.second);
	}
	std::sort(list.begin(), list.end());

	printf("%d\n", list.size());
	for (const auto & ele : list) {
		printf("%.4d %d %.3lf %.3lf\n", ele.minID, ele.memb.size(), ele.ts / ele.memb.size(), ele.ta / ele.memb.size());
	}
	return 0;
}

Summary

PAT Advanced 1114 Family Property tests Union-Find algorithm and assoicates each Disjoint-set with real estate information and test to calculate average stats.

Written on November 19, 2016