GPLT L2-007. 家庭房产 dfs

题目链接戳这里
有关系的人连边,深搜路上收集那些信息即可,但是这题很繁琐,状态数很多,要细心兼顾好.最后的解别忘记排序
写的时候傻的一个点:
人的编号并非都只出现在首编号里,对于那些父母 孩子也要进行存在性的标记,这样dfs才不会漏了这些点!
我是默认vis=-1,存在则为0,访问过为1.
再就是浮点数之间的比较要小心,我是先得到他要求的精度之后再进行比较的.

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define pb push_back
const int inf = 0x3f3f3f3f, maxN = 10005;
int N, M, vis[maxN];
vector<int> G[maxN];

// dfs要用的全局变量
// 家族最小编号 总人数 总套数 总面积
int min_num, zrs; double zts, zmj;

// 链接操作 与 保存每个人的财产money:套数 面积 解结构
void link(int a, int b) { G[a].pb(b); G[b].pb(a); }
struct node { double ts, mj; } mny[maxN];
struct answer { 
    int num, rks; double avg_ts, avg_mj;
    answer(int n_ = 0, int r_ = 0, double t_ = 0, double m_ = 0):
        num(n_), rks(r_), avg_ts(t_), avg_mj(m_) {}
};

vector<answer> ans;

void dfs(int s) {
    min_num = min(min_num, s);

    vis[s] = 1;
    ++zrs;
    zts += mny[s].ts;
    zmj += mny[s].mj;

    rep(i, 0, G[s].size()) {
        int ch = G[s][i];
        if (!vis[ch]) {
            dfs(ch);
        }
    }
}

bool comp(const answer& A, const answer& B) {
    int ma, mb;
    ma = (A.avg_mj + 0.0005) * 1000;
    mb = (B.avg_mj + 0.0005) * 1000;
    if (ma == mb)
        return A.num < B.num;
    else
        return ma > mb;
}

int main() {
    // freopen("data.in", "r", stdin);
    mst(mny, 0);
    mst(vis, -1);
    scanf("%d", &N);
    int bh, f, m, sch, ch, fc, mj;
    rep(i, 0, N) {
        scanf("%d %d %d %d", &bh, &f, &m, &sch);
        vis[bh] = 0;
        if (f != -1) { link(bh, f); vis[f] = 0; }
        if (m != -1) { link(bh, m); vis[m] = 0; }
        
        rep(j, 0, sch) {
            scanf("%d", &ch);
            link(bh, ch);
            vis[ch] = 0;
        }
        scanf("%lf %lf", &mny[bh].ts, &mny[bh].mj);
    }

    int cnt = 0;
    rep(i, 0, 10000) {
        if (!vis[i]) {
            ++cnt;
            zrs = zts = zmj = 0;
            min_num = inf;
            dfs(i);
            zts /= zrs;
            zmj /= zrs;
            ans.pb(answer(min_num, zrs, zts, zmj));
        }
    }
    sort(ans.begin(), ans.end(), comp);
    printf("%d\n", cnt);
    rep(i, 0, cnt) {
        printf("%04d %d %.3lf %.3lf\n",
                ans[i].num, ans[i].rks, ans[i].avg_ts, ans[i].avg_mj);
    }
    return 0;
}