L2-007 家庭房产
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
using namespace std;
struct fam
{
int id,num;
double avg1,avg2;
};
const int N = 10000;
int father[N];
int root[N];
bool cmp(struct fam a,struct fam b)
{
if(a.avg2 != b.avg2)
return a.avg2 > b.avg2;
else
return a.id < b.id;
}
void Init()
{
for(int i = 0; i < N; i++)
{
father[i] = i;
}
}
int Find(int a)
{
while(father[a] != a)
a = father[a];
return a;
}
void Union(int a,int b)
{
int fa = Find(a);
int fb = Find(b);
if(fa > fb)
father[fa] = fb;
else if(fa < fb)
father[fb] = fa;
}
int main()
{
int n;
scanf("%d",&n);
Init();
map<int,int> mp1;
map<int,int> mp2;
map<int,int> mp3;
map<int,int> mp4;
map<int,int> mp5;
set<int> st;
for(int i = 0; i < n; i++)
{
int id,dad,mom,k;
scanf("%d%d%d%d",&id,&dad,&mom,&k);
st.insert(id);
if(dad != -1)
{
st.insert(dad);
Union(id,dad);
}
if(mom != -1)
{
st.insert(mom);
Union(id,mom);
}
for(int j = 0; j < k; j++)
{
int child;
scanf("%d",&child);
Union(id,child);
st.insert(child);
}
int house,area;
scanf("%d%d",&house,&area);
mp1[id] = house;
mp2[id] = area;
}
set<int>::iterator it;
int count = 0;
for(it = st.begin(); it != st.end(); it++)
{
int temp = Find(*it);
if(root[temp] == 0)
count++;
root[temp]++;
if(mp1[*it])
{
mp3[temp] += mp1[*it];
mp4[temp] += mp2[*it];
}
}
vector<fam> v(count);
int t = 0;
for(int i = 0; i < N; i++)
{
if(root[i])
{
v[t].id = i;
v[t].num = root[i];
v[t].avg1 = mp3[i] * 1.0 / root[i];
v[t].avg2 = mp4[i] * 1.0 / root[i];
t++;
}
}
sort(v.begin(),v.end(),cmp);
printf("%d\n",count);
for(int i = 0; i < count; i++)
{
printf("%04d %d %.3lf %.3lf\n",v[i].