PAT 1114

题目 ： Family Property

分值 ： 25
难度 ： 并叉集
思路 ： 并叉集来做，一开始就想到了，但是他是变式，就很惹人厌.
坑点 ： 总的来说首先是一个结构体来并叉集，这个简单，但是他除了并叉集之外，还有几个恶心人的
       地方，他有其他的要求：  
       1）首先你作为一个联通集的根 要是整个联通集最小的
       2）其次你要把一个联通集的所有节点两个变量都加合起来求平均 作为整个联通集的特性
       3）然后你要根据一个集合的两个平均变量做出排序
       一开始我的做法：
       单方面去记录联通集信息，然后用单独记录每个集合的 最小成员id 和 两个平均变量，烦😡
       也导致了一开始做的很不顺利，完全是探索式地去写，哪有问题就贴一个膏药，效率低下
       然后冷静思考了原因，发现自己对于这种问题的求解一直存在着问题：
       首先利用 结构体存放每个节点信息 利用结构体完成 并叉集中的 集合划分
       求解每个区域的最小节点id： 遍历每个节点，如果发现节点的根 比自己大，调换一下
       （一开始我怀疑这种操作会不会打乱之前压缩好的路径，其实不然，因为每次调换都会重新压缩）
       求解每个区域的成员个数： 遍历每个节点，除非是根节点，不然每个节点的根节点.count++
       求解每个区域的总财产值： 遍历每个节点，除根节点外，每个节点的根节点财产值都加上当前节点财产.
       然后遍历每个有效的根节点，存入结果数组，根节点个数就出来了，然后按要求结构体排序输出.

具体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <iostream>
#include <algorithm>
using namespace std ;
typedef struct Node {
    int id ;
    int f;
    double Areas ;
    double Sets ;
    int count ;
}Nodes ;
Nodes data[10001] ;
Nodes result[10001];
bool cmp(Node a , Node b)
{
    if(a.Areas/a.count == b.Areas /b.count )
        return a.id < b.id ;
    return a.Areas/a.count > b.Areas /b.count ;
}
int find(int x)
{
    if(data[x].f == x)
        return x ;
    else
        return data[x].f = find( data[x].f );
}
int main(){
    int N ;
    cin >> N ;
    int id,fa,ma,k,ch,sets,areas ;
    int s1,s2,s3;
    for(int i = 0 ; i < 10001 ;i++)
        data[i].f = i ;
    for(int i = 0 ; i< N ; i++)
    {
        cin >> id >> fa >> ma ;
        s1 = find(id) ;
        if(fa !=-1)
        {
            s2 = find(fa);
            if(s1!=s2 )
                data[s2].f = s1 ;
        }
        if(ma!= -1)
        {
            s3 = find(ma) ;
            if(s1!=s3)
                data[s3].f = s1;
        }
        cin >> k ;
        for(int j = 0 ; j< k ;j++)
        {
            cin >> ch;
            s2 = find (ch) ;
            if(s2!=s1 )
            {
                data[s2].f = s1 ;
            }
        }
        data[id].count =1  ;
        cin >> data[id].Sets >> data[id].Areas ;
    }
    //cout <<data
    for(int i = 0 ; i< 10000 ; i++)
    {
        int source = find(i) ;
        if( source > i )
        {
            data[source].f = i ;
            data[i].count = 1 ;
            data[i].f = i ;
        }
    }
    for(int i = 0 ; i< 10000; i++)
    {
        int source = find(i) ;
        if( source == i ) continue ;
        data[source].count++ ;
        data[source].Sets += data[i].Sets;
        data[source].Areas+= data[i].Areas;
    }
    int cur = 0 ;
    for(int i = 0 ; i< 10000 ; i++)
    {
        if(data[i].count && find(i)==i)
        {
            result[cur].id = i ;
            result[cur].f = data[i].f ;
            result[cur].Areas = data[i].Areas;
            result[cur].Sets = data[i].Sets;
            result[cur].count = data[i].count ;
            cur ++ ;
        }
    }
    sort(result , result + cur ,cmp );
    cout <<cur <<endl ;
    for(int i = 0 ; i< cur ;i++)
    {
        printf("%04d %d %.3lf %.3lf\n" ,result[i].id ,result[i].count ,result[i].Sets/result[i].count , result[i].Areas/result[i].count);
    }
}