PAT 1114

https://pintia.cn/problem-sets/994805342720868352/problems/994805356599820288

这次，你需要帮助我们计算出家庭财产数据。给出每个人的家庭成员，以及他的房产信息，我们需要知道每个家庭的大小，以及平均大小以及它们房产的套数。 输入：ID Father Mother k Child1 … Childk M area 输出：ID M AVGsets ​​ AVG​area​​

这里<code>id</code>代表的是一个家庭成员的唯一 <code>id</code>，<code>Father</code>代表的是他的父亲<code>id</code>，<code>mother</code>代表的是他的母亲id，k代表的是他的孩子数，<code>Child1 ... Childk</code> 代表的就是他的孩子的id；M ： 房产数； area ：房产大小。

首先输出总家族数，接着换行输出该家族最小的id；总房产数；人均房产数；人均房产大小

<code>Family Property</code> 家庭财产

这倒题初见以为可以使用深搜实现，可以深度搜索该id的所有father,mother,child…但是存在的一个问题是，对于有些数据，可能无法实现。可能的数据示例如下：

上面这些成员其实都是一个家族，但是如果使用<code>DFS</code>得到的结果却是2个家族。这是为什么呢？

通过<code>1234</code>可以得到的家庭成员有：

<code>1234：1234 5678 9012 0002 1236 1235 5678</code>

因为深搜是通过下标实现的，导致因为没有<code>1236</code>这个下标的数据，所以出现了类似<code>2222</code>这种节点无法被计算到一个家族中。

针对上述这个问题我们就需要使用并查集 了。

实现步骤如下：

step 1：【根据题目要求，因为要找出最小的id，所以这里取最小的节点作为父节点】将每行输入中的数放在一个集合中。取较小的id作为父节点 【这是一个关键点】

step 2：在对输入数据进行并查操作之后，就得到了一个数组<code>father</code>

step 3：遍历这个father数组，找出根的那个节点，并在for循环中累计房产数，房产大小。然后写入到一个ans数组。

step 4：对ans数组进行排序，然后输出想要的前几位数。

<code>find()</code>函数

这里的<code>find()</code>函数是非常重要的！！！ 代码如下：

因为需要统计结果， 所以只能是统计 最深根 的那个结果。所谓最深根，举例如下：

那么这里的最深根就是1，而不是5678，或者是1234。因为在它们之上，仍然还有一个较小的节点1。同理，<code>find()</code>函数就是用于寻找最深根的那个元素。可以保证无论在哪个节点上，都能够遍历到最深的那个节点。这就是实现的关键。

下面给出针对上面测试用例生成的<code>father</code> 数组。

参考了 liuchuo 的代码 【给点广告费好不好嘛*_*】

========================update on 20190216 ==================

距上次写这个博客大概已经一个月过去了，我重新自己重新实现了这个代码并AC了。

代码如下：

注意点

1）注意这里的求得的财产信息等需要精确到三位数，所以需要使用 <code>double</code>存储，这个问题导致我没有一遍AC

2）找出不同family的个数。我这里使用的方法是用一个set进行标记，然后找出这些set的不同的最小sun的个数，即 得到 familyCount。

3）这里只定义了一个结构体

4）输出格式的控制我喜欢使用 <code>printf()</code>