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

其实不难吧。。。

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

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

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

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

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

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

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

#7 entreveur@2008-10-08 09: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 19:00:00
回复 删除
http://rqnoj.cn/Problem_Show.asp?PID=366和这题一样,LS的去看看那一题的题解吧。
#9 lijiaming12340@2011-09-25 12:06:00
回复 删除
用KURUSCAL!

#10 xiaoyangdi@2014-05-13 09: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,至此题目解完,程序自己去实现!
查看更多回复
提交回复