[UVA] 125 Numbering Paths

大概是中年痴呆，這題居然花了我一整天...

這是一道DP題，非常classic的Floyd-Warshall題。F-W非常適合求all pair relation，有sub problem的DP題。想法如下：

dp[ i ] [ j ] [ k ]:  所有點 i 到點 j ，只經過點 0 ~ k 的路徑總合 

那麼：

dp[ i ] [ j ] [ k + 1] = dp[ i ] [ j ] [ k ] + 點 i 到點 j ，必包含點 k + 1的路徑數量

點 i 到點 j ，必包含點 k + 1的路徑數量即為：dp[ i ] [ k + 1] [ k ] * dp[ k + 1] [ j ] [ k ]

重新整理程式碼，出忽意料的簡單：

 

for k 

   for i

      for j 

          dp[ i ][ j ] += dp[ i ][ k + 1] * dp[ k + 1][ j ]

第二步是要消除 cycle。一開始想不到如何判斷一個點有沒有在cycle上。後來google後了解，如果點 i 在cycle上，那麼 dp[ i ][ i ] 會大於0，因為點 i 會有不為0的input edge 跟 output edge。然後注意不為0 的dp[ i ] [ k ] 和 dp[ k ][ i ]也要標成 -1。