作者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/cn.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