POJ 2054 Color a Tree 巧妙的贪心思想

题目大意就是要求 Sigma( i * Ci ) (i = 1 .. n) 的值最小，{ Ci } 是节点费用的一个排列，同时要满足父节点要出现在子节点前面。

考虑某一个可行解，就是{ Ci }的某一个排列。找到其中的最大值，比如为Ck，它有一个父节点比如Cp。显然Cp要出现在Ck之前。更进一步，Cp就应该出现在Ck的前一个位置。只有这样才有可能Sigma的值最小。不然我们可以将Ck位置向前移动，得到一个更小的Sigma值，并且不破坏上面的约束。既然Cp就出现在Ck的前一个位置，那么它们其实就是连在一起的，可以最为一个整体来看。因此可以把Ck和Cp合并为一个节点，这样就缩小为n-1的规模，缩小后的点的Ci值修改为他们的平均数，然后同样处理即可。这里的平均数，是指两个被合并的集合的Ci值之和除以两个集合的大小之和，譬如两个集合A，B，A的Ci和为Ca，大小为Ta，B的Ci和为Cb，大小为Tb，则合并后为(Ca+Cb)/(Ta+Tb)。

7795200    IwfWcf    2054    Accepted    752K    282MS    G++    1288B    2010-10-27 11:33:56