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:【终极WA错误点】这道题真恶心,用BELLMAN 最长路径 正权环 WA了三次才AC,给出我WA的地方给大家参考testtesttest

Posted by gaojie at 2009-12-15 18:14:24 on Problem 1932
In Reply To:【终极WA错误点】这道题真恶心,用BELLMAN 最长路径 正权环 WA了三次才AC,给出我WA的地方给大家参考 Posted by:bobten2008 at 2009-12-12 00:57:19
> 在用BELLMAN时,当考虑某个点i时,如果从1到i的当前最大距离是负值,则这个点必须跳出来不能处理。因为此时这个点并不是活着的点,所以不能处理以它为起点的边。
> 
> 如果不这样做可能会存在的错误CASE如下所示:
> 1->2->3->4
>       ^  |
>    6<-5 <
> 即:如果3,4,5可以构成一个正权环,但是2点的生命值为-1000,
> 那么当游戏者从1走到2时的当前生命值为100-1000=-900,即已经
> 为负了,是不能继续往下走的。否则如果不从2跳出的话,后续的处理中便会找到
> 正权环3,4,5且从这个环到6是可达的,结果就会错误地输出WINNABLE,
> 但是这个图是HOPELESS的
> 
> 其他的错误点就不说了,估计应该都很容易搞定。另外判断可达可以事先从n点利用
> BFS反向搜索来进行!

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