作者ching4562 (monster710623)
看板Grad-ProbAsk
標題[理工] 資演 交大101 第16題
時間Fri Jan 10 14:59:41 2020
https://i.imgur.com/lDGnQVK.jpg
問一下這題在做什麼啊
就我的理解好像是在找longest path 嗎?
然後為何46題是c
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.217.110.114 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1578639583.A.8D4.html
1F：→ cossetannie: 找最小瓶頸路徑吧01/10 15:06
2F：→ cossetannie: 從s出發 每次都只走weight最小的邊就是最小瓶頸路01/10 15:13
3F：→ cossetannie: 好像不是這樣 還是等大神來回答好了01/10 15:16
可是weight那邊好像是max誒
※ 編輯: ching4562 (1.167.52.251 臺灣), 01/10/2020 15:18:35
4F：→ cossetannie: 對啊 那條路上權重最大的邊就是瓶頸01/10 15:20
5F：→ cossetannie: 這問題應該等價於最大流問題 都在找最小瓶頸01/10 15:20
6F：推 zuchang: shortest path吧01/10 15:27
7F：→ zuchang: 啊 不對01/10 15:30
8F：→ zuchang: critical path /work01/10 15:34
9F：推 b10007034: 的確是longest path定義，對過楓葉本定義了01/10 18:12
10F：推 b10007034: 按照這個邏輯的話，只差驗證解Dijkstra的instance為什01/10 18:16
11F：→ b10007034: 麼不能拿DP解，E的time complexity比c大，所以ineffic01/10 18:16
12F：→ b10007034: ient01/10 18:16
13F：→ b10007034: 等等我看錯了，怎麼又max又smallest01/10 18:38
14F：推 mistel: 應該是bottle neck 但不知道min bottleneck tree生出來的01/10 18:48
15F：→ mistel: tree是不是bottleneck path01/10 18:48
16F：推 jeremyyuan: 這是minimax path 可用Dijk修改relex function求得=>g01/10 19:02
17F：→ jeremyyuan: reedy01/10 19:02
所以這類minimax path問題是要求什麼啊
※ 編輯: ching4562 (219.91.74.143 臺灣), 01/10/2020 21:43:26
※ 編輯: ching4562 (219.91.74.143 臺灣), 01/10/2020 21:50:54
20F：推 gash55025502: 感謝樓上大大用心翻譯XD01/10 23:30
21F：推 mistel: 再請教一下 這樣bottleneck path是不是反過來定義就好了01/11 00:10
22F：→ mistel: ？ 01/11 00:10
23F：→ mistel: 用題目的定義方法的話就是W(P)=min_i=0~k-1{(wi,wi+1)} 01/11 00:10
24F：→ mistel: 求max W(P)這樣？ 01/11 00:10
25F：推 jeremyyuan: 回樓上 對的 maximin path 就是 bottleneck path 01/11 00:30
26F：推 mistel: 感謝j大大 01/11 08:31
感謝樓上各位大神
※ 編輯: ching4562 (1.200.202.223 臺灣), 01/11/2020 08:36:40
27F：→ mathtsai: 不就只是找path上最大的edge嗎 01/11 19:41
28F：→ mathtsai: 這題應該是用MST來解 01/11 20:41
29F：推 jeremyyuan: 回樓上 要用MST也沒錯 minimax path可以在兩點間的MST 01/11 21:05
30F：→ jeremyyuan: 找到 但這題不是在找MST 也不是edge 他是找path 01/11 21:05
31F：推 FRAXIS: 先找 MST 這樣任兩點間就可以在 MST 上有 path 了 01/12 06:53