【題意】給定一個N(N<=100)個節點的有向圖，求不相交的最短路徑個數（兩條路徑沒有公共邊）。 【思路】先用Floyd求出最短路，把最短路上的邊加到網絡流中，這樣就保證了從s->t的一個流一定是一條最短路，也就保證了網絡流建模的正確性。 【找最短路上的邊】 滿足最優子結構的性質：(i, j)是最短路上的邊，當且僅當dist[s][i] + edge[i][j] + dist[j][t] = dist[s][t]. 一開始想的是滿足dist[s][j] = dist[s][i] + edge[i][j]就行了，不過這顯然是不對的。這只滿足了i點到s點是最短路，卻不能保證j點到t點也是最短路，自然也保證不了(i, j)是最短路上的邊。 【代碼】http://paste.ubuntu.com/5887014/

轉載于:https://www.cnblogs.com/AbandonZHANG/p/4114261.html

總結

以上是生活随笔為你收集整理的ZOJ 2760 How Many Shortest Path (不相交的最短路径个数)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。