【刷题-PAT】A1114 Family Property （25 分）

1114 Family Property （25 分）

This time, you are supposed to help us collect the data for family-owned property. Given each person's family members, and the estate（房产）info under his/her own name, we need to know the size of each family, and the average area and number of sets of their real estate.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤1000). Then N lines follow, each gives the infomation of a person who owns estate in the format:

ID Father Mother k child1 child2 ... childk M Area

where ID is a unique 4-digit identification number for each person; Father and Mother are the ID's of this person's parents (if a parent has passed away, -1 will be given instead); k (0≤k≤5) is the number of children of this person; Child**i's are the ID's of his/her children; Mestate is the total number of sets of the real estate under his/her name; and Area is the total area of his/her estate.

Output Specification:

For each case, first print in a line the number of families (all the people that are related directly or indirectly are considered in the same family). Then output the family info in the format:

\(ID M AVG_{sets} AVG_{area}\)

where ID is the smallest ID in the family; M is the total number of family members; AVGsets is the average number of sets of their real estate; and AVGarea is the average area. The average numbers must be accurate up to 3 decimal places. The families must be given in descending order of their average areas, and in ascending order of the ID's if there is a tie.

Sample Input:

10

6666 5551 5552 1 7777 1 100

1234 5678 9012 1 0002 2 300

8888 -1 -1 0 1 1000

2468 0001 0004 1 2222 1 500

7777 6666 -1 0 2 300

3721 -1 -1 1 2333 2 150

9012 -1 -1 3 1236 1235 1234 1 100

1235 5678 9012 0 1 50

2222 1236 2468 2 6661 6662 1 300

2333 -1 3721 3 6661 6662 6663 1 100

Sample Output:

3

8888 1 1.000 1000.000

0001 15 0.600 100.000

5551 4 0.750 100.000

分析：要将每个家庭的数据分离出来，使用并查集即可实现，数据处理上有两种方法：

1.先将录入的数据按照输入的形式存在数组中，录入的同时完成集合的合并，然后再从录入的数据中挑出需要的数据，最后对挑出的数据仓晒礼输出；

2.在录入的同时进行集合的合并，并将数据按照输出的格式存储，然后进行处理

#include<iostream>

#include<cstdio>

#include<vector>

#include<string>

#include<unordered_map>

#include<set>

#include<queue>

#include<algorithm>

#include<cmath>

using namespace std;

const int nmax = 10100;

int fath[nmax];

void init(){

    for(int i = 0; i < nmax; ++i)fath[i] = i;

}

int findF(int x){

    int z = x;

    while(x != fath[x])x = fath[x];

    while(z != fath[z]){

        int temp = fath[z];

        fath[z] = x;

        z = temp;

    }

    return x;

}

void Union(int a, int b){

    int fa = findF(a), fb = findF(b);

    if(fa < fb)fath[fb] = fa;

    else if(fa > fb)fath[fa] = fb;

}

struct node{

    int id, people;

    double num, area;

    bool flag = false;

    bool operator < (node &a)const{

        return area != a.area ? area > a.area : id < a.id;

    }

}ans[nmax];

struct data{

    int id, fid, mid, k;

    int child[6];

    int num, area;

}v[nmax];

bool vis[nmax] = {false};

int main(){

    #ifdef ONLINE_JUDGE

    #else

    freopen("input.txt", "r", stdin);

    #endif // ONLINE_JUDGE

    init();

    int N;

    scanf("%d", &N);

    //录入数据并合并，由于序号不连续，要标记哪些序号已经出现过

    for(int i = 0; i < N; ++i){

        int id, fid, mid, k;

        scanf("%d%d%d%d", &id, &fid, &mid, &k);

        v[id].id = id;

        v[id].fid = fid;

        v[id].mid = mid;

        v[id].k = k;

        vis[id] = true;

        if(fid != -1){

            Union(id, fid);

            vis[fid] = true;

        }

        if(mid != -1){

            Union(id, mid);

            vis[mid] = true;

        }

        for(int j = 0; j < k; ++j){

            scanf("%d", &v[id].child[j]);

            Union(id, v[id].child[j]);

            vis[v[id].child[j]] = true;

        }

        scanf("%d%d", &v[id].num, &v[id].area);

    }

    //统计并抽出需要的数据，用flag标记该根节点是否已经出现

    int cnt = 0;

    for(int i = 0; i < nmax; ++i){

        if(vis[i] == true){

            int index = findF(i);

            ans[index].id = index;

            ans[index].people++;

            ans[index].num += v[i].num;

            ans[index].area += v[i].area;

            if(ans[index].flag == false)cnt++;

            ans[index].flag = true;

        }

    }

    //处理

    for(int i = 0; i < nmax; ++i){

        if(ans[i].flag == true){

            ans[i].num /= ans[i].people;

            ans[i].area /= ans[i].people;

        }

    }

    //排序输出

    sort(ans, ans + nmax);

    printf("%d\n", cnt);

    for(int i = 0; i < cnt; ++i){

        printf("%04d %d %.3f %.3f\n", ans[i].id, ans[i].people, ans[i].num, ans[i].area);

    }

    return 0;

}

