1114 Family Property

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.

知识点：并查集

注意并查集的写法

 #include <iostream>

 #include <algorithm>

 #include <vector>

 using namespace std;

 const int maxn = ;

 int ManSet[maxn];

 int Property[maxn][];

 int used[maxn];

 //set<int>

 bool cmp(int a,int b){

     if(Property[a][]/(-ManSet[a]+0.0)==Property[b][]/(-ManSet[b]+0.0)){

         return a<b;

     }

     return Property[a][]/(-ManSet[a]+0.0)>Property[b][]/(-ManSet[b]+0.0);

 }

 int Find(int v){

     if(ManSet[v]<=-){

         return v;

     }

     return ManSet[v] = Find(ManSet[v]);

 }

 int Unite(int n1, int n2){

     if(n1<n2){

         ManSet[n1] += ManSet[n2];

         ManSet[n2] = n1;

         return n1;

     }else{

         ManSet[n2] += ManSet[n1];

         ManSet[n1] = n2;

         return n2;

     }

 }

 int main(int argc, char *argv[]) {

     int n;

     fill(ManSet,ManSet+maxn,-);

     fill(Property[],Property[]+maxn*,);

     fill(used,used+maxn,);

     scanf("%d",&n);

     int man,fa,mo,k,tmpc,m,area;

     for(int i=;i<n;i++){

         //printf("\n");

         scanf("%d %d %d",&man,&fa,&mo);

         used[man] = used[fa] = used[mo] = ;

         //printf("\n. %d %d,%d\n",Find(man),i,n);

         man = Find(man); //printf("%d  ",man);

         if(fa!=-){

             fa = Find(fa);

             if(fa!=man){

                 man = Unite(man,fa); //printf("%d ",man);

             }

         }

         man = Find(man);

         if(mo!=-){

             mo = Find(mo);

             if(mo!=man){

                 man = Unite(man,mo);//printf("%d ",man);

             }

         }

         scanf("%d",&k);

         for(int j=;j<k;j++){

             scanf("%d",&tmpc);

             used[tmpc] = ;

             tmpc = Find(tmpc);

             man = Find(man);

             if(man!=tmpc){

                 man = Unite(man,tmpc);//printf("%d ",man);

             }

         }

         scanf("%d %d",&m,&area);

         Property[man][] += m;

         Property[man][] += area;

     }

     for(int i=;i<maxn;i++){

         if(used[i]==&&ManSet[i]>&&Property[i][]>){

             int an = Find(i);

             Property[an][]+=Property[i][];

             Property[an][]+=Property[i][];

         }

     }

     vector<int> list;

     for(int i=;i<maxn;i++){

         if(used[i]==&&ManSet[i]<){

             list.push_back(i);

             //printf("%04d %d %.3f %.3f\n",i,(-ManSet[i]),Property[i][0]/(-ManSet[i]+0.0),Property[i][1]/(-ManSet[i]+0.0));

         }

     }

     sort(list.begin(), list.end(), cmp);

     printf("%d\n",list.size());

     for(int i=;i<list.size();i++){

         printf("%04d %d %.3f %.3f\n",list[i],(-ManSet[list[i]]),Property[list[i]][]/(-ManSet[list[i]]+0.0),Property[list[i]][]/(-ManSet[list[i]]+0.0));

     }

 }

巴特西

1114 Family Property

Input Specification:

Output Specification:

最新文章

热门文章