PAT1114 Family Property
原题
题目大意
题目中给定了一些人的家庭情况及房产情况，要求输出：
- 家庭的个数（祖先后代全算一个家庭）
- 按照一定次序输出 ID 该家庭里人数 平均房子栋数 平均房子面积
此处ID为该家庭里的最小ID
思路
该题考察的是并查集。
- 如果要按照一定规则输出的话应该需要构建一个结构体来进行排序
- 因为是输出家庭里的最小ID，所以在合并的时候可以让那个父亲ID大的指向小的
- 关于家庭人数及平均房产等，在结构体里我们可以设定属性为家庭人数，总房产栋数，总面积，最后再求平均。而结构体值的变化应该在初始化及合并的时候进行，可以用一个set集合存储现在有的家庭，在合并的时候删除其一，同时也可以实现排序。
代码
尝试：
#include<iostream>
#include<algorithm>
#include<set>
#include<vector>
#include<cmath>
#include<map>
using namespace std;
int fa[10010]={0};
bool isRoot[10010]={false};
set<int> snumber;
struct family{
int smallid,sumpeople;
double sumset,sumarea;
friend bool operator < (const family& a, const family& b)
{
return a.sumarea/a.sumpeople==b.sumarea/b.sumpeople?a.smallid<b.smallid:a.sumarea/a.sumpeople>b.sumarea;
}
};
int findfather(int v){
if(v==fa[v]) return v;
else{
int f=findfather(fa[v]);
fa[v]=f;
return f;
}
}
void Union(int a,int b){
int faA=findfather(a);
int faB=findfather(b);
if(faA<faB){
for(auto it=snumber.begin();it!=snumber.end();it++) if(fa[*it]==fa[b]) fa[*it]=faA;
fa[b]=faA;
}
else{
for(auto it=snumber.begin();it!=snumber.end();it++) if(fa[*it]==fa[a]) fa[*it]=faB;
fa[a]=faB;
}
}
bool cmp(family a,family b){
return a.sumarea/a.sumpeople==b.sumarea/b.sumpeople?a.smallid<b.smallid:a.sumarea/a.sumpeople>b.sumarea/b.sumpeople;
}
int main(){
int n;
cin>>n;
int id,father,mom,sonnum;
double mset,area;
vector<family> v;
map<int,family> m;
for(int i=0;i<n;i++){
set<family> s;
cin>>id>>father>>mom>>sonnum;
int addnumber=0;
// cout<<fa[id]<<endl;
if(fa[id]==0){
fa[id]=id;
}
else{
s.insert(m[fa[id]]);
//cout<<1<<endl;
}
if(snumber.find(id)==snumber.end()) addnumber++;
snumber.insert(id);
if(father!=-1){
// cout<<"!"<<endl;
if(snumber.find(father)==snumber.end()) addnumber++;
if(fa[father]==0){
fa[father]=father;
}
else{
cout<<s.size()<<endl;
s.insert(m[fa[father]]);
// cout<<2<<" "<<m[fa[father]].smallid<<" "<<s.size()<<endl;
}
snumber.insert(father);
}
if(mom!=-1){
if(snumber.find(mom)==snumber.end()) addnumber++;
if(fa[mom]==0){
fa[mom]=mom;
}
else{
s.insert(m[fa[mom]]);
// cout<<3<<" "<<m[fa[mom]].smallid<<" "<<s.size()<<endl;
}
snumber.insert(mom);
}
int sid=fa[id];
//cout<<sid<<endl;
//cout<<"father- id:"<<fa[id]<<" father:"<<fa[father]<<" mom:"<<fa[mom]<<" ";
vector<int> sonv(sonnum);
for(int i=0;i<sonnum;i++){
cin>>sonv[i];
if(sonv[i]<sid) sid=sonv[i];
if(snumber.find(sonv[i])==snumber.end()) addnumber++;
if(fa[sonv[i]]==0){
fa[sonv[i]]=sonv[i];
}
else{
s.insert(m[fa[sonv[i]]]);
//cout<<4<<endl;
}
snumber.insert(sonv[i]);
//cout<<sonv[i]<<":"<<fa[sonv[i]]<<" ";
}
cout<<endl;
cin>>mset>>area;
double addset=mset,addarea=area;
for(auto it=s.begin();it!=s.end();it++){
cout<<it->smallid<<endl;
addset+=it->sumset;
addarea+=it->sumarea;
addnumber+=it->sumpeople;
//cout<<5<<endl;
}
//cout<<addset<<" "<<addarea<<" "<<addnumber<<endl;
if(father!=-1&&findfather(father)) sid=min(sid,fa[father]);
if(mom!=-1&&findfather(mom)) sid=min(sid,fa[mom]);
Union(sid,id);
if(father!=-1) Union(father,sid);
if(mom!=-1) Union(mom,sid);
for(int i=0;i<sonnum;i++) Union(sonv[i],sid);
//family f={sid,addnumber+m[sid].sumpeople,mset+m[sid].sumset,area+m[sid].sumarea};
family f={sid,addnumber,addset,addarea};
m[sid]=f;
//cout<<sid<<": "<<m[sid].sumpeople<<" "<<m[sid].sumset<<" "<<m[sid].sumarea<<endl;
}
for(auto it=snumber.begin();it!=snumber.end();it++){
isRoot[findfather(*it)]=true;
//cout<<*it<<" "<<findfather(*it)<<endl;
}
int ans=0;
for(auto it=snumber.begin();it!=snumber.end();it++){
if(isRoot[*it]){
v.push_back(m[*it]);
}
// cout<<*it<<" "<<isRoot[*it]<<" "<<m[*it].smallid<<" "<<m[*it].sumpeople<<" "<<m[*it].sumset<<" "<<m[*it].sumarea<<endl;
}
printf("%d\n",v.size());
sort(v.begin(),v.end(),cmp);
for(int i=0;i<v.size();i++){
printf("%04d %d %.3f %.3f\n",v[i].smallid,v[i].sumpeople,v[i].sumset/v[i].sumpeople,v[i].sumarea/v[i].sumpeople);
}
return 0;
}
以上代码没有解决这个问题。
（稍后继续修改更新）
小收获
尝试的代码其实并没有解决这个问题。暂时没调试出来的问题是：
（此处读者看可能有些疑惑。可以对照着我//后的注释来看，这里我稍微解释一下）
（-0-|||之所以这样输出是因为之前点devc++的调试一直有问题，但刚刚参考完其他博文的步骤 好像又可以了？）
第四行的1代表现在s集合里有一个元素，但经过第五行（判断并加入m[fa[father]]）大小还是1，第六行也还是1。 试了很久也暂时没发现是哪里出了问题，因为m[fa[id]]和m[fa[father]]不同，不应该会被消除重复值，大小应该为2.
虽然用这种方法花了一个下午还没有解出来，但是有很多收获：
- set类型用结构体需要重载＜
- 更加熟悉并查集的使用
- 此类代码的运用：
for(auto it=snumber.begin();it!=snumber.end();it++){
isRoot[findfather(*it)]=true;
}
- 浮点数位数控制
printf(%m.nf) 表示打印至少m个字符宽度(包括整数、小数点和小数部分的位数)，n位小数
for(int i=0;i<v.size();i++){
printf("%04d %d %.3f %.3f\n",v[i].smallid,v[i].sumpeople,v[i].sumset/v[i].sumpeople,v[i].sumarea/v[i].sumpeople);
}