[理工] 102 台大資工 資演 對答案

看板Grad-ProbAsk作者 (大蜘蛛)時間12年前 (2014/02/04 19:22), 編輯推噓8(8推 0噓 23→)
留言31則, 8人參與, 最新討論串1/1
題目 http://exam.lib.ntu.edu.tw/sites/default/files/exam/graduate/102/102415.pdf 我寫的答案 http://imgur.com/UsVP373
http://imgur.com/SyS1jFu
http://imgur.com/faf781n
http://imgur.com/CuzDREj
手邊沒有答案 跟大家對個答案 然後 .. 第六題不知怎麼的變成一個環了 不知道有沒有關係 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 1.165.113.190
→
02/04 21:56, , 1F
第六題 minimum cut 值應該跟 maximum flow 一樣吧?
02/04 21:56, 1F
→
02/04 21:57, , 2F
我畫的residual network 跟你一樣 所以答案應該是 28
02/04 21:57, 2F
→
02/04 22:38, , 3F
請問要怎麼切 可以得到28呢？
02/04 22:38, 3F
→
02/06 11:49, , 4F
你切過的邊 4 還有 15不可以加進去 所以應該是28 大概吧..
02/06 11:49, 4F
→
02/06 17:30, , 5F
Cormen解釋the value of max flow is equal to the
02/06 17:30, 5F
→
02/06 17:30, , 6F
capacity of the min cut你切法對 但4,15不應該算進去
02/06 17:30, 6F
→
02/06 19:37, , 7F
請問一下要如何判斷 哪個邊要算 哪個邊不要算呢 ?
02/06 19:37, 7F
→
02/06 19:38, , 8F
不懂為什麼 4,15 可以不用算 ？
02/06 19:38, 8F
→
02/06 20:16, , 9F
假設cut(S,T) 左下是S集 右上是T集 必須要滿足(u,v)
02/06 20:16, 9F
→
02/06 20:17, , 10F
u屬於S v屬於T 要(u,v)才可加進去 至於為什麼max flow
02/06 20:17, 10F
→
02/06 20:17, , 11F
=min cut相關證明很複雜 印象中記得cormen花3.4頁證
02/06 20:17, 11F
→
02/06 20:17, , 12F
有興趣可以去看…
02/06 20:17, 12F
→
02/06 20:28, , 13F
所以是要轉回原本的圖去看 (u,v) ? 看了發現是 28
02/06 20:28, 13F
→
02/06 20:29, , 14F
看來不能在最後的圖看流量... 感謝 kiki 大 <(_ _)>
02/06 20:29, 14F
推
02/07 17:45, , 15F
在你第六題解答的圖, 從s當起點出發, S就是蒐集s可達點
02/07 17:45, 15F
→
02/07 17:48, , 16F
剩下點就是T, 把S上的點到T上的點之edge 容量全加總
02/07 17:48, 16F
→
02/07 17:49, , 17F
只有10 8 10 是S到T的edge
02/07 17:49, 17F
→
02/07 21:39, , 18F
謝謝大大_φ(･_･
02/07 21:39, 18F
推
02/21 20:17, , 19F
3(c)猜ii,iv,v，5(a) x.rank>y.rank，x.rank==y.rank，
02/21 20:17, 19F
→
02/21 20:18, , 20F
return Find-set (x.parent)
02/21 20:18, 20F
→
02/25 19:35, , 21F
請問 3.(c) iii,iv,v 要怎麼判斷呢 ？
02/25 19:35, 21F
→
02/26 10:42, , 22F
我是代例子耶，如果最大小於兩倍最小，應該都會是fixed
02/26 10:42, 22F
推
02/27 15:22, , 23F
請問怎麼代例子呢? 謝謝><
02/27 15:22, 23F
推
02/28 08:53, , 24F
3、3、3、5，3、3、3、7，3、3、3、3，這三個建Huffman
02/28 08:53, 24F
→
02/28 08:54, , 25F
建完會有一點點感覺，個人見解啦XD，說不定我錯
02/28 08:54, 25F
推
02/03 14:36, , 26F
3.(a)答案在此 http://bit.ly/1z96kHO
02/03 14:36, 26F
推
02/03 14:49, , 27F
3.(c)應該是ii,iv,v 答案在此http://bit.ly/1DzF6Kf
02/03 14:49, 27F
推
02/03 14:58, , 28F
6. min-cut 切10-4-8-15-10的邊 只算源區到匯區的邊,
02/03 14:58, 28F
→
02/03 14:59, , 29F
也就是 10+8+10(都是源-->匯)=28
02/03 14:59, 29F
→
02/03 15:02, , 30F
這是min-cut的定義 可以看這http://bit.ly/1z9b4NS
02/03 15:02, 30F
推
02/03 15:07, , 31F
7.NPC證明,看http://bit.ly/1z9bDr0 第12頁 大家加油
02/03 15:07, 31F
‣ 更多 olderbrother 的文章
文章代碼(AID): #1IyCsC6G (Grad-ProbAsk)