[理工] 資演 交大101 第16題

[ching4562 (monster710623)]

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

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.217.110.114 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1578639583.A.8D4.html
→ cossetannie: 找最小瓶頸路徑吧
→ cossetannie: 從s出發 每次都只走weight最小的邊就是最小瓶頸路
→ cossetannie: 好像不是這樣 還是等大神來回答好了
可是weight那邊好像是max誒
※ 編輯: ching4562 (1.167.52.251 臺灣), 01/10/2020 15:18:35
→ cossetannie: 對啊 那條路上權重最大的邊就是瓶頸
→ cossetannie: 這問題應該等價於最大流問題 都在找最小瓶頸
推 zuchang: shortest path吧
→ zuchang: 啊 不對
→ zuchang: critical path /work
推 b10007034: 的確是longest path定義，對過楓葉本定義了
推 b10007034: 按照這個邏輯的話，只差驗證解Dijkstra的instance為什
→ b10007034: 麼不能拿DP解，E的time complexity比c大，所以ineffic
→ b10007034: ient
→ b10007034: 等等我看錯了，怎麼又max又smallest
推 mistel: 應該是bottle neck 但不知道min bottleneck tree生出來的
→ mistel: tree是不是bottleneck path
推 jeremyyuan: 這是minimax path 可用Dijk修改relex function求得=>g
→ jeremyyuan: reedy
所以這類minimax path問題是要求什麼啊
※ 編輯: ching4562 (219.91.74.143 臺灣), 01/10/2020 21:43:26
※ 編輯: ching4562 (219.91.74.143 臺灣), 01/10/2020 21:50:54
→ jeremyyuan: https://reurl.cc/alKe1Y
推 mi981027: https://i.imgur.com/DXDrICi.jpg
推 gash55025502: 感謝樓上大大用心翻譯XD
推 mistel: 再請教一下 這樣bottleneck path是不是反過來定義就好了
→ mistel: ？
→ mistel: 用題目的定義方法的話就是W(P)=min_i=0~k-1{(wi,wi+1)}
→ mistel: 求max W(P)這樣？
推 jeremyyuan: 回樓上 對的 maximin path 就是 bottleneck path
推 mistel: 感謝j大大
感謝樓上各位大神
※ 編輯: ching4562 (1.200.202.223 臺灣), 01/11/2020 08:36:40
→ mathtsai: 不就只是找path上最大的edge嗎
→ mathtsai: 這題應該是用MST來解
推 jeremyyuan: 回樓上 要用MST也沒錯 minimax path可以在兩點間的MST
→ jeremyyuan: 找到 但這題不是在找MST 也不是edge 他是找path
推 FRAXIS: 先找 MST 這樣任兩點間就可以在 MST 上有 path 了