英雄哪里出來

隨筆 - 97, 文章 - 22, 評論 - 81, 引用 - 0

數據加載中……

夜深人靜寫算法（二十三） - 最短路

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

posted on 2015-11-19 23:44 英雄哪里出來閱讀(35028) 評論(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

刷新評論列表

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: 夜深人靜寫算法（七）[2016 賀歲版] - 線段樹夜深人靜寫算法（六） - 最近公共祖先夜深人靜寫算法（五） - 初等數論夜深人靜寫算法（二十三） - 最短路夜深人靜寫算法（十三） - 樹狀數組夜深人靜寫算法（二） - 動態規劃夜深人靜寫算法（一） - 搜索入門二維線段樹 AC自動機 RMQ

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

# re: 夜深人靜寫算法（四） - 差分約束回復 更多評論

# re: 夜深人靜寫算法（四） - 差分約束回復 更多評論

# re: 夜深人靜寫算法（四） - 差分約束回復 更多評論

# re: 夜深人靜寫算法（四） - 差分約束 回復 更多評論

英雄哪里出來

夜深人靜寫算法（二十三） - 最短路

評論

導航

常用鏈接

留言簿(22)

隨筆分類(102)

文章分類(22)

ACM

搜索

積分與排名

最新評論

英雄哪里出來

夜深人靜寫算法（二十三） - 最短路

評論

# re: 夜深人靜寫算法（四） - 差分約束 回復 更多評論

# re: 夜深人靜寫算法（四） - 差分約束 回復 更多評論

# re: 夜深人靜寫算法（四） - 差分約束 回復 更多評論

# re: 夜深人靜寫算法（四） - 差分約束 回復 更多評論

導航

常用鏈接

留言簿(22)

隨筆分類(102)

文章分類(22)

ACM

搜索

積分與排名

最新評論

# re: 夜深人靜寫算法（四） - 差分約束回復更多評論

# re: 夜深人靜寫算法（四） - 差分約束回復更多評論

# re: 夜深人靜寫算法（四） - 差分約束回復更多評論

# re: 夜深人靜寫算法（四） - 差分約束回復更多評論