Knight
KNIGHT
C++博客
首页
新随笔
联系
聚合
管理
posts - 74, comments - 33, trackbacks - 0
最小树形图
对于最小树形图前几天做了n个不定根的最小树形图,因为n<16对此我用的是dp方法WS过去了那道题目,0.3s相对于最小树形图的正确解法的0.001实在是惭愧,为此也找到了一种最小树形图的DP解法当然n<16时间和空间上才能受得了。
再谈朱刘算法解决最小树形图问题:下面是转载的资料:
有固定根的最小树形图求法O(VE):
首先消除自环,显然自环不在最小树形图中。然后判定是否存在最小树形图,以根为起点DFS一遍即可。
之后进行以下步骤。
设cost为最小树形图总权值。
0
.置cost
=
0
。
1
.求最短弧集合Ao (一条弧就是一条有向边)
除源点外,为所有其他节点Vi,找到一条以Vi为终点的边,把它加入到集合Ao中。
(加边的方法:所有点到Vi的边中权值最小的边即为该加入的边,记prev[vi]为该边的起点,mincost[vi]为该边的权值)
2
.检查Ao中的边是否会形成有向圈,有则到步骤3,无则到步骤4。
(判断方法:利用prev数组,枚举为检查过的点作为搜索的起点,做类似DFS的操作)
3
.将有向环缩成一个点。
假设环中的点有(Vk1,Vk2,… ,Vki)总共i个,用缩成的点叫Vk替代,则在压缩后的图中,其他所有不在环中点v到Vk的距离定义如下:
gh[v][Vk]
=
min
{ gh[v][Vkj]
-
mincost[Vkj] }
(
1
<=
j
<=
i)而Vk到v的距离为
gh[Vk][v]
=
min
{ gh[Vkj][v] }
(
1
<=
j
<=
i)
同时注意更新prev[v]的值,即if(prev[v]
==
Vkj) prev[v]
=
Vk
另外cost
=
cost
+
mincost[Vkj] (
1
<=
j
<=
i)
到步骤1.
4
.cost加上Ao的权值和即为最小树形图总权值。
如要输出最小树形图较烦,没实现过。
找环O(V),收缩O(E),总复杂度O(VE)。
那幅对我有莫大帮助的流程图如下,
对于不固定根的最小树形图,wy教主有一巧妙方法。摘录如下:
新加一个点,和每个点连权相同的边,这个权大于原图所有边权的和,这样这个图固定跟的最小树形图和原图不固定跟的最小树形图就是对应的了。
这分资料上在理论上证明并不完整导致看上去也许多不解之处.......而具体证明建议是自己按照资料上说的出几个带环的图然后按照上面说一布一步执行慢慢的就会理解证明,
对于实现代码建议自己先写一份然后搜一份模板比对一下。
posted on 2009-04-30 17:16
KNIGHT
阅读(1300)
评论(0)
编辑
收藏
引用
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
<
2009年5月
>
日
一
二
三
四
五
六
26
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
6
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
(8)
给我留言
查看公开留言
查看私人留言
随笔档案
2009年6月 (4)
2009年5月 (14)
2009年4月 (12)
2009年3月 (10)
2009年2月 (12)
2009年1月 (10)
2008年12月 (12)
文章档案
2009年3月 (1)
Friends
OJ
HEU
PKU
ZJU
搜索
最新评论
1. re: (转载)TopCoder入门手册
好,学习了
--wuyiqi
2. re: Knights
评论内容较长,点击标题查看
--Lightning
3. re: Knights
请问您说的奇偶性不同的x,y是指什么?
--Lightning
4. re: [ZZ]后缀数组[未登录]
@爱上对方
请你仔细阅读标题
【ZZ】转载。。懂
--Knight
5. re: [ZZ]后缀数组
请你不要抄
--爱上对方
阅读排行榜
1. (转载)TopCoder入门手册(6458)
2. 浅谈2—SAT问题(6167)
3. 分而治之算法---距离最近的点对 (2727)
4. poj 3648 Wedding(1431)
5. 最小树形图(1300)
评论排行榜
1. Making the Grade(3)
2. poj 3648 Wedding(3)
3. [ZZ]后缀数组(2)
4. Knights(2)
5. 感(2)