推 shanbb: 16題組 floyd-warshall 01/15 22:51
推 FRAXIS: 16應該是bottleneck path吧.. 01/15 22:53
→ kather: cnt++;DFS(k) 01/15 22:57
→ kather: flow那題s→b兩條1,4;b→t兩條2,3 01/15 23:00
推 qoozxc789: cnt++;放那裏好像怎麼算都是N-1? 01/15 23:03
→ qoozxc789: *N 01/15 23:04
→ kather: 沒有visited才會加吧 01/15 23:06
→ qoozxc789: 上面那個loop已經把每個visited改false了不是嗎? 01/15 23:08
→ qoojordon: 上面那個loop 應該只是初始化,k大那個寫法應該是對的 01/15 23:09
→ kather: 所以後面的dfs會把路過的改成true 01/15 23:09
→ skellroyal: 同k大答案，把資料結構畫出來跑一遍會比較容易懂 01/15 23:25
→ shanbb: 可以在這邊偷問交大101年17題題組嗎QQ 01/15 23:31
→ harryron9: 101題組4 我是算60 注意的是data[0]從來沒被用過 01/16 01:58
→ harryron9: 有錯請指教 01/16 01:58
先謝謝大家的討論,已將提供的解法補充於原文
shanbb提到的題組17我已放棄,#1I-FaxPP這篇有kather提供的說明,
自己看起來是慢試出來der = ="
101 58(c)想問如果是SIMPLE GRAPH的話,同樣edge weight都unique,這樣cut會唯一嗎?
因為我自己都try 非multigraph的例子 , 思路如下:
a----- c --- p1 p1
s / \2 , s ~~~~~ t
\ b----- d-----t ~~~~~
\ /1p2 p2
\----e----
由s到t的flow因為edge weight都unique的關係,每條s→t的path都被唯一最小weight
的edge bounded,我想成是這條path的瓶頸
若path之間瓶頸相同,則可合併一起討論
如上圖,如果edge weight都是unique且是自然數,因為1,2恰為兩個最小的自然數
且剛好連著t,所以不管前面的weight是多少都無所謂,這兩根edge就決定了min cut在這裡了
把這種想法一般化, s->t的所有path的瓶頸相同者歸納為同一類,則min cut是所有瓶頸
edge的聯集,因為edge weight unique 所以這cut會唯一 , 不曉得這樣思考會不會有錯
-......-
※ 編輯: qoojordon (59.115.95.138), 01/16/2015 08:16:30
→ A4P8T6X9: 58 c 01/16 08:39
→ qoojordon: 謝謝，這樣我的盲點清楚惹 01/16 10:49
推 FRAXIS: 16 題組 minimax path problem 可以在Wikipedia上找到 01/17 02:15
→ FRAXIS: 線性時間可解 01/17 02:15
推 AgentSkye56: 想請問16題組47題 是五個點的完全圖嗎 01/17 18:57
推 AgentSkye56: 到底 OPTIMAL跟SHORTEST差在哪裡QQ 01/17 19:26
推 galapous: 推~今天做完這份有相同疑惑~感謝發問XD 01/19 20:34
回AgentSkye56:
依題目上的定義,我自己是解讀為 a到b的path中,weight最大的那根要最小
做法上應該是: 由A出發 , 一直走wight最小的edge , 直到碰到B為止
※ 編輯: qoojordon (59.115.67.222), 01/20/2015 07:37:16