#include<cstdio>

#include<iostream>

#include<vector>

#include<map>

#include<algorithm>

using namespace std;

const int Nmax = 10000;

int father[Nmax];

bool vis[Nmax] = {false};

struct node{

    int id, peoNum;

    double Sav, Aav;

};

void init(){

    for(int i = 0; i < Nmax; ++i)father[i] = i;

}

int findF(int x){

    int z = x;

    while(x != father[x])x = father[x];

    while(z != father[z]){

        int temp = father[z];

        father[z] = x;

        z = temp;

    }

    return x;

}

void Union(int a, int b){

    int fa = findF(a), fb = findF(b);

    if(fa != fb)father[fb] = fa;

}

bool cmp(node a, node b){

    bool flag = false;

    if(a.Aav / a.peoNum > b.Aav / b.peoNum){

        flag = true;

    }else if(a.Aav / a.peoNum == b.Aav / b.peoNum && a.id < b.id){

        flag = true;

    }

    return flag;

}

int main(){

    init();

    int N = 0;

    vector<node>v, v2;

    scanf("%d", &N);

    for(int i = 0; i < N; ++i){

        int f, m, id, k, idm = 10000;

        int peonum = 0;

        scanf("%d%d%d%d", &id, &f, &m, &k);

        if(f == -1 && m == -1)idm = id;

        if(f == -1 && m != -1)idm = min(id, m);

        if(f != -1 && m == -1)idm = min(id, f);

        if(f != -1 && m != -1)idm = min(min(m, f), id);

        if(!vis[id]){

            peonum = 1;

            vis[id] = true;

        }

        if(f != -1){

            Union(f, id);

            if(!vis[f]){

                peonum++;

                vis[f] = true;

            }

        }

        if(m != -1){

            Union(m, id);

            if(!vis[m]){

                peonum++;

                vis[m] = true;

            }

        }

        for(int j = 0; j < k; ++j){

            int child;

            scanf("%d", &child);

            idm = min(idm, child);

            Union(id, child);

            if(!vis[child]){

                peonum++;

                vis[child] = true;

            }

        }

        int setNum, area;

        scanf("%d%d", &setNum, &area);

        int flag = false;

        for(int j = 0; j < v.size(); ++j){

            if(findF(v[j].id) == findF(idm)){

                v[j].id = min(idm, v[j].id);

                v[j].peoNum += peonum;

                v[j].Sav += (double)setNum;

                v[j].Aav += (double)area;

                flag = true;

                break;

            }

        }

        if(!flag)v.push_back({idm, peonum , (double)setNum, (double)area});

    }

    //录入数据的时候只合并了一部分家庭，再合并一遍

    v2.push_back(v[0]);

    for(int i = 1; i < v.size(); ++i){

        int flag = false;

        for(int j = 0; j < v2.size(); ++j){

            if(findF(v[i].id) == findF(v2[j].id)){

                v2[j].id = min(v[i].id, v2[j].id);

                v2[j].peoNum += v[i].peoNum;

                v2[j].Sav += v[i].Sav;

                v2[j].Aav += v[i].Aav;

                flag = true;

                break;

            }

        }

        if(!flag)v2.push_back(v[i]);

    }

    cout<<v2.size()<<endl;

    sort(v2.begin(), v2.end(), cmp);

    for(int i = 0; i < v2.size(); ++i){

        printf("%04d %d %.3f %.3f\n", v2[i].id, v2[i].peoNum, v2[i].Sav / v2[i].peoNum, v2[i].Aav / v2[i].peoNum);

    }

    return 0;

}

巴特西

【刷题-PAT】A1114 Family Property （25 分）

最新文章

热门文章