PAT 1114

#include<cstdio> #include<cstring> #include<vector> #include<iostream> #include<algorithm> #include<set> #include<stdio.h> using namespace std; const int maxn = 10100; int e[maxn] = { 0 }, a[maxn] = {0}; int id, fa, mo, k, child,estate,area; int n; int father[maxn]; struct Node { int num; int id; double estate, area; }node[maxn],root[maxn]; vector<Node> ans; void init() { for (int i=0;i<maxn;i++) { father[i] = i; node[i].area = node[i].estate = node[i].num = 0; root[i].area = root[i].estate = root[i].num = 0; } return; } int findfather(int a) { int b, temp; b = a; while(a!=father[a]) { a = father[a]; } while (b != a) { temp = father[b]; father[b] = a; b = temp; } return a; } void _union(int a,int b) { if (findfather(a)!=findfather(b)) { if (findfather(a) < findfather(b)) father[findfather(b)] = findfather(a); else father[findfather(a)] = findfather(b); } return; } bool cmp(Node a,Node b) { if (a.area != b.area) return a.area > b.area; else return a.id < b.id; } bool flag[maxn] = { false }; int main() { //freopen("input.txt","r",stdin); // freopen("con", "r", stdin); init(); cin >> n; for (int i=0;i<n;i++) { cin >> id >> fa >> mo; if (flag[id] == false) { node[id].num++; flag[id] = true; } if (fa != -1) { _union(id, fa); if (flag[fa] == false) { node[id].num++; flag[fa] = true; } } if (mo != -1) { _union(id, mo); if (flag[mo] == false) { node[id].num++; flag[mo] = true; } } cin >> k; for (int j=0;j<k;j++) { cin >> child; _union(id,child); if (flag[child] == false) { node[id].num++; flag[child] = true; } } cin >> estate >> area; node[id].estate = estate; node[id].area = area; } for (int i=0;i<maxn;i++) { if (node[i].estate != 0 || node[i].area != 0 || node[i].num != 0) { root[findfather(i)].num += node[i].num; root[findfather(i)].estate += node[i].estate; root[findfather(i)].area += node[i].area; root[findfather(i)].id = findfather(i); } } for (int i=0;i<maxn;i++) { if (root[i].num != 0) ans.push_back(root[i]); } cout <<ans.size()<<endl; for (int i=0;i<ans.size();i++) { ans[i].estate /= ans[i].num; ans[i].area /= ans[i].num; } sort(ans.begin(), ans.end(), cmp); for (int i=0;i<ans.size();i++) { printf("d %d %.3lf %.3lf\n",ans[i].id,ans[i].num,ans[i].estate,ans[i].area); } system("pause"); return 0; }