[理工]交大101資演59, 60
59.Which statement is wrong for a flow networkG=(V,E)?
(D)If all edges of G have different capacities, then there exists a unique flow f that gives the maximum flow.
(E)The capacity of each edge of G can be any non-negative number.
60.Let G=(V, E) be a bipartite graph, where V = L union R. Which statement is wrong about finding a maximum bipartite matching?
(C)The capacity of each edge in the corresponding flow network is set to 1.
(D)The maximum flow of the corresponding flow network is always integral and the flow value each edge is integral as well.
兩題給的答案皆是D，但是59的D為何錯呢？而60的D敘述問題在哪，因為用max flow的演算法那這樣應該每次皆要填滿s到t的path中之最小edge的weight，因此會是1吧？
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.99
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1486521641.A.458.html
→
02/08 10:42, , 1F
02/08 10:42, 1F
→
02/08 10:50, , 2F
02/08 10:50, 2F
推
02/08 10:50, , 3F
02/08 10:50, 3F
→
02/08 10:51, , 4F
02/08 10:51, 4F
懂了！我一直不太了解題意的flow不唯一代表什麼，原來是有相同max flow不同的流法之義，感謝！，
推
02/08 10:55, , 5F
02/08 10:55, 5F
考前竟然還有這個觀念沒有釐清orz，我一直被max flow的code中每次取path中的minial weighted edge混淆了，感謝！！！
※ 編輯: ssssIssss (140.112.25.99), 02/08/2017 11:19:03