因为期末要交project,
但题目看很久不知道该怎么从哪下手,
google很久
只看到说可以转成prize-collecting Steiner tree
所以想请教大大们,可不可以给我一些提示
感谢
附题目ppt:
https://www.asuswebstorage.com/navigate/s/53DE46AEC6CD41C99D3A3CDAC7318B49Y
在网络上找到相关内容的ppt:
https://www.asuswebstorage.com/navigate/s/34D9CE30384C48759D2E8A3713C1F3ADY

搜寻 Maximum-Weight Connected Graph Problem应该是NP-Complete问题 所以就只好找些Heuristic方法了

不好意思 我只有看到几篇论文 我平常很少碰论文 不知从何看起

这是一个NPC问题 可是你观察一下他给的那张图的样子他是一个长得有点像某个东西的图 然后就可以有一个多项式时间复杂度的算法

请问c2251393大大 你说的是MST 还是tree 可以再讲详细一点吗? 感谢

他那个图长得很像是一个二维矩阵 每个点连到周围四个点然后角落再插上一个点 但这不重要然后你可以得到一个类似flood fill的算法就是你枚举一个点 然后开始扩展 每次找与你这个子图相邻最好的点 加入子图中详细的作法可以参考 JOI '08-'09 本选 认証レベル 这一题只不过这题是有两个矩阵 然后各找一个连通子图使得权值总和最大 官方题解(日文) : http://tinyurl.com/mwpvkxu

c2251393大大 不晓得我的想法是不是跟你想得差不多 我想说用BFS一层到某点所相连的其他点 之后再从BFS到的的点 在做DFS找该被加入的点 然后递回的做(这应该是DP)我算法学得不是很好= =