点这里查看
讨论 / 搞不定了……
Zx.MYS 2011-09-24 21:06:00
点我顶贴 收藏 删除
好像挺难……
#1 wish@2008-08-29 06:00:00
回复 删除
。。。。

其实不难吧。。。

我一开始花了20分钟写出了非常容易理解的 O(n^2) 解法

之后学到了传说中 O(nlgn) 解法。。。

#2 Zx.MYS@2008-08-29 06:03:00
回复 删除
容易理解的O(n^2)不会超时么……
#3 wish@2008-08-29 06:05:00
回复 删除
会超时

不过当时比赛时是提交答案题目。。。

第二个点在机子上算了大约半分钟后得出了正确答案

#4 Zx.MYS@2008-08-29 06:09:00
回复 删除
WISH牛有空写个题解讲解下O(nlgn)算法吧~~~
#5 guoshi3@2008-08-29 06:15:00
回复 删除
对对
#6 wish@2008-08-29 06:16:00
回复 删除
其实不难啊。。。

大家自己考虑一下求 MST 的过程以及 MST 的一些性质，最起码 n^2 算法应该能看出来

#7 entreveur@2008-10-07 18:55:00
回复 删除
O(n^2)只能过第一个点啊，话说一共就两个点，汗...

O(n^2)的话，就是先算出MST的长度，然后枚举图中不属于MST的每条边(u,v)，生成包含这条边的MST2, 那么(u,v)=MST+1-MST2，直到所有边都加好后求一个和就行了，可是呃...传说中的O(nlgn)谁能讲一下?

#8 Zx.MYS@2008-10-08 04:00:00
回复 删除
http://rqnoj.cn/Problem_Show.asp?PID=366和这题一样，LS的去看看那一题的题解吧。
#9 lijiaming12340@2011-09-24 21:06:00
回复 删除
用KURUSCAL！

#10 xiaoyangdi@2014-05-12 18:40:51
回复 删除
读完题目肯定往最小生成树这方面去思考，就2个（prim和kruskal），再看下n，果断思考kruskal，换句话来描述题目就是给出一棵树，然后把树构造成无向完全图，且边权加和最小，那么就来思考kruskal构造最小生成树的过程，结合并查集把2个区域连通（左边区域有x个节点，右边区域有y个节点），假设连通的边权为Wi，为什么Wi是最小生成树中的边，而其他的边不是呢？因为其他的边权都>Wi啊，所以Wi是最小生成树中的边，现在把2个区域合并成一个区域，新增加了x*y条边，Wi也在其中，这样才是无向完全图。那么我们就让每次增量尽量小就OK了，即x*y*（Wi + 1）-1，至此题目解完，程序自己去实现！
查看更多回复
提交回复