L2-007. 家庭房产
参考博客
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <algorithm>
5 #include <vector>
6 #include <queue>
7 #include <set>
8 #include <map>
9 #include <string>
10 #include <cmath>
11 #include <cstdlib>
12 #include <ctime>
13 #include <stack>
14 using namespace std;
15 const int maxn=11000;
16 int vis[maxn],m[maxn];
17 int p[10010];
18 struct node{
19 double ans1,ans2;
20 int id,num;
21 };
22
23 bool cmp(node a,node b){
24 if(a.ans2!=b.ans2)
25 return a.ans2>b.ans2;
26 return a.id<b.id;
27 }
28
29 void init(){
30
31 for(int i=0;i<=10000;i++)
32 p[i]=i;
33 }
34
35 int find(int x)
36 {
37 if(x==p[x])
38 return x;
39 else
40 return p[x]=find(p[x]);
41 }
42
43 void un(int a,int b){
44 int x=find(a);
45 int y=find(b);
46 if(x!=y){
47 if(x>y)
48 p[x]=y;
49 else
50 p[y]=x;
51 }
52 }
53
54
55 int main()
56 {
57 //freopen("in.txt","r",stdin);
58 //freopen("out.txt","w",stdout);
59 int i,j,n;
60 node a[10005];
61 node b[10005];
62 node mul[10005];
63 cin>>n;
64 init();
65 memset(vis,0,sizeof(vis));
66 memset(m,0,sizeof(m));
67 for(i=0;i<n;i++)
68 {
69 int p1,p2,d,k;
70 cin>>a[i].id>>p1>>p2;
71 vis[a[i].id]=1;
72 if(p1!=-1){
73 un(p1,a[i].id);
74 vis[p1]=1;
75 }
76 if(p2!=-1){
77 un(p2,a[i].id);
78 vis[p2]=1;
79 }
80 cin>>k;
81 while(k--){
82 cin>>d;
83 if(d!=-1){
84 un(a[i].id,d);
85 vis[d]=1;
86 }
87 }
88 cin>>a[i].ans1>>a[i].ans2;
89 }
90 for(i=0;i<n;i++){
91 int id=find(a[i].id);
92 mul[id].id=id;
93 mul[id].ans1+=a[i].ans1;
94 mul[id].ans2+=a[i].ans2;
95 }
96 for(i=0; i<10000; i++)
97 if(vis[i])
98 { mul[find(i)].num++;
99 }
100 int cnt=0;
101 for(i=0;i<10000;i++){
102 if(vis[i]){
103 int id=find(i);
104 if(!m[id]){
105 m[id]=1;
106 double x=double(mul[id].num);
107 b[cnt].ans1=mul[id].ans1*1.0/x;
108 b[cnt].ans2=mul[id].ans2*1.0/x;
109 b[cnt].id=id;
110 b[cnt++].num=int(x);
111 }
112 }
113 }
114 cout<<cnt<<endl;
115 sort(b,b+cnt,cmp);
116 for(i=0;i<cnt;i++)
117 printf("%04d %d %.3lf %.3lf
",b[i].id,b[i].num,b[i].ans1,b[i].ans2);
118 return 0;
119 }