推 cshcsh6847: 58. 就算每個flow 都不同capacity 也不一定切集唯一 01/24 15:13
→ cshcsh6847: （可能 2,5 3,4 這樣 也是一樣的結果） 01/24 15:13
→ cshcsh6847: 59.應該也是同理 01/24 15:13
推 cshcsh6847: 60. 不一定要是整數？ 以上是我的看法啦 歡迎強者糾 01/24 15:16
→ cshcsh6847: 正！ 01/24 15:16
推 Transfat: 60題integral是積分ㄟ,我懷疑他是想打integer 01/24 15:17
→ Transfat: 要是整數吧，每條邊的capacity都是1的話 01/24 15:18
→ w181496: 60簡單舉個反例 兩個都最大流 01/24 15:28
推 hut326521: 如果容量不是整數的話 最大流也不用是整數吧 01/24 15:31
→ yupog2003: integral也有整數的意思喔，再一次考英文XD 01/24 15:33
→ yupog2003: 60D我也有疑問，他是說corresponding flow network，也 01/24 15:36
→ yupog2003: 就是這個圖應該是從bipartite graph轉換過來的，感覺就 01/24 15:38
→ yupog2003: 會是integral，我找不到反例 01/24 15:38
→ yupog2003: 阿阿w大已經給反例了我都沒看到QQ感謝 01/24 15:40
→ yupog2003: 可是那個capacity不全為1耶... 01/24 15:41
→ yupog2003: 還是說這個轉換capacity也不一定要為1，只要一樣就好？ 01/24 15:42
→ w181496: 喔喔～對 我那例子應該要把邊權改1比較符合題意 不過改了 01/24 15:48
→ w181496: 反例還是成立XD 01/24 15:48
→ gouya: 可以參考林立宇那本P176 01/24 15:51
→ yupog2003: 嗯嗯，反例還是成立，這樣就ok了 01/24 15:52
推 Transfat: maximum-flow network不用要求每次都要流過最大可流過的 01/24 15:53
→ Transfat: 量嗎＠＠？ 01/24 15:53
→ yupog2003: 好像沒有這樣的要求，只是這樣子方便計算所以大家都直 01/24 16:03
→ yupog2003: 接給他一次流好留滿 01/24 16:03
→ w181496: 我那個例子好像有點不太對 重新構造一個明顯點的反例 01/24 16:13
推 joeboy: 應該是說你從圖轉過來，可是容量可以自己決定，看要整數 01/24 16:14
→ joeboy: 還是小數這樣吧？反正只要每條一樣就好？應該是這樣吧？ 01/24 16:14
推 kaofushwai: 順便問一下57的a哪裡對 01/24 17:45
→ joeboy: 講原來的圖轉成完全圖，原來的邊是1，不存在的是2，然後 01/24 17:55
→ joeboy: 找最短路徑 01/24 17:55
→ Gabino: 範嘛？ 01/24 19:09
→ joeboy: Sorry我看錯題目意思，不過他確實可以用floyd解決，找最 01/24 21:08
→ joeboy: 後的矩陣，然後看你給定的K是否存在矩陣裡面 01/24 21:08
→ Gabino: 那j大可以用Floyd示範一下怎解我上面的同一個例子嗎 01/24 21:12
→ Gabino: 感恩~~~ 01/24 21:12
推 yupog2003: 先用floyd找出all pairs shortest path 01/24 21:55
→ yupog2003: 然後窮舉所有可能的path，共n!個path 01/24 21:56
→ yupog2003: 假設其中一個path是1->2->3->4->5，檢查看看1->2、 01/24 21:56
→ yupog2003: 2->3、3->4、4->5，最短距離是否為1，如果是的話就找到 01/24 21:57
→ yupog2003: 了，阿如果不是的話再嘗試下一個可能的排列 01/24 21:58
→ yupog2003: 當然這樣子有點脫褲子放屁，每個edge的weight都已經是 01/24 21:59
→ yupog2003: 1了，幹麻還用floyd...不管，反正floyd可以拿來用就是 01/24 22:00
→ yupog2003: 了，只是用法很怪而已，如果今天每個edge的weight都不 01/24 22:00
→ yupog2003: 是1的話，就派的上用場 01/24 22:01
→ yupog2003: 好拉...我也覺得我在硬凹QQ 01/24 22:06
→ joeboy: 然後我剛剛有查了一下這題，大碩的老師是說你直接忽略那 01/24 22:45
→ joeboy: 個exactly單字，用at most來解這個 01/24 22:45