PAT A1114 Family Property

用并查集处理每个家庭的信息,注意标记~

#include<bits/stdc++.h>
using namespace std;
const int maxn=;
bool visit[maxn]={false};
int N;
struct node {
int id;
int child[];
double num;
double area;
}Node[maxn];
struct family {
int id;
double num;
double area;
int renshu;
}f[maxn];
int father[maxn];
void init () {
for (int i=;i<maxn;i++)
father[i]=i;
}
int findfather (int x) {
int a=x;
while (x!=father[x])
x=father[x];
while (a!=father[a]) {
int z=a;
a=father[a];
father[z]=x;
}
return x;
}
void Union (int a,int b) {
int faA=findfather (a);
int faB=findfather (b);
if (faA<faB) father[faB]=faA;
else father[faA]=faB;
};
bool cmp (family a,family b) {
if (a.area!=b.area) return a.area>b.area;
else return a.id<b.id;
}
int main () {
scanf ("%d",&N);
int id,fatherid,motherid,k;
double num,area;
init ();
for (int i=;i<N;i++) {
scanf ("%d %d %d %d",&id,&fatherid,&motherid,&k);
Node[i].id=id;
visit[id]=true;
if (fatherid!=-) {
visit[fatherid]=true;
Union (id,fatherid);
}
if (motherid!=-) {
visit[motherid]=true;
Union (id,motherid);
}
for (int j=;j<k;j++) {
scanf ("%d",&Node[i].child[j]);
visit[Node[i].child[j]]=true;
Union (id,Node[i].child[j]);
}
scanf ("%lf %lf",&Node[i].num,&Node[i].area);
}
for (int i=;i<N;i++) {
f[findfather(Node[i].id)].area+=Node[i].area;
f[findfather(Node[i].id)].num+=Node[i].num;
}
int ans=;
for (int i=;i<maxn;i++) {
if (visit[i]==true) {
f[findfather(i)].renshu++;
f[findfather(i)].id=findfather(i);
}
}
for (int i=;i<maxn;i++)
if (f[i].renshu!=) {
ans++;
f[i].area/=f[i].renshu;
f[i].num/=f[i].renshu;
}
sort (f,f+maxn,cmp);
printf ("%d\n",ans);
for (int i=;i<ans;i++) {
printf ("%04d %d %.3f %.3f\n",f[i].id,f[i].renshu,f[i].num,f[i].area);
}
return ;
}
上一篇:bzoj2500幸福的道路 树形dp+单调队列


下一篇:PAT (Advanced Level) Practice(更新中)