[理工] 資演交大101 第16題 ching4562 PTT批踢踢實業坊

作者: ching4562 (monster710623) 2020-01-10 14:59:41

https://i.imgur.com/lDGnQVK.jpg
問一下這題在做什麼啊
就我的理解好像是在找longest path 嗎?
然後為何46題是c

作者: cossetannie (paa) 2020-01-10 15:06:00

找最小瓶頸路徑吧從s出發每次都只走weight最小的邊就是最小瓶頸路好像不是這樣還是等大神來回答好了對啊那條路上權重最大的邊就是瓶頸這問題應該等價於最大流問題都在找最小瓶頸

作者: zuchang (chang) 2020-01-10 15:27:00

shortest path吧啊不對critical path /work

作者: b10007034 (Warren) 2020-01-10 18:12:00

的確是longest path定義，對過楓葉本定義了按照這個邏輯的話，只差驗證解Dijkstra的instance為什麼不能拿DP解，E的time complexity比c大，所以inefficient等等我看錯了，怎麼又max又smallest

作者: mistel (Mistel) 2020-01-10 18:48:00

應該是bottle neck 但不知道min bottleneck tree生出來的tree是不是bottleneck path

作者: jeremyyuan (阿元) 2020-01-10 19:02:00

這是minimax path 可用Dijk修改relex function求得=>greedyhttps://reurl.cc/alKe1Y

作者: mi981027 (呱呱竹) 2020-01-10 22:58:00

作者: gash55025502 (白影弓) 2020-01-10 23:30:00

感謝樓上大大用心翻譯XD

作者: mistel (Mistel) 2020-01-11 00:10:00

再請教一下這樣bottleneck path是不是反過來定義就好了？用題目的定義方法的話就是W(P)=min_i=0~k-1{(wi,wi+1)}求max W(P)這樣？

作者: jeremyyuan (阿元) 2020-01-11 00:30:00

回樓上對的 maximin path 就是 bottleneck path

作者: mistel (Mistel) 2020-01-11 08:31:00

感謝j大大

作者: mathtsai (mathtsai) 2020-01-11 19:41:00

不就只是找path上最大的edge嗎這題應該是用MST來解

作者: jeremyyuan (阿元) 2020-01-11 21:05:00

回樓上要用MST也沒錯 minimax path可以在兩點間的MST找到但這題不是在找MST 也不是edge 他是找path

作者: FRAXIS (喔喔) 2020-01-12 06:53:00

先找 MST 這樣任兩點間就可以在 MST 上有 path 了

繼續閱讀