CCCC L2-007. 家庭房产 建图 XJB模拟

https://www.patest.cn/contests/gplt/L2-007

题解：一开始是想直接并查集，一个家就是一个集合，对每个集合维护一个人数num1一个房产数num2 一个房产面积area 以及一个最小编号。

　　后来想了一下，直接建树，然后对每棵树搜一遍算了，给的信息太多了。。。但是每个人会有两个父亲节点，我们一个都不管，只是存在数组里，在找这颗树的最小id时会用到。

　　再想了一下，直接建图呗。然后写了半小时。。太复杂了吧

坑：1.set的erase的参数不是int，是iterator//把我neng得没脾气

　　2。这题的总人数和给的数据数是不一样的//我这儿卡了

　　3.最后还忘了输出家庭总数

　　4.auto t:不能修改容器的值，只能用来输出。

　

#define _CRT_SECURE_NO_WARNINGS

#include<iostream>

#include<vector>

#include<queue>

#include<map>

#include<cmath>

#include<stack>

#include<string.h>

#include<set>

#include<algorithm>

using namespace std;

const int maxn = 1e5 + ;

int f[maxn], num[maxn], are[maxn], mn[maxn],vis[maxn];

vector<int> E[maxn];

vector<int> root;

set<int> st;

map<int, int>mmp;

struct node {

    double num1, num2, area;//1人2房

    int idx;

    node(double num1 = , double num2 = , double area = , int idx = 1e5) :num1(num1), num2(num2), area(area), idx(idx) {}

};

int cmp(node a, node b) {

    if (a.area == b.area) {

        return a.idx < b.idx;

    }

    else return a.area > b.area;

}

int main(){

    int n;

    cin >> n;

    int cnt = n;

    while (n--) {

        int x, y, z,k;

        cin >> x >> y >> z; mmp[x]++; mmp[y]++; mmp[z]++;

        if (y == - && z == -)root.push_back(x);

        else {

            if(y!=-)E[y].push_back(x); E[x].push_back(y);

            if(x!=-)E[z].push_back(x); E[x].push_back(z);

        }

         if (x == -)  x = 1e5;

         if (y == -)y = 1e5;

        mn[x] = min(x, y);

        cin>> k;

        while (k--) {

            int w;

            cin >> w; mmp[w]++;

            E[x].push_back(w); E[w].push_back(x);

        }

        cin >> num[x] >> are[x];

    }

    vector<node>  ans; vis[-] = ;

    int id =;

    mmp.erase(-);

    while(!mmp.empty()) {

        int t = mmp.begin()->first;

        if (vis[t]) continue;//his couple has done.

        //bfs

        ans.push_back(node());

        ans[id].num2 =num[t];

        ans[id].num1=;

        ans[id].area = are[t];

        ans[id].idx =t;

        id++;

        queue<int> Q;

        Q.push(t); vis[t] = ; mmp.erase(t);

        while (!Q.empty()) {

            int now = Q.front(); Q.pop();

            for (int i = ; i < E[now].size(); i++) {

                int v = E[now][i];

                if (vis[v])continue;

                Q.push(v); vis[v] = ; mmp.erase(v);

                ans.back().num2+= num[v];

                ans.back().num1++;

                ans.back().area += are[v];

                ans.back().idx = min(ans.back().idx, v);

            }

        }

    }

    for (vector<node>::iterator t = ans.begin(); t != ans.end();t++) { t->area /= t->num1; t->num2 /= t->num1; }

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

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

    for (auto t : ans) {

        printf("%04d", t.idx);

        //cout << ' ' << t.num1;

        printf(" %.0lf %.3lf %.3lf\n", t.num1, t.num2, t.area);

        //<< ' ' << t.num2 << ' ' << t.area << endl;

    }

    system("pause");

}