作者joeboy (揪立)
看板Grad-ProbAsk
標題[理工] 101交大資演
時間Wed Jan 25 22:54:42 2017
http://i.imgur.com/B82S6aJ.jpg
想問一下愛為什麼最後一題的c錯
B選項如果我的cut不是min cut那他的flow不就不是最大嗎
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.136.182.68
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1485356084.A.FC6.html
1F：推 gary19941208: B.如果不是min cut那就會大於f了C.cut數量應該不只O 01/25 23:00
2F：→ gary19941208: (n)個 01/25 23:00
3F：→ joeboy: B選項的f沒有說是最大流吧？ 01/25 23:09
4F：→ gary19941208: cut值大於等於flow值，等於成立於min cut max flow 01/25 23:25
5F：推 kyuudonut: 你的陳述有矛盾 最大流量僅能滿足min cut 01/25 23:27
6F：→ kyuudonut: 又怎麼能滿足比min cut更大的cut? 01/25 23:27
7F：推 Astar5566: 所以b應該是錯的吧？ 可能比最大流還要大 01/25 23:41
8F：→ gary19941208: B是對的，因為他已經寫等於了，那就是max flow 01/26 08:17
9F：推 yupog2003: 任何cut的capacity值確實可能比max flow大，但是當某個 01/26 08:36
10F：→ yupog2003: cut的capacity值跟flow相同時，代表這個cut已經無法容 01/26 08:37
11F：→ yupog2003: 納更多flow流過去了，所以任何從source跑出來的流量跑 01/26 08:37
12F：→ yupog2003: 到這個cut一定會被卡住，所以這個flow一定就是max flow 01/26 08:38
13F：→ yupog2003: 沒錯 01/26 08:39
14F：→ yupog2003: 此時這個cut就會是minimum cut 01/26 08:40
15F：→ yupog2003: 我一開始也是被min cut的字義上給混淆了，也覺得cut 01/26 08:42
16F：→ yupog2003: 不是min cut那個flow就不是max flow，但是當該flow等於 01/26 08:43
17F：→ yupog2003: 某個cut的capacity時，那個cut就會成為min cut了 01/26 08:43