2012年1月29日 星期日

PKU2455-Secret Milking Machine

題目:http://poj.org/problem?id=2455
無向帶權圖有N(200)個點M(40000)條邊,現在想找出T條從點1到達點N的路徑
並且這T條路徑使用的邊不可重複
單個邊的路程越長的話,FJ的行跡也越容易暴露
找出T條夠秘密的路徑讓最長的那條路長度最短、報告這個長度


程式碼:(待補)
網路流又要二分答案的題目太多,這題也很容易就被看出來
惟時限稍微緊了點
單純的SAP會超時,補上GAP優化就能266ms通過

沒有留言:

張貼留言