作者tank123zzz (哇呼呼)
看板Grad-ProbAsk
標題Re: [理工] 交大101資演
時間Fri Jan 10 22:57:55 2020
※ 引述《justlike68 (DAY)》之銘言：
: 大家晚安
: 有幾題資演想請教~
: 20.
: (58)
: http://i.imgur.com/TShP2Xu.jpg
: 想問(58)題的C為什麼是對的呢?
: Ford-Fulkerson複雜度不是|f*|E嗎，應該跟capacity無關?
: 19.
: http://i.imgur.com/O2UOidz.jpg
: http://i.imgur.com/71MWKtm.jpg
: 想問的是
: promblem1是在說哪個問題?
: problem2是TSP嗎?(TSP可以讓每條邊加權值是1?)
: problem3是LP嗎?(LP可以讓每條邊加權值是1?)
: (57)的D是什麼詭異的敘述!?不知道怎麼問，但就是...想問xd
: 17.
: (51)
: http://i.imgur.com/InGHWGN.jpg
: 這題也是很詭異，怎麼看出他可以化成D選項的呢?
: (E)又是哪裡錯?為什麼無法表示全部?
: 先謝謝各位了~祝大家考試順利
: -----
: Sent from JPTT on my Samsung SM-J710GN.
想問一下55-57的那個題組的problem 2
為什麼是shortest path呢
選項還說可以用floyd解
可是他要求visit exactly once
這樣floyd能解嗎？
-----
Sent from JPTT on my Sony G3426.
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.255.127.115 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1578668277.A.987.html
→ DLHZ: shortest path還會visit兩次嗎? 01/10 23:03
因為想說p3說at most once
exactly once 不是所有點都要一次的意思嗎
※ 編輯: tank123zzz (111.255.127.115 臺灣), 01/10/2020 23:12:21
※ 編輯: tank123zzz (111.255.127.115 臺灣), 01/10/2020 23:12:42
→ cry589036511: 最短路徑一定最多經過各點一次，exactly once代表 01/10 23:46
→ cry589036511: 圖上要有hp才成立，所以可用floyd找是否有長度v-1 01/10 23:46
→ cry589036511: 路徑存在 01/10 23:46
→ DLHZ: 喔喔看錯了 他的exactly once指的是經過的點 而不是所有點 01/10 23:51
→ DLHZ: 就是有沒有長度為K的simple path 01/10 23:54
好的 感謝兩位
※ 編輯: tank123zzz (101.12.44.191 臺灣), 01/11/2020 10:13:16