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

不知道哪位大牛写的 但真的很好用 保证可以过

Posted by zhoubizhang at 2010-07-28 13:54:16 on Problem 1364
差分约束根本不需要什么附加顶点, 附加顶点的唯一
用处就是保证图的连通性, 不让你有负环判不到的情况, 
解决这种问题的最佳途径就是初始把所有顶点都加入队列, 
并且将所有dis置0, 这就相当于加了一个不存在的附加顶点, 
它与所有的顶点的直连长度都是0. 但是注意在判负环时必须是
"cnt>n"而不是"cnt>=n", 因为第一次所有顶点入队只是相当于
把一个附加顶点加入到队列中而已, 不应该算在cnt中, 如果在
此步骤没有增加过cnt, 则">="也是可以的.

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