作者soheadsome (我是大帅哥)
看板Prob_Solve
标题[请益] 演算法作业的问题 (max weight subgraph)
时间Thu May 30 20:21:28 2013
因为期末要交project,
但题目看很久不知道该怎麽从哪下手,
google很久
只看到说可以转成prize-collecting Steiner tree
所以想请教大大们,可不可以给我一些提示
感谢
附题目ppt:
https://www.asuswebstorage.com/navigate/s/53DE46AEC6CD41C99D3A3CDAC7318B49Y
在网路上找到相关内容的ppt:
https://www.asuswebstorage.com/navigate/s/34D9CE30384C48759D2E8A3713C1F3ADY
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.122.217.24
1F：推 FRAXIS:搜寻 Maximum-Weight Connected Graph Problem 05/30 20:54
2F：→ FRAXIS:应该是NP-Complete问题 所以就只好找些Heuristic方法了 05/30 20:54
3F：→ soheadsome:不好意思 我只有看到几篇论文 我平常很少碰论文 不知从 05/30 22:07
4F：→ soheadsome:何看起 05/30 22:07
5F：→ c2251393:这是一个NPC问题 可是你观察一下他给的那张图的样子 05/31 10:55
6F：→ c2251393:他是一个长得有点像某个东西的图 然後就可以有一个多项 05/31 10:56
7F：→ c2251393:式时间复杂度的演算法 05/31 10:57
8F：→ soheadsome:请问c2251393大大 你说的是MST 还是tree 可以再讲详细 05/31 18:51
9F：→ soheadsome:一点吗? 感谢 05/31 18:52
10F：→ c2251393:他那个图长得很像是一个二维矩阵 每个点连到周围四个点 06/01 17:49
11F：→ c2251393:然後角落再插上一个点 但这不重要 06/01 17:52
12F：→ c2251393:然後你可以得到一个类似flood fill的演算法 06/01 17:54
13F：→ c2251393:就是你枚举一个点 然後开始扩展 每次找与你这个子图相邻 06/01 17:55
14F：→ c2251393:最好的点 加入子图中 06/01 17:56
15F：→ c2251393:详细的作法可以参考 JOI '08-'09 本选 认证レベル 这一题 06/01 17:59
16F：→ c2251393:只不过这题是有两个矩阵 然後各找一个连通子图使得权值总 06/01 18:00
18F：→ soheadsome:c2251393大大 不晓得我的想法是不是跟你想得差不多 我 06/02 01:18
19F：→ soheadsome:想说用BFS一层到某点所相连的其他点 之後再从BFS到的 06/02 01:20
20F：→ soheadsome:的点 在做DFS找该被加入的点 然後递回的做(这应该是DP) 06/02 01:20
21F：→ soheadsome:我演算法学得不是很好= = 06/02 01:21