作者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/cn.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