[理工] 交大 101 資演 最大流

看板Grad-ProbAsk作者 (一顆星5566)時間7年前 (2017/01/24 14:40), 編輯推噓8(8推 0噓 43→)
留言51則, 9人參與, 最新討論串1/1
http://i.imgur.com/SsvmSB0.jpg
第20大題答案是DDD 都是選錯的敘述 請問選項各是錯在哪裡 最大流好難 都看不太懂 感謝各位 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.137.27.198 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1485240037.A.2BC.html
推
01/24 15:13, , 1F
58. 就算每個flow 都不同capacity 也不一定切集唯一
01/24 15:13, 1F
→
01/24 15:13, , 2F
（可能 2,5 3,4 這樣 也是一樣的結果）
01/24 15:13, 2F
→
01/24 15:13, , 3F
59.應該也是同理
01/24 15:13, 3F
推
01/24 15:16, , 4F
60. 不一定要是整數？ 以上是我的看法啦 歡迎強者糾
01/24 15:16, 4F
→
01/24 15:16, , 5F
正！
01/24 15:16, 5F
推
01/24 15:17, , 6F
60題integral是積分ㄟ,我懷疑他是想打integer
01/24 15:17, 6F
→
01/24 15:18, , 7F
要是整數吧，每條邊的capacity都是1的話
01/24 15:18, 7F
→
01/24 15:28, , 8F
60簡單舉個反例 兩個都最大流
01/24 15:28, 8F
→
01/24 15:28, , 9F
01/24 15:28, 9F
推
01/24 15:31, , 10F
如果容量不是整數的話 最大流也不用是整數吧
01/24 15:31, 10F
→
01/24 15:33, , 11F
integral也有整數的意思喔，再一次考英文XD
01/24 15:33, 11F
→
01/24 15:36, , 12F
60D我也有疑問，他是說corresponding flow network，也
01/24 15:36, 12F
→
01/24 15:38, , 13F
就是這個圖應該是從bipartite graph轉換過來的，感覺就
01/24 15:38, 13F
→
01/24 15:38, , 14F
會是integral，我找不到反例
01/24 15:38, 14F
→
01/24 15:40, , 15F
阿阿w大已經給反例了我都沒看到QQ感謝
01/24 15:40, 15F
→
01/24 15:41, , 16F
可是那個capacity不全為1耶...
01/24 15:41, 16F
→
01/24 15:42, , 17F
還是說這個轉換capacity也不一定要為1，只要一樣就好？
01/24 15:42, 17F
→
01/24 15:48, , 18F
喔喔～對 我那例子應該要把邊權改1比較符合題意 不過改了
01/24 15:48, 18F
→
01/24 15:48, , 19F
反例還是成立XD
01/24 15:48, 19F
→
01/24 15:51, , 20F
可以參考林立宇那本P176
01/24 15:51, 20F
→
01/24 15:52, , 21F
嗯嗯，反例還是成立，這樣就ok了
01/24 15:52, 21F
推
01/24 15:53, , 22F
maximum-flow network不用要求每次都要流過最大可流過的
01/24 15:53, 22F
→
01/24 15:53, , 23F
量嗎＠＠？
01/24 15:53, 23F
→
01/24 16:03, , 24F
好像沒有這樣的要求，只是這樣子方便計算所以大家都直
01/24 16:03, 24F
→
01/24 16:03, , 25F
接給他一次流好留滿
01/24 16:03, 25F
→
01/24 16:13, , 26F
我那個例子好像有點不太對 重新構造一個明顯點的反例
01/24 16:13, 26F
→
01/24 16:13, , 27F
01/24 16:13, 27F
推
01/24 16:14, , 28F
應該是說你從圖轉過來，可是容量可以自己決定，看要整數
01/24 16:14, 28F
→
01/24 16:14, , 29F
還是小數這樣吧？反正只要每條一樣就好？應該是這樣吧？
01/24 16:14, 29F
推
01/24 17:45, , 30F
順便問一下57的a哪裡對
01/24 17:45, 30F
→
01/24 17:55, , 31F
講原來的圖轉成完全圖，原來的邊是1，不存在的是2，然後
01/24 17:55, 31F
→
01/24 17:55, , 32F
找最短路徑
01/24 17:55, 32F
→
01/24 19:09, , 33F
樓上可以用這個例子示
01/24 19:09, 33F
→
01/24 19:09, , 34F
範嘛？
01/24 19:09, 34F
→
01/24 21:08, , 35F
Sorry我看錯題目意思，不過他確實可以用floyd解決，找最
01/24 21:08, 35F
→
01/24 21:08, , 36F
後的矩陣，然後看你給定的K是否存在矩陣裡面
01/24 21:08, 36F
→
01/24 21:12, , 37F
那j大可以用Floyd示範一下怎解我上面的同一個例子嗎
01/24 21:12, 37F
→
01/24 21:12, , 38F
感恩~~~
01/24 21:12, 38F
推
01/24 21:55, , 39F
先用floyd找出all pairs shortest path
01/24 21:55, 39F
→
01/24 21:56, , 40F
然後窮舉所有可能的path，共n!個path
01/24 21:56, 40F
→
01/24 21:56, , 41F
假設其中一個path是1->2->3->4->5，檢查看看1->2、
01/24 21:56, 41F
→
01/24 21:57, , 42F
2->3、3->4、4->5，最短距離是否為1，如果是的話就找到
01/24 21:57, 42F
→
01/24 21:58, , 43F
了，阿如果不是的話再嘗試下一個可能的排列
01/24 21:58, 43F
→
01/24 21:59, , 44F
當然這樣子有點脫褲子放屁，每個edge的weight都已經是
01/24 21:59, 44F
→
01/24 22:00, , 45F
1了，幹麻還用floyd...不管，反正floyd可以拿來用就是
01/24 22:00, 45F
→
01/24 22:00, , 46F
了，只是用法很怪而已，如果今天每個edge的weight都不
01/24 22:00, 46F
→
01/24 22:01, , 47F
是1的話，就派的上用場
01/24 22:01, 47F
→
01/24 22:06, , 48F
好拉...我也覺得我在硬凹QQ
01/24 22:06, 48F
→
01/24 22:45, , 49F
01/24 22:45, 49F
→
01/24 22:45, , 50F
然後我剛剛有查了一下這題，大碩的老師是說你直接忽略那
01/24 22:45, 50F
→
01/24 22:45, , 51F
個exactly單字，用at most來解這個
01/24 22:45, 51F
‣ 更多 Astar5566 的文章
文章代碼(AID): #1OXlRbAy (Grad-ProbAsk)