#1 wish@2008-08-29 06:00:00
5580
回复
删除
。。。。
其实不难吧。。。
我一开始花了20分钟写出了非常容易理解的 O(n^2) 解法
之后学到了传说中 O(nlgn) 解法。。。
#7 entreveur@2008-10-07 18:55:00
6732
回复
删除
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
6745
回复
删除
http://rqnoj.cn/Problem_Show.asp?PID=366和这题一样,LS的去看看那一题的题解吧。
#10 xiaoyangdi@2014-05-12 18:40:51
32644
回复
删除
读完题目肯定往最小生成树这方面去思考,就2个(prim和kruskal),再看下n,果断思考kruskal,换句话来描述题目就是给出一棵树,然后把树构造成无向完全图,且边权加和最小,那么就来思考kruskal构造最小生成树的过程,结合并查集把2个区域连通(左边区域有x个节点,右边区域有y个节点),假设连通的边权为Wi,为什么Wi是最小生成树中的边,而其他的边不是呢?因为其他的边权都>Wi啊,所以Wi是最小生成树中的边,现在把2个区域合并成一个区域,新增加了x*y条边,Wi也在其中,这样才是无向完全图。那么我们就让每次增量尽量小就OK了,即x*y*(Wi + 1)-1,至此题目解完,程序自己去实现!