*PAT_甲級_1114 Family Property (25分) (C++)【并查集】

目錄

​​1，題目描述​​

​​2，思路​​

​​資料結構​​

​​算法​​

​​3，AC代碼​​

​​4，解題過程​​

1，題目描述

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      

2，思路

感謝大佬​​@日沉雲起【pat甲級1114. Family Property (25)】​​

在接受每行資料的時候，進行并查集的合并，并存儲每行id對應的資産。周遊father集合，統計來自同一個根的節點數目、資産。周遊統計結果，将其放入ans容器中，排序輸出。

資料結構

• struct estate{

  int id, num = 0;                    //id家族中的最小編号 num家族人數

  double sets = 0.0, area = 0.0;      //sets家族總房子數 area家族房産總面積

  };

• int father[10006]：并查集，根節點為家族中編号最小的id；
• unordered_map<int, pair<double, double>> idEstate;  // !!!對應每行輸入的首個id， 兩個double分别對應sets、area(確定每個家庭的資産隻計算一次)；
• unordered_map<int, estate> familyEstate：    //家族的情況
• vector<estate> ans：最終結果，用vector存放便于排序；

算法

1. 初始化并查集father：



2. 将每一行的id和其他成員進行并查集合并，并且用idEstate記錄每一行的資産：



3. 周遊并查集father，統計每個根節點root下的家族人數以及資産總數，并存放在familyEstate：



4. 周遊familyEstate，将家族資訊存放在vector<estate>ans中，便于排序：



5. 輸出（事實證明最後一行末尾的\n不影響送出的正确性）：

3，AC代碼

#include<bits/stdc++.h>
using namespace std;
struct estate{
    int id, num = 0;                    //id家族中的最小編号 num家族人數
    double sets = 0.0, area = 0.0;      //sets家族總房子數 area家族房産總面積
};
bool cmp(estate a, estate b){
    return a.area != b.area ? a.area > b.area : a.id < b.id;
}
int father[10006];
int findFather(int x){
    if(father[x] == x)
        return x;
    father[x] = findFather(father[x]);
    return father[x];
}
int unionSet(int a, int b){
    int A = findFather(a), B = findFather(b);
    if(A != B)
        father[max(A, B)] = min(A, B);      //将較大值的根節點變更為較小的值
}
unordered_map<int, pair<double, double>> idEstate;  // !!!對應每行輸入的首個id sets、area(確定每個家庭的資産隻計算一次)
unordered_map<int, estate> familyEstate;    //家族的情況
int main(){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt", "r", stdin);
#endif // ONLINE_JUDGE
    int N, id, fa, ma, num, chi;
    cin>>N;
    iota(father, father + 10006, 0);        //并查集初始化
    for(int i = 0; i < N; i++){
        scanf("%d %d %d %d", &id, &fa, &ma, &num);
        if(fa != -1) unionSet(id, fa);
        if(ma != -1) unionSet(id, ma);
        while(num--){
            scanf("%d", &chi);
            unionSet(id, chi);
        }
        scanf("%lf %lf", &idEstate[id].first, &idEstate[id].second);    //分别指sets、area
    }
    for(int i = 0; i < 10006; i++){         //統計每個根節點下的家族人數以及資産總數
        int root = findFather(i);
        if(root != i){
            familyEstate[root].num++;
        }
        if(idEstate.find(i) != idEstate.cend()){
            familyEstate[root].sets += idEstate[i].first;   // !!!注意是first 第一個double即sets
            familyEstate[root].area += idEstate[i].second;  // !!!注意是second 第二個double即area
        }
    }
    vector<estate> ans;
    for(auto it : familyEstate){
        estate n;
        n.id = it.first;
        n.num = it.second.num + 1;          //上個for循環周遊時 沒有加上根節點 是以這裡加一
        n.sets = it.second.sets / n.num;
        n.area = it.second.area / n.num;
        ans.push_back(n);
    }
    sort(ans.begin(), ans.end(), cmp);
    printf("%d\n", ans.size());
    for(int i = 0; i < ans.size(); i++){
        printf("%04d %d %.3f %.3f\n", ans[i].id, ans[i].num, ans[i].sets, ans[i].area);
    }
    return 0;
}      

4，解題過程

想到了并查集，但是沒想好怎麼做。。。(;´༎ຶД༎ຶ`)