[資工][資演][交大][101 102]

看板Grad-ProbAsk作者qoojordon (穎川琦)時間11年前 (2015/01/15 21:39)推噓8(8推 0噓 15→)

留言23則, 10人參與討論串1/1

[交大102 第10題] http://ppt.cc/FWsa Line30: true Line32: pN->pNext Line43: cnt++; DFS(k); 謝謝kather提供想不到Line43要怎麼填 = =" 爬了一下前面好像沒討論到 [交大101 第四題組] http://ppt.cc/cC-s main跑完之後 data[3]應該是26吧? , 交大答案給60不懂為啥謝謝harryron9提供 , 答案沒錯 , 它的heapify沒有做到root [交大101 第16題組] 想問這題的 optimal path定義有特別和哪類型的問題相關嗎? 看起來不是shortest path , 題組後兩題大概是哪個方向的題目? 還是只是單純定義個東西出來魯小而以.... 謝謝FRAXIS提供關鍵字 , minimax problem , 依WIKI說法貌似greedy可解和 Dijkstra是親戚問題 [交大101 58小題(c)] T or F: If each edge has a different capacity, then there exists a unique minimun cut. 答案給F , 有反例嗎 ? ---- 謝謝大家看完~ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 59.115.95.138 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1421329167.A.9CB.html

推

shanbb

01/15 22:51, , 1^F

01/15 22:51, 1^F

推

FRAXIS

01/15 22:53, , 2^F

01/15 22:53, 2^F

→

kather

01/15 22:57, , 3^F

01/15 22:57, 3^F

→

kather

01/15 23:00, , 4^F

01/15 23:00, 4^F

推

qoozxc789

01/15 23:03, , 5^F

01/15 23:03, 5^F

→

qoozxc789

01/15 23:04, , 6^F

01/15 23:04, 6^F

→

kather

01/15 23:06, , 7^F

01/15 23:06, 7^F

→

qoozxc789

01/15 23:08, , 8^F

01/15 23:08, 8^F

→

qoojordon

01/15 23:09, , 9^F

01/15 23:09, 9^F

→

kather

01/15 23:09, , 10^F

01/15 23:09, 10^F

→

skellroyal

01/15 23:25, , 11^F

01/15 23:25, 11^F

→

shanbb

01/15 23:31, , 12^F

01/15 23:31, 12^F

→

harryron9

01/16 01:58, , 13^F

01/16 01:58, 13^F

→

harryron9

01/16 01:58, , 14^F

01/16 01:58, 14^F

先謝謝大家的討論,已將提供的解法補充於原文 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

01/16 08:39, , 15^F

01/16 08:39, 15^F