[理工] 清大資工計科 最後一題 reduction

看板Grad-ProbAsk作者 (18號)時間7年前 (2018/02/03 12:09), 7年前編輯推噓44(44推 0噓 20→)
留言64則, 26人參與, 7年前最新討論串1/1
題目是 將無向圖中 HC reduce 至 HP https://i.imgur.com/L9OH6L5.jpg
這樣轉換不知道可不可以？ 感覺好像可以又有點怪怪的 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.14.160.181 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1517630997.A.6F4.html
→
02/03 12:11, 7年前 , 1F
已爆炸 幹+365
02/03 12:11, 1F
推
02/03 12:13, 7年前 , 2F
tree 那題n是三小？ 感覺帶多少都可以
02/03 12:13, 2F
我算2
推
02/03 12:13, 7年前 , 3F
幹有講無向圖喔?
02/03 12:13, 3F
有 我本來也是寫有向 發現好像不太行
→
02/03 12:13, 7年前 , 4F
2
02/03 12:13, 4F
推
02/03 12:13, 7年前 , 5F
2
02/03 12:13, 5F
推
02/03 12:14, 7年前 , 6F
看到這題直接笑出來哈哈哈嗚嗚嗚…
02/03 12:14, 6F
推
02/03 12:16, 7年前 , 7F
我用接點拿邊的方式
02/03 12:16, 7F
求詳細 今年好多reduce
→
02/03 12:16, 7年前 , 8F
有人知道清大正取幾分嗎
02/03 12:16, 8F
→
02/03 12:17, 7年前 , 9F
或最低錄取
02/03 12:17, 9F
推
02/03 12:19, 7年前 , 10F
考幾分都是假的 是要看你能幹掉多少人
02/03 12:19, 10F
今年要幹掉1000人左右... ※ 編輯: can18 (101.14.160.181), 02/03/2018 12:20:20
推
02/03 12:28, 7年前 , 11F
到底怎麼算的 他也沒說n0有幾個
02/03 12:28, 11F
推
02/03 12:28, 7年前 , 12F
什麼什麼 n只有我算1嗎
02/03 12:28, 12F
→
02/03 12:29, 7年前 , 13F
n0不是就是degree=1唷？
02/03 12:29, 13F
推
02/03 12:30, 7年前 , 14F
Tree
02/03 12:30, 14F
推
02/03 12:32, 7年前 , 15F
E+1=V E=deg/2
02/03 12:32, 15F
推
02/03 12:33, 7年前 , 16F
分享一下 希格瑪deg=2e=11n , e=v-1, v=6n, e=6n-1, 12n-
02/03 12:33, 16F
→
02/03 12:33, 7年前 , 17F
2=11n, n=2
02/03 12:33, 17F
推
02/03 12:34, 7年前 , 18F
1-b怎麼解啊qq
02/03 12:34, 18F
我算1222 ※ 編輯: can18 (101.14.160.181), 02/03/2018 12:34:50
推
02/03 12:35, 7年前 , 19F
1-b我用高中的算法算XD
02/03 12:35, 19F
推
02/03 12:35, 7年前 , 20F
1~29分三堆 除3餘1 2 3的
02/03 12:35, 20F
算法跟s大一樣 s大答案跟我一樣嗎Q ※ 編輯: can18 (101.14.160.181), 02/03/2018 12:39:08
推
02/03 12:38, 7年前 , 21F
我算1224
02/03 12:38, 21F
幹我發現我加法加錯... 崩潰 ※ 編輯: can18 (101.14.160.181), 02/03/2018 12:40:31
推
02/03 12:40, 7年前 , 22F
1224...+1
02/03 12:40, 22F
推
02/03 12:41, 7年前 , 23F
我也是用餘數去算的 自己感覺蠻暴力
02/03 12:41, 23F
→
02/03 12:41, 7年前 , 24F
不知道有沒有其他方法
02/03 12:41, 24F
推
02/03 12:41, 7年前 , 25F
1224 +1
02/03 12:41, 25F
推
02/03 12:41, 7年前 , 26F
嗚嗚GG
02/03 12:41, 26F
推
02/03 12:45, 7年前 , 27F
1224+1
02/03 12:45, 27F
Gggggg
推
02/03 12:46, 7年前 , 28F
1224 +1
02/03 12:46, 28F
推
02/03 13:02, 7年前 , 29F
我的想法是G中隨意一個點複製一份(該點的鄰點和接邊)，然後
02/03 13:02, 29F
→
02/03 13:02, 7年前 , 30F
其中一個接邊到s另一個接邊到t
02/03 13:02, 30F
推
02/03 15:07, 7年前 , 31F
計系寫60分鐘就出來了 無壓力
02/03 15:07, 31F
推
02/03 15:20, 7年前 , 32F
計組好難喔
02/03 15:20, 32F
推
02/03 15:30, 7年前 , 33F
好多論述題 寫到手快斷掉
02/03 15:30, 33F
推
02/03 15:30, 7年前 , 34F
計系滿佛的
02/03 15:30, 34F
推
02/03 15:34, 7年前 , 35F
banker algo 那題p1失敗後跳到p3後是不是要再check p1
02/03 15:34, 35F
推
02/03 15:36, 7年前 , 36F
計系根本寫不完==
02/03 15:36, 36F
推
02/03 15:44, 7年前 , 37F
論述到沒時間惹qq
02/03 15:44, 37F
怎麼大家反應差那麼多XD
→
02/03 15:47, 7年前 , 38F
1b我一開始想窮舉找規律 舉幾個就放棄 第二次回來 用餘0
02/03 15:47, 38F
→
02/03 15:47, 7年前 , 39F
餘1 餘2 加到自己亂掉想驗算都不會==
02/03 15:47, 39F
往好處想我會算也算錯 QQ
推
02/03 15:51, 7年前 , 40F
三的倍數我算980耶
02/03 15:51, 40F
c9取3 + c10取3 + c10取3 + (10取1*10取1*9取1)
推
02/03 15:51, 7年前 , 41F
怎麼都沒公車…救命
02/03 15:51, 41F
推
02/03 15:53, 7年前 , 42F
1224+1
02/03 15:53, 42F
推
02/03 15:55, 7年前 , 43F
準備半天dp結果都考reduction啥鬼
02/03 15:55, 43F
→
02/03 15:59, 7年前 , 44F
02/03 15:59, 44F
J大請問 你要怎麼保證u,v在HC為相鄰點 有可能 u ~> w1~> v ~> w2 ~> u才能繞成一個cycle吧 (上面的圖) 這樣 x -> u ~> w1~> v ~> w2 無法接到 y 或是 x -> u ~> w1~> v -> y 不為 HP
推
02/03 16:43, 7年前 , 45F
那張圖是多找一個點連到所有點 所以所有情況都有考慮進去
02/03 16:43, 45F
→
02/03 16:51, 7年前 , 46F
太棒了 我餘一跟餘二都數錯個 讚讚
02/03 16:51, 46F
※ 編輯: can18 (101.14.160.181), 02/03/2018 16:58:43 ※ 編輯: can18 (101.14.160.181), 02/03/2018 17:01:14
→
02/03 17:01, 7年前 , 47F
上圖是將HC Prob. 轉成 HP Prob.
02/03 17:01, 47F
沒錯阿 可是要怎麼找u,v 你怎麼確定HC中u,v為相鄰 ※ 編輯: can18 (101.14.160.181), 02/03/2018 17:02:56
→
02/03 17:05, 7年前 , 48F
若上右圖能找到HP,則HP兩端必為xy.將上右圖回復成上左圖,H
02/03 17:05, 48F
→
02/03 17:05, 7年前 , 49F
P就可連成HC
02/03 17:05, 49F
→
02/03 17:07, 7年前 , 50F
找所有相鄰的uv.time=theta(|E|)=O(n^2)
02/03 17:07, 50F
→
02/03 17:09, 7年前 , 51F
找HP的演算法最多跑n^2次
02/03 17:09, 51F
了解了 要check多次
推
02/03 17:22, 7年前 , 52F
這題林立宇正課班NP後面有題台大103有類似的
02/03 17:22, 52F
推
02/03 17:41, 7年前 , 53F
我也是憑印象寫林立宇那題的解法，可是不確定印象有沒有
02/03 17:41, 53F
→
02/03 17:41, 7年前 , 54F
錯qq
02/03 17:41, 54F
推
02/03 17:52, 7年前 , 55F
如果HC轉HP,用把某兩點之邊去除
02/03 17:52, 55F
→
02/03 17:52, 7年前 , 56F
這種轉法可以嗎
02/03 17:52, 56F
估計不行 你去掉的邊不一定在HC中
推
02/03 17:55, 7年前 , 57F
我沒有外接額外的點
02/03 17:55, 57F
推
02/03 17:57, 7年前 , 58F
有道理
02/03 17:57, 58F
→
02/03 17:59, 7年前 , 59F
我回去翻課本看看QQ
02/03 17:59, 59F
如果是有向圖的話 將任一點split成Vin 及Vout即可
推
02/03 18:32, 7年前 , 60F
有向無向有差嗎?
02/03 18:32, 60F
有向將一點split成 Vin, Vout可以保證 : 若有HP Vout必為起點 Vin必為終點 此時將Vin Vout merge可得原圖的HC 但在無向split成V1 V2中無法保證為起終點 有可能 HP 為 (V1 ~> ... ~> V2 ~> ....) (所以我才又加了S,T 保證V1 V2他們是HP起點第2個及終點前2個 去掉S T就可merge回原圖的HC )
推
02/03 21:18, 7年前 , 61F
子嘉說過圖形證明絕對不能拆邊 只能加東西進去
02/03 21:18, 61F
那是用induction的時候吧 不過確實 拆邊會出現不知道要拆哪一個邊的問題
推
02/03 21:39, 7年前 , 62F
喔喔看懂了，原本是想說這個方法有向無向都可以用的意思
02/03 21:39, 62F
※ 編輯: can18 (1.173.124.34), 02/03/2018 21:49:09
推
02/03 22:42, 7年前 , 63F
講反了吧，是只能拆不能加
02/03 22:42, 63F
我也記得是 然後大多是拆點 ※ 編輯: can18 (1.173.124.34), 02/03/2018 23:07:39
推
02/03 23:39, 7年前 , 64F
http://tinyurl.com/yav5s643 Reduction from HC to HP
02/03 23:39, 64F
我的做法應該就是這個 https://i.imgur.com/2pG8lM7.jpg
※ 編輯: can18 (1.173.124.34), 02/04/2018 00:03:15
‣ 更多 can18 的文章
文章代碼(AID): #1QTJOLRq (Grad-ProbAsk)