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