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

我贪心0ms过。构造有向图,每次选入度最小的一个G作为下一个目标,即可。取最多G不对,有反例。

Posted by jieshoucode at 2008-07-23 21:47:59 on Problem 1548
In Reply To:可否这样贪? Posted by:gzw_02 at 2008-07-19 18:39:08
若能从a到b,则存在a到b的有向边,由此转化成图。
每次选下一个目标时,选可以到达且入度最小的结点。其实就是当有入度为1的点时把它选出来。因为入度不为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