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

看板Grad-ProbAsk作者 (monster710623)時間5年前 (2020/01/10 14:59), 5年前編輯推噓12(12推 0噓 19→)
留言31則, 9人參與, 5年前最新討論串1/1
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
→
01/10 15:06, 5年前 , 1F
找最小瓶頸路徑吧
01/10 15:06, 1F
→
01/10 15:13, 5年前 , 2F
從s出發 每次都只走weight最小的邊就是最小瓶頸路
01/10 15:13, 2F
→
01/10 15:16, 5年前 , 3F
好像不是這樣 還是等大神來回答好了
01/10 15:16, 3F
可是weight那邊好像是max誒 ※ 編輯: ching4562 (1.167.52.251 臺灣), 01/10/2020 15:18:35
→
01/10 15:20, 5年前 , 4F
對啊 那條路上權重最大的邊就是瓶頸
01/10 15:20, 4F
→
01/10 15:20, 5年前 , 5F
這問題應該等價於最大流問題 都在找最小瓶頸
01/10 15:20, 5F
推
01/10 15:27, 5年前 , 6F
shortest path吧
01/10 15:27, 6F
→
01/10 15:30, 5年前 , 7F
啊 不對
01/10 15:30, 7F
→
01/10 15:34, 5年前 , 8F
critical path /work
01/10 15:34, 8F
推
01/10 18:12, 5年前 , 9F
的確是longest path定義，對過楓葉本定義了
01/10 18:12, 9F
推
01/10 18:16, 5年前 , 10F
按照這個邏輯的話，只差驗證解Dijkstra的instance為什
01/10 18:16, 10F
→
01/10 18:16, 5年前 , 11F
麼不能拿DP解，E的time complexity比c大，所以ineffic
01/10 18:16, 11F
→
01/10 18:16, 5年前 , 12F
ient
01/10 18:16, 12F
→
01/10 18:38, 5年前 , 13F
等等我看錯了，怎麼又max又smallest
01/10 18:38, 13F
推
01/10 18:48, 5年前 , 14F
應該是bottle neck 但不知道min bottleneck tree生出來的
01/10 18:48, 14F
→
01/10 18:48, 5年前 , 15F
tree是不是bottleneck path
01/10 18:48, 15F
推
01/10 19:02, 5年前 , 16F
這是minimax path 可用Dijk修改relex function求得=>g
01/10 19:02, 16F
→
01/10 19:02, 5年前 , 17F
reedy
01/10 19:02, 17F
所以這類minimax path問題是要求什麼啊 ※ 編輯: ching4562 (219.91.74.143 臺灣), 01/10/2020 21:43:26 ※ 編輯: ching4562 (219.91.74.143 臺灣), 01/10/2020 21:50:54
→
01/10 22:34, 5年前 , 18F
01/10 22:34, 18F
推
01/10 22:58, 5年前 , 19F
01/10 22:58, 19F
推
01/10 23:30, 5年前 , 20F
感謝樓上大大用心翻譯XD
01/10 23:30, 20F
推
01/11 00:10, 5年前 , 21F
再請教一下 這樣bottleneck path是不是反過來定義就好了
01/11 00:10, 21F
→
01/11 00:10, 5年前 , 22F
？
01/11 00:10, 22F
→
01/11 00:10, 5年前 , 23F
用題目的定義方法的話就是W(P)=min_i=0~k-1{(wi,wi+1)}
01/11 00:10, 23F
→
01/11 00:10, 5年前 , 24F
求max W(P)這樣？
01/11 00:10, 24F
推
01/11 00:30, 5年前 , 25F
回樓上 對的 maximin path 就是 bottleneck path
01/11 00:30, 25F
推
01/11 08:31, 5年前 , 26F
感謝j大大
01/11 08:31, 26F
感謝樓上各位大神 ※ 編輯: ching4562 (1.200.202.223 臺灣), 01/11/2020 08:36:40
→
01/11 19:41, 5年前 , 27F
不就只是找path上最大的edge嗎
01/11 19:41, 27F
→
01/11 20:41, 5年前 , 28F
這題應該是用MST來解
01/11 20:41, 28F
推
01/11 21:05, 5年前 , 29F
回樓上 要用MST也沒錯 minimax path可以在兩點間的MST
01/11 21:05, 29F
→
01/11 21:05, 5年前 , 30F
找到 但這題不是在找MST 也不是edge 他是找path
01/11 21:05, 30F
推
01/12 06:53, 5年前 , 31F
先找 MST 這樣任兩點間就可以在 MST 上有 path 了
01/12 06:53, 31F
‣ 更多 ching4562 的文章
文章代碼(AID): #1U623VZK (Grad-ProbAsk)