Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

my sol.

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

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator