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

夜深人静写算法（二十三） - 最短路

​

新地址：夜深人静写算法（二十三）- 最短路

posted on 2015-11-19 23:44 英雄哪里出来 阅读(34821) 评论(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   知识库   博问   管理