随笔 - 97, 文章 - 22, 评论 - 81, 引用 - 0
数据加载中……

夜深人静写算法(二十三) - 最短路

新地址:夜深人静写算法(二十三)- 最短路

posted on 2015-11-19 23:44 英雄哪里出来 阅读(34612) 评论(4)  编辑 收藏 引用 所属分类: 算法专辑

评论

# re: 夜深人静写算法(四) - 差分约束  回复  更多评论   

写得很不错。
2015-11-30 15:53 | Sleepless Loki

# re: 夜深人静写算法(四) - 差分约束  回复  更多评论   

差分约束一直不懂,知道看到博主举的例子,醍醐灌顶,感谢分享
2016-04-12 12:06 | _

# re: 夜深人静写算法(四) - 差分约束  回复  更多评论   

spfa中为何是vcnt++>n判断负环?
假如n=10,一个点已经入队10次,那么这样写显然会允许第11次入队,那么入队次数就大于n了呀
2016-06-01 20:54 | Rapiz

# re: 夜深人静写算法(四) - 差分约束  回复  更多评论   

“言之,用一个数组c[i]来记录i这个点入队的次数,所有的c[i]必定都小于等于n”
这里的"小于等于"应是写错了。

入队c[i]次的点的最短路包含c[i]+1个顶点。
比如邻s的点,边权足够小,那么它只会入队1次,包含2个顶点。

又因为最短路最长包含n个顶点,所以c[i]+1<=n
推出c[i]<n

这也就解释了我上一条评论的疑问。
2016-06-01 21:00 | Rapiz

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理