[理工] 資工 MST的問題

看板Grad-ProbAsk作者 (洛克人)時間10年前 (2014/02/18 11:31), 編輯推噓7(7推 0噓 50→)
留言57則, 8人參與, 最新討論串1/1
請問double MST的每個edge 原本某個MST的edge (u, v) 會屬在新的 MST嗎 好像前幾天的題目 忘了正確是什麼了 謝謝 -- Sent from my Android -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.114.74.159
→
02/18 12:38, , 1F
True
02/18 12:38, 1F
→
02/18 12:42, , 2F
好像是清大?我寫T記得好像還有一題考類似shorted path
02/18 12:42, 2F
→
02/18 12:42, , 3F
問path是否一樣 那題我寫F
02/18 12:42, 3F
→
02/18 12:44, , 4F
如果本來的spanning tree 權重小於MST的權重，兩倍後還
02/18 12:44, 4F
→
02/18 12:44, , 5F
是小於MST
02/18 12:44, 5F
→
02/18 12:45, , 6F
Path那題我也寫False，好像常看到
02/18 12:45, 6F
推
02/18 12:55, , 7F
是交大11.d?我寫T說。 GG了
02/18 12:55, 7F
→
02/18 13:05, , 8F
為啥是false ?
02/18 13:05, 8F
→
02/18 13:23, , 9F
交大的吧 我寫T推一下應該就知了
02/18 13:23, 9F
→
02/18 13:25, , 10F
想問flow那題 每個capacity+1 mincut還會是同條嗎Q_Q
02/18 13:25, 10F
推
02/18 13:27, , 11F
我覺得不會。
02/18 13:27, 11F
→
02/18 13:31, , 12F
嗯…好吧XD
02/18 13:31, 12F
→
02/18 13:35, , 13F
仔細想想 shorted path應該是同一條耶 才對 應該是T==
02/18 13:35, 13F
→
02/18 13:35, , 14F
憑感覺寫太快 因為不等式關系 GG了
02/18 13:35, 14F
→
02/18 13:36, , 15F
double 那題我寫T 我記得是每譬edge 都加1 才會變false
02/18 13:36, 15F
→
02/18 13:36, , 16F
, capacity 那題我也寫false...
02/18 13:36, 16F
→
02/18 13:37, , 17F
但交大數學傷我好深 都到現在了我還是走不出陰影
02/18 13:37, 17F
→
02/18 13:41, , 18F
不用擔心，數學有我在下面墊著。
02/18 13:41, 18F
→
02/18 13:41, , 19F
拼台大吧我交大也沒希望 計系單選拿不到20分就對不下去
02/18 13:41, 19F
→
02/18 13:41, , 20F
了==2選1都猜錯 Fxxk 沒對多選和題組 離散也考爆
02/18 13:41, 20F
→
02/18 13:42, , 21F
Ki大是說double那題嗎 我寫T 兩邊同乘2可以消掉吧…
02/18 13:42, 21F
→
02/18 13:42, , 22F
我是這樣解釋
02/18 13:42, 22F
→
02/18 13:44, , 23F
Path嗎?寫T的 應該都是對的 因為不等式relax關係
02/18 13:44, 23F
→
02/18 13:44, , 24F
……數學都在比爛嗎 只能說我數學也爆了XD
02/18 13:44, 24F
→
02/18 13:46, , 25F
考卷c.F d.T 這樣
02/18 13:46, 25F
→
02/18 14:20, , 26F
我以為是11.c
02/18 14:20, 26F
推
02/18 14:45, , 27F
shortest path不會同一條，本來a到b走四段長度一跟一
02/18 14:45, 27F
→
02/18 14:45, , 28F
段長度三，兩倍後會變成走一段長度六比較短
02/18 14:45, 28F
→
02/18 14:47, , 29F
交大數學完全崩潰，計系單選對三錯五但有5x,ds基本題
02/18 14:47, 29F
→
02/18 14:47, , 30F
好幾題錯了QQ
02/18 14:47, 30F
→
02/18 14:49, , 31F
一開始走3比走四個1還要短吧，還是我誤會你的意思？
02/18 14:49, 31F
→
02/18 14:57, , 32F
d[u,w]+d[w,v]<d[u,v] 小於改大於 乘兩倍都可以互相
02/18 14:57, 32F
→
02/18 14:57, , 33F
抵消吧 shortest path依然同條啊
02/18 14:57, 33F
→
02/18 15:00, , 34F
washfreeid應該是想成每個edge都加1才會不一樣，都乘2
02/18 15:00, 34F
→
02/18 15:00, , 35F
還是一樣
02/18 15:00, 35F
→
02/18 15:02, , 36F
話說booth那題64bit 會給對嗎……
02/18 15:02, 36F
→
02/18 15:06, , 37F
如果有人去申訴應該要給吧
02/18 15:06, 37F
→
02/18 15:08, , 38F
就怕大家都以為有人會去 結果沒人去…手邊沒原文所以
02/18 15:08, 38F
→
02/18 15:08, , 39F
沒辦法弄囧
02/18 15:08, 39F
推
02/18 15:12, , 40F
我打錯了，是加一不同，兩倍同，sor
02/18 15:12, 40F
→
02/18 15:12, , 41F
我好像是寫32bit 但想想發現64bit也可以作32bit啊 都填
02/18 15:12, 41F
→
02/18 15:12, , 42F
0不就好 感覺是陷阱 給分不太大…QQ不管了derder
02/18 15:12, 42F
→
02/18 15:15, , 43F
我還是覺得怪怪der 因為product只能用到左半部32bit 6
02/18 15:15, 43F
→
02/18 15:15, , 44F
4bit會弄到整個product吧@@
02/18 15:15, 44F
→
02/18 15:24, , 45F
那下面那題呢？BE都很怪。
02/18 15:24, 45F
→
02/18 15:26, , 46F
不知耶 我有寫對…e錯在哪啊？
02/18 15:26, 46F
→
02/18 15:28, , 47F
stall如果把後面的都清掉，那裡來資料給stall的
02/18 15:28, 47F
→
02/18 15:31, , 48F
我自己解讀的意思是lu偵測到了 所以要把next stage的c
02/18 15:31, 48F
→
02/18 15:31, , 49F
ontrol signal全設為0 我記得lu hazard有這個步驟@@
02/18 15:31, 49F
→
02/18 15:42, , 50F
計組有問題的張凡會弄吧
02/18 15:42, 50F
→
02/18 15:45, , 51F
反正都考完了 準備下間卡實在 不要忘了還有台大成大啊
02/18 15:45, 51F
→
02/18 15:45, , 52F
尤其台大計系 那科才較猛…
02/18 15:45, 52F
→
02/18 15:48, , 53F
為了台大計系 我已開始增強英文閱測能力
02/18 15:48, 53F
→
02/18 15:51, , 54F
還在放鬆中 XDD
02/18 15:51, 54F
推
02/18 15:54, , 55F
再兩個禮拜解脫了 ~~
02/18 15:54, 55F
推
02/18 16:02, , 56F
覺得難過
02/18 16:02, 56F
推
02/18 16:33, , 57F
問path：F ，問MST：T
02/18 16:33, 57F
‣ 更多 tkurockman 的文章
文章代碼(AID): #1J0jFz5_ (Grad-ProbAsk)