Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
不知道哪位大牛写的 但真的很好用 保证可以过差分约束根本不需要什么附加顶点, 附加顶点的唯一 用处就是保证图的连通性, 不让你有负环判不到的情况, 解决这种问题的最佳途径就是初始把所有顶点都加入队列, 并且将所有dis置0, 这就相当于加了一个不存在的附加顶点, 它与所有的顶点的直连长度都是0. 但是注意在判负环时必须是 "cnt>n"而不是"cnt>=n", 因为第一次所有顶点入队只是相当于 把一个附加顶点加入到队列中而已, 不应该算在cnt中, 如果在 此步骤没有增加过cnt, 则">="也是可以的. Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator