`
huobengle
  • 浏览: 854464 次
文章分类
社区版块
存档分类
最新评论

POJ-2983 用SPFA求解差分约束..

 
阅读更多

同上..用SPFA来解决...用SPFA的第一个问题是如何跳出while..因为这题明显的可能有负环..SPFA如果普通的...有负环..则会将环上的点不断入队列..就会死循环!!为了能跳出死循环或者说能判断出有负环..就用个数组来记录每个点入队的次数...如果入队的次数超过点的总数N了..则可以判断出是出现负环了..这个思想是从Bellman-Ford那来的..回想Bellman-Ford..外围是用来循环次数..是循环了N次..第二层则循环所有的边..可以发现一个点最多就更新循环次数N了...

再一个要注意的是用SPFA就必须先要确定源点然后入队...但这里如果任意确定源点会出错...因为这题的图不一定时连通的~~有可能有多个独立的图..有多个源点..所以要么就在开始时将所有点入队...d [ ] 统一赋值为0...要么加一个超级点指向所有点权值为0....其实本质是一样的...


Program:



分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics