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

看板Grad-ProbAsk作者 (奧斯丁)時間15年前 (2011/01/15 00:38), 編輯推噓4(4推 0噓 10→)
留言14則, 6人參與, 最新討論串2/2 (看更多)
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
→
01/15 06:04, , 1F
true是基於flow 不過他只給directed gragh 所以gg
01/15 06:04, 1F
推
01/15 06:55, , 2F
差別是在哪？ 不能在directed graph上用flow?
01/15 06:55, 2F
→
01/15 07:10, , 3F
一個圖要稱之為flow 有他的條件呀
01/15 07:10, 3F
→
01/15 07:12, , 4F
如s的in degree=0 t的outdegree=0
01/15 07:12, 4F
→
01/15 07:13, , 5F
不過我自己也是從答案去猜的就是了0.0
01/15 07:13, 5F
推
01/15 09:25, , 6F
題目應該是給你一個有向圖和s及t 要找s-t的Min Cut
01/15 09:25, 6F
→
01/15 09:26, , 7F
可以把這個有向圖稍作修改 然後再執行flow 不就可以了？
01/15 09:26, 7F
推
01/15 13:11, , 8F
這題答案交大不是給TRUE嗎@@??
01/15 13:11, 8F
推
01/15 23:09, , 9F
交大答案明明就給TRUE 哪裡gg了??
01/15 23:09, 9F
→
01/15 23:22, , 10F
這選項假如是FALSE 那20題就沒答案了
01/15 23:22, 10F
→
01/16 09:46, , 11F
是喔 那我錯哩 抱歉
01/16 09:46, 11F
→
01/17 00:04, , 12F
不好意思，應該是我抄錯答案了~o_o我又對了一下，發現交大
01/17 00:04, 12F
→
01/17 00:05, , 13F
給的是True，我抄成B，自己是寫d所以想很久，搞不清！
01/17 00:05, 13F
→
09/11 14:09, , 14F
這選項假如是FALSE https://daxiv.com
09/11 14:09, 14F
‣ 更多 Austin9 的文章
文章代碼(AID): #1DC7mMCR (Grad-ProbAsk)
‣ 更多 Austin9 的文章
文章代碼(AID): #1DC7mMCR (Grad-ProbAsk)