Home PAT 1114 Family Property
Post
Cancel

PAT 1114 Family Property

Link

这题坑的地方在于, 你和你的 siblings 有着相同的 parents, 但是输入中没有 parents 节点, 因此你不知道你们其实是 siblings 😓… 于是就把原本是一个 family 的给拆了 hhh

解决方法: 对于孩子而言, 不管是 dad 还是 mom, 也不管有无重复, 全都放到 parents 数组中; 对于父母而言, 不管孩子有无重复, 全都放到 children 数组中. 因为 DFS 时会对 ID 的访问进行记录.

最后就是在对 ans 排序的时候 (看下面代码中的 node2 结构体), 不要比较 double, 而是写成整数乘法的形式. 这个我一开始就注意到了, 所以不知道写成 double 然后用 epsilon 比较能不能 AC. 下次可以试一试.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
using namespace std;
int n;
struct node1{
    int id,m=0,area=0;
    vector<int>parents,children;
}person[10010];
struct node2{
    int id,num,sets,area;
    bool operator<(node2 x)const{
        long long t1=area*x.num,t2=x.area*num;
        if(t1!=t2) return t1>t2;
        return id<x.id;
    }
};
vector<node2>ans;
int idmap[1010];
bool v[10010];
void DFS(int cur,int &minID,int &sets,int &area,int &num){
    minID=min(minID,cur);
    sets+=person[cur].m;
    area+=person[cur].area;
    num++;
    for(int i=0;i<person[cur].parents.size();++i)
        if(!v[person[cur].parents[i]]){
            v[person[cur].parents[i]]=true;
            DFS(person[cur].parents[i],minID,sets,area,num);
        }
    for(int i=0;i<person[cur].children.size();++i)
        if(!v[person[cur].children[i]]){
            v[person[cur].children[i]]=true;
            DFS(person[cur].children[i],minID,sets,area,num);
        }
}
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        int id,dad,mom,k,child;
        scanf("%d%d%d%d",&id,&dad,&mom,&k);
        idmap[i]=id;
        person[id].id=id;
        if(dad!=-1){
            person[dad].children.push_back(id);
            person[id].parents.push_back(dad);
        }
        if(mom!=-1){
            person[mom].children.push_back(id);
            person[id].parents.push_back(mom);
        }
        for(int j=1;j<=k;++j){
            scanf("%d",&child);
            person[id].children.push_back(child);
            person[child].parents.push_back(id);
        }
        scanf("%d%d",&person[id].m,&person[id].area);
    }
    for(int i=1;i<=n;++i)
        if(!v[idmap[i]]){
            int sets=0,area=0,minID=idmap[i],num=0;
            v[idmap[i]]=true;
            DFS(idmap[i],minID,sets,area,num);
            ans.push_back({minID,num,sets,area});
        }
    sort(ans.begin(),ans.end());
    printf("%d\n",ans.size());
    for(int i=0;i<ans.size();++i)
        printf("%04d %d %.3lf %.3lf\n",ans[i].id,ans[i].num,double(double(ans[i].sets)*1.0/ans[i].num),double(double(ans[i].area)*1.0/ans[i].num));
    return 0;
}
This post is licensed under CC BY 4.0 by the author.