PKU3272-Cow Traffic

題目：http://poj.org/problem?id=3272
給一N(5000)點M(50000)邊的有向無環圖，點編號1...N
保證所有連結邊u->v都滿足u<v、可能有重邊、所有點都能走到點N
(所以，它也是個弱連通圖)

入度為0的點是起點，編號N是終點
問從起點走到終點的所有路徑中，「被經過最多次的邊」被經過了幾次？



程式碼：codepad掛了，待補
Hint有點怪怪的，讓人誤解成「起點到終點有幾種走法」
但是實際上「起點到點x有幾種走法」卻是這題的關鍵
首先「起點到點x有幾種走法」這個DP[x]的求法
由於題目已經保證u<v、N只有5000可以開鄰接矩陣，這個表格非常容易求

那麼什麼才是一條邊u->v被經過的次數呢？
答案就是「起點走到u的方法數」×「v走到終點的方法數」

於是乎再把所有邊反向過來，求取DP_[x]
然後逐一檢查所有邊的DP[u]*DP_[v]哪個最大就可以了

這道題目如果把N和M改到十萬級、把圖改成任意有向無環圖
就變成一道考驗coding技術/細節考慮的好題目了