PATA1114题解

并查集与排序

//
//  main.cpp
//  PATA1114
//
//  Created by Phoenix on 2018/2/24.
//  Copyright © 2018年 Phoenix. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 10010;
int father[maxn], num[maxn], minid[maxn], area[maxn], sets[maxn];
bool flag[maxn] = {false};

struct node {
    int id, num, minid, area, sets;
    bool tag;
    double ave_sets, ave_area;
}peo[maxn];

int findFather(int x) {
    int a = x;
    while (a != father[a]) {
        a = father[a];
    }
    while (x != father[x]) {
        int c = father[x];
        father[x] = a;
        x = c;
    }
    return a;
}

void Union(int a, int b) {
    int faA = findFather(a);
    int faB = findFather(b);
    if(faA != faB) father[faA] = faB;
}

bool cmp(node a, node b) {
    if(a.tag != b.tag) return a.tag > b.tag;
    else if(a.ave_area != b.ave_area) return a.ave_area > b.ave_area;
    else return a.id < b.id;
}

int main(int argc, const char * argv[]) {
    for(int i = 0; i < maxn; i++) {
        peo[i].id = father[i] = i;
        peo[i].minid = 11111;
        peo[i].sets = peo[i].area = peo[i].num = 0;
    }
    int n, num = 0;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        int a, b, c, k, money, place;
        scanf("%d %d %d %d", &a, &b, &c, &k);
        flag[a] = true;
        if(b != -1) {
            flag[b] = true;
            Union(a, b);
        }
        if(c != -1) {
            flag[c] = true;
            Union(a, c);
        }
        for(int i = 0; i < k; i++) {
            int d;
            scanf("%d", &d);
            flag[d] = true;
            Union(a, d);
        }
        scanf("%d %d", &money, &place);
        peo[a].sets = sets[a] = money;
        peo[a].area = area[a] = place;
    }
    for(int i = 0; i < maxn; i++) {
        if(flag[i] == true) {
            if(father[i] == i) {
                num++;
                peo[i].tag = 1;
                peo[i].num++;
            } else {
                peo[i].tag = 0;
                peo[findFather(i)].sets += peo[i].sets;
                peo[findFather(i)].area += peo[i].area;
                peo[findFather(i)].num++;
            }
            if(i < peo[findFather(i)].minid) peo[findFather(i)].minid = i;
        }
    }
    for(int i = 0; i < maxn; i++) {
        if(flag[i] == true && father[i] == i) {
            peo[i].ave_sets = 1.0 * peo[i].sets / peo[i].num;
            peo[i].ave_area = 1.0 * peo[i].area / peo[i].num;
        }
    }
    sort(peo, peo + maxn, cmp);
    printf("%d\n", num);
    for(int i = 0; i < num; i++) {
        printf("%04d %d %.3f %.3f\n", peo[i].minid, peo[i].num, peo[i].ave_sets, peo[i].ave_area);
    }
    return 0;
}