作者DJWS (...)
看板Prob_Solve
标题Re: [问题] approximation
时间Tue Apr 3 22:22:02 2012
※ 引述《wsx02 ()》之铭言：
: http://ppt.cc/_7PH
: 这是交大研究所的考题 不是作业0.0
: 这题我找了一些答案
: 想跟大大确认一下答案
: (6) O(|E| * (|E|+|V|)) 或
: O(|V| * (|E|+|V|))
: 不知道哪个是正确的..
照字面看 每次V点可选，运气不好又重复选 O(无限大)
最普通的 每次V点可选，检查边需要E，总共要选V点 O(VVE)
强一点的 选过的点永不再选，检查边需要E，总共要选V点 O(VE)
最强的 如果一开始先把两点之间多重的edge拼起来 O(VV)
不知道考官喜欢哪一种......
: (7) 1/2 或
: |E|/2
: 不知道应该填哪一个
E
运气好的时候可以找到正解
运气好是什麽时候呢？ 正解最大会是多少呢？
例如下面那题的完全二分图 :p
: (8) 找到的是2n^2 可是不是很确定
: 谢谢
完全二分图(X,Y)一定可以找到正解
抓一个点过去 ---> a. 与X同侧: 边数为零，不会增加边，所以最後啥都没做
b. 与Y同侧: 因为是完全图，一定会增加边
所以答案就是 K(2n, 2n) 的边数 2n * 2n = 4nn
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.230.125.83
※ 编辑: DJWS 来自: 61.230.125.83 (04/03 22:32)
1F：推 wsx02:谢谢 04/04 11:50
2F：推 yamaimo:每移动1个点,S,T之间的边数至少增加1,最多只需要移动|E| 04/07 18:31
3F：→ yamaimo:O(|E|*(|V|+|E|))可解决。 04/07 18:37