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

Re:是我弱了 应该枚举rank的上界

Posted by hansechang at 2008-07-30 20:39:34 on Problem 1062
In Reply To:Re:请您稍稍详细的讲一下吧，因为我发现数据弱，有些dijkstra是错的能ac Posted by:xfxyjwf at 2006-03-15 21:26:41 
> 增加一个起点S, 若某物品Ai的价格为Pi, 添一条权值为Pi的边S-->Ai
> 若物品Aj可以用Ai加优惠价Qi换得,加权值为Qi的边Ai-->Aj
> 除了S,每个点都有一个rank,枚举rank最大的点(从1到n),不妨设其rank值为R0,除去rank大于R0的,以及rank小于R0-m的.在剩余的图中求S到A1的最短路.
> 最短路(dijkstra)的时间复杂度是O(n^2),枚举n次,总的时间复杂度是O(n^3)
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