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

• Re:my sol. (401) fatboy 2005-01-16 09:47:19
  • Re:my sol. (11) fatboy 2005-01-16 09:47:44
• Re:my sol. (401) Miracles 2005-05-13 21:59:02
  • 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
• 很多不懂的地方 (196) Cubic 2005-08-06 06:29:58
  • 我现在WA，我试着回答一下，也请高手看看我想得对不对。 (274) mostleg 2005-08-06 14:35:02
    • ac le (78) frkstyc 2005-08-06 14:44:55
      • 嗯。回得好快呀：） (0) mostleg 2005-08-06 14:47:47
    • 合并后的值怎么计算的？ (78) tmpbt 2005-08-06 16:19:23