[理工] [資結演算]99交大

[Austin9 (奧斯丁)]

There exists a polynomial time algorithm that finds the value of an s-t
minimum cut in a directed graph.

請問這題答案是對的還是錯的啊？強者朋友的答案是true，但交大給的答案是false，
所以我迷糊了....有人可以教一嗎？謝謝。

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 61.62.150.108
→ privatewind:true是基於flow 不過他只給directed gragh 所以gg
推 FRAXIS:差別是在哪？ 不能在directed graph上用flow?
→ privatewind:一個圖要稱之為flow 有他的條件呀
→ privatewind:如s的in degree=0 t的outdegree=0
→ privatewind:不過我自己也是從答案去猜的就是了0.0
推 FRAXIS:題目應該是給你一個有向圖和s及t 要找s-t的Min Cut
→ FRAXIS:可以把這個有向圖稍作修改 然後再執行flow 不就可以了？
推 dy957:這題答案交大不是給TRUE嗎@@??
推 dacvidania:交大答案明明就給TRUE 哪裡gg了??
→ dacvidania:這選項假如是FALSE 那20題就沒答案了
→ privatewind:是喔 那我錯哩 抱歉
→ Austin9:不好意思，應該是我抄錯答案了~o_o我又對了一下，發現交大
→ Austin9:給的是True，我抄成B，自己是寫d所以想很久，搞不清！
→ sneak: 這選項假如是FALSE https://daxiv.com