基于小树形图模板优化算法研究.pdfVIP

最小树形图朱刘算法

在所有操作开始之前，我们需要把图中所有的自环全都清除。很明显，自环是不可能在任何

一个树形图上的。只有进行了这步操作，总算法复杂度才真正能保证是O(VE)。

首先为除根之外的每个点选定一条入边，这条入边一定要是所有入边中最小的。现在所

有的最小入边都选择出来了，如果这个入边集不存在有向环的话，我们可以证明这个集合就

是该图的最小树形图。这个证明并不是很难。如果存在有向环的话，我们就要将这个有向

环所称一个人工顶点，同时改变图中边的权。假设某点u在该环上，并设这个环中指向u的

边权是in[u]，那么对于每条从u出发的边(u,i,w)，在新图中连接(new,i,w)的边，其中new为

新加的人工顶点;对于每条进入u的边(i,u,w)，在新图中建立边(i,new,w-in[u])的边。为什

么入边的权要减去in[u]，这个后面会解释，在这里先给出算法的步骤。然后可以证明，新图

中最小树形图的权加上旧图中被收缩的那个环的权和，就是原图中最小树形图的权。

上面结论也不做证明了。现在依据上面的结论，说明一下为什么出边的权不变，入边的

权要减去in[u]。对于新图中的最小树形图T，设指向人工节点的边为e。将人工节点展开以

后，e指向了一个环。假设原先e是指向u的，这个时候环上指向u的边in[u]删除，

这样就得到了原图中的一个树形图。我们会发现，如果新图中e的权w(e)是原图中e的权

w(e)减去in[u]权的话，那么在我们删除掉in[u]，并且将e恢复为原图状态的时候，这个树

形图的权仍然是新图树形图的权加环的权，而这个权值正是最小树形图的权值。所以在展开

节点，我们得到的仍然是最小树形图。逐步展开所有的人工节点，就会得到初始图的

最小树形图了。

如果实现得很聪明的话，可以达到找最小入边O(E)，找环O(V)，收缩O(E)，其中在找

环O(V)这里需要一点技巧。这样每次收缩的复杂度是O(E)，然后最多会收缩几次呢？由于我

所以我们最多只会进行V-1次的收缩，所以总得复杂度自然是O(VE)了。由此可见，如果一

开始不除去自环的话，理论复杂度会和自环的数目有关。

1、找到除了root以为其他点的权值最小的入边。用In[i]记录

2、如果出现除了root以为存在其他孤立的点，则不存在最小树形图。

3、找到图中所有的环，并对环进行缩点，重新编号。

4、更新其他点到环上的点的距离，如：

环中的点有（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)

5、重复3，4知道没有环为止。

#includecstdio

#includeiostream

#includequeue

#includeset

#includectime

#includealgorithm

#includecmath

#includevector

#includemap

#includecstring

usingnamespacestd;

constdoubleeps=1e-10;

#defineM109

#definetypedouble

consttypeinf=(1)30;

structpoint

{

doublex,y;

}p[M];

doubledis(pointa,pointb)

{

returnsqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

}

structNode{

intu,v;

typecost;

}E[M*M+5];

intpre[M],ID[M],vis[M];

typeIn[M];

intn,m;

typeDirected_MST(introot,intNV,intNE)

{typeret=0;

while(true){

//1.找最