> 这道题就是要求 Sigma( i * Ci ) (i = 1 .. n) 的值最小，{ Ci } 是节点费用的一个排列，同时要满足父节点要出现在子节点前面。
> 如果没有父节点出现在子节点前面这个限制，那么答案很明显。当{ Ci }按降序排列的时候，Sigma的值是最小的。当有这个限制的时候情况也是类似的。考虑某一个可行解，就是{ Ci }的某一个排列。找到其中的最大值，比如为Ck，它有一个父节点比如Cp。显然Cp要出现在Ck之前。更进一步，Cp就应该出现在Ck的前一个位置。只有这样才有可能Sigma的值最小。不然我们可以将Ck位置向前移动，得到一个更小的Sigma值，并且不破坏上面的约束。既然Cp就出现在Ck的前一个位置，那么它们其实就是连在一起的，可以最为一个整体来看。这样问题的规模就有n减小到n-1。然后重复这一过程，直到所有的位置都确定下来。
> 这样我们就找到了最优解。

• How to "重复这一过程"? (0) Miracles 2005-05-13 21:59:33
  • 合并后的结点用它们的平均值代替 (0) frkstyc 2005-05-13 22:10:55
    • 合并结点应该用什么结构来处理呢？感觉code起来好麻烦啊，合并后还要记下里面的顺序啊 (0) Cubic 2005-08-06 06:32:03
      • frkstyc兄帮帮忙啊~~~不知道怎么写方便点 (0) Cubic 2005-08-06 16:10:02