L2-007 family real estate (25 points) and search set or graph traversal

Topic details - L2-007 Family property (25 branch ) (pintia.cn)

Union checking set

Ideas ： Record the number of families 、 The idea of real estate quantity and real estate area is the same as that of connecting blocks （ Remember to initialize ）, When a new node is merged into the set, the attribute value of the node is added to the ancestor node （ Set the minimum number to ancestor ）, One last poll to get ancestors （f[x] = x spot ） The number of is the number of families . Then the structure is sorted and output .

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 10010;
//cnt  The number of properties , pn Number of families  
int f[N],cnt[N],area[N],pn[N];
vector<int> child(N);

struct Node{
    int id,pn;
    double avlc,avla; // Number of houses per capita   Area per capita  
    bool operator<(const Node &t) const{
        if(avla != t.avla) return avla > t.avla;
        return id < t.id;
    }
};

int getf(int x){
    if(x == f[x]) return x;
    else return f[x] = getf(f[x]);
}

void merge(int a,int b){
    int ta = getf(a);
    int tb = getf(b);
    if(ta != tb){
        if(ta > tb) swap(ta,tb);
        f[tb] = ta;
        cnt[ta] += cnt[tb];
        area[ta] += area[tb];
        pn[ta] += pn[tb];
    }
}

void init(int x){
	pn[x] = 1;
	f[x] = x;
} 

int main(){
    int n;
    cin>>n;
    memset(f,-1,sizeof f);
    memset(cnt,0,sizeof cnt);
    memset(area,0,sizeof area);
    for(int i = 0; i < n; i++){
        int num,father,mother,k;
        cin>>num>>father>>mother>>k;
        for(int j = 0; j < k; j++){
            cin>>child[j];
            if(f[child[j]] == -1) init(child[j]);
        }
        int fc,zarea;
        cin>>fc>>zarea;
        if(f[num] == -1) init(num);
        cnt[getf(num)] += fc;
        area[getf(num)] += zarea;
        
        if(father != -1) {
            if(f[father] == -1) init(father);
            merge(num,father);
        }
        if(mother != -1) {
            if(f[mother] == -1) init(mother);
            merge(num,mother);
        }

        for(int j = 0; j < k; j++) merge(num,child[j]);
    }
    
    vector<Node> ans;
    for(int i = 0; i < N; i++) 
        if(f[i] == i) 
            ans.push_back({i,pn[i],1.0*cnt[i]/pn[i],1.0*area[i]/pn[i]});
    
    sort(ans.begin(),ans.end());
    
    cout<<ans.size()<<'\n';
    for(int i = 0; i < ans.size(); i++)
        printf("%04d %d %.3lf %.3lf\n",ans[i].id,ans[i].pn,ans[i].avlc,ans[i].avla);
    
    return 0;
}

Graph traversal

L2-007 Family property (25 branch )_ One more line and go to sleep -CSDN Blog

This may be better written .