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 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 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.
Sample Input:
|
1 2 3 4 5 6 7 8 9 10 11 |
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:
|
1 2 3 4 |
3 8888 1 1.000 1000.000 0001 15 0.600 100.000 5551 4 0.750 100.000 |
用 disjoint set 来确定家庭……
child 和 parent 的 id 可能不在给出的人中，且没有资产
代码如下：
|
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 120 121 122 123 124 125 126 127 128 129 130 131 132 133 |
#include<stdio.h> #include<stdlib.h> typedef struct info_ { int related; int m_estate; int area; int smallest_id; } info; info set[10000]; int find(int index) { int root,temp=index,min=index; while(set[temp].related>-1) { temp=set[temp].related; if(temp<min) { min=temp; } } root=temp; while(set[temp].related>-1) { index=temp; temp=set[temp].related; set[index].related=root; } if(min<set[root].smallest_id) { set[root].smallest_id=min; } return root; } int set_union(int a,int b) { a=find(a); b=find(b); if(a==b) { return 0; } if(set[a].related<set[b].related) { set[a].related+=set[b].related; set[b].related=a; if(set[a].smallest_id>set[b].smallest_id) { set[a].smallest_id=set[b].smallest_id; } } else { set[b].related+=set[a].related; set[a].related=b; if(set[b].smallest_id>set[a].smallest_id) { set[b].smallest_id=set[a].smallest_id; } } return 1; } int compare(const void *a,const void *b) { if(set[*(int *)a].area*(-set[*(int *)b].related)==set[*(int *)b].area*(-set[*(int *)a].related)) { return set[*(int *)a].smallest_id-set[*(int *)b].smallest_id; } return set[*(int *)b].area*(-set[*(int *)a].related)-set[*(int *)a].area*(-set[*(int *)b].related); } int main() { int i,j,n,id,temp,father,mother,k,child,m_estate,area,*list,*result,offset=0; info *members; for(i=0;i<10000;i++) { set[i].related=-1; set[i].area=0; set[i].m_estate=0; set[i].smallest_id=10000; } scanf("%d",&n); list=(int *)malloc(n*sizeof(int)); result=(int *)malloc(n*sizeof(int)); for(i=0;i<n;i++) { scanf("%d%d%d%d",&id,&father,&mother,&k); list[i]=id; if(father!=-1) { set_union(id,father); } if(mother!=-1) { set_union(id,mother); } for(j=0;j<k;j++) { scanf("%d",&child); set_union(id,child); } scanf("%d%d",&m_estate,&area); set[id].m_estate=m_estate; set[id].area=area; } for(i=0;i<n;i++) { id=list[i]; temp=find(id); for(j=0;j<offset;j++) { if(result[j]==temp) { break; } } if(j==offset) { result[offset++]=temp; } if(temp!=id) { set[temp].m_estate+=set[id].m_estate; set[temp].area+=set[id].area; } } qsort(result,offset,sizeof(int),compare); printf("%d\n",offset); for(i=0;i<offset;i++) { printf("%04d %d %.3lf %.3lf\n",set[result[i]].smallest_id,-set[result[i]].related,set[result[i]].m_estate/(double)(-set[result[i]].related),set[result[i]].area/(double)(-set[result[i]].related)); } } |