下载文档原格式
最⼩树形图——朱刘算法学习笔记问题描述给定⼀张⽆向图和⼀个根r，求出⼀个n-1条边的⼀张⼦图，使得从r出发可以到达任意⼀个点，同时使得所有选择的边权之和最⼩。
根据最⼩树形图的定义，这张图的除了根的每⼀个点都必须有且仅有⼀个⼊度。
那么我们可以贪⼼⼀点，对于除了根的所有点都找出⼀条连向它的边且边权最⼩，称作这个点的代表边，并把这些边权加⼊答案中。
然后我们找出了⼀张图，这张图中每个点都只有⼀个⼊度。
如果不算根的话，它应当是⼀个外向基环树森林。
然后我们找到所有的环，把它们缩成⼀个点。
再去扫描不在环内的边，假设有u->v,那么这条边的边权要减掉v的代表边权。
因为v是⼀个环，如果继续连u->v的边的话，相当于是把原来v的⽗亲断开，再连上u。
于是我们就完成了缩点，⼀直做下去，知道图中没有环。
⽆解就是图中除了根有点没有⼊度。
代码细节1、初始化，我们令id[]表⽰这个点在那个环⾥，top[]表⽰环顶(找环时⽤)，mi[]表⽰代表边的边权,cnt表⽰环数。
2、找环的时候，因为是⼀颗外向基环树，所以我们对于每个点记录father，这样father就变成了内向基环树，这样可以⽅便找环。
3、没有和其他点组成环的让它⾃⼰成为⼀个环。
4、每做完⼀轮之后要更新⼀下点数和根。
代码#include<iostream>#include<cstdio>#define N 109#define M 10009#define inf 2e9using namespace std;int tot,top[N],id[N],cnt,mi[N],n,m,fa[N],r;long long ans;inline int rd(){int x=0;char c=getchar();bool f=0;while(!isdigit(c)){if(c=='-')f=1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}return f?-x:x;}struct edge{int from,to,l;}e[M];inline void add(int u,int v,int l){e[++tot].to=v;e[tot].l=l;e[tot].from=u;}inline bool solve(){while(1){for(int i=1;i<=n;++i)id[i]=top[i]=0,mi[i]=inf;for(int i=1;i<=m;++i)if(e[i].to!=e[i].from&&e[i].l<mi[e[i].to])fa[e[i].to]=e[i].from,mi[e[i].to]=e[i].l;int u=0;mi[r]=0;for(int i=1;i<=n;++i){if(mi[i]==inf)return0;ans+=mi[i];for(u=i;u!=r&&top[u]!=i&&!id[u];u=fa[u])top[u]=i;if(u!=r&&!id[u]){id[u]=++cnt;for(int v=fa[u];v!=u;v=fa[v])id[v]=cnt;}}if(!cnt)return1;for(int i=1;i<=n;++i)if(!id[i])id[i]=++cnt;for(int i=1;i<=m;++i){int num=mi[e[i].to];e[i].from=id[e[i].from];e[i].to=id[e[i].to];if(e[i].from!=e[i].to)e[i].l-=num;}n=cnt;r=id[r];cnt=0;}}int main(){n=rd();m=rd();r=rd();int u,v,w;for(int i=1;i<=m;++i){u=rd();v=rd();w=rd();add(u,v,w); }if(solve())cout<<ans;else puts("-1");return0;}。
最小树与最小树形图（数学建模）讲解一、最小树的定义及性质1. 定义：最小树，又称最小树，是指在给定的带权无向图中，包含图中所有顶点的一个树形结构，且树中所有边的权值之和最小。
2. 性质：（1）最小树中不存在回路；（2）对于最小树中的任意两个顶点，它们之间有且仅有一条路径；（3）最小树中边的数量等于顶点数量减一；（4）在最小树中添加任意一条边，都会形成一条回路；（5）最小树不唯一，但权值之和相同。
二、求解最小树的方法1. Prim算法Prim算法是一种贪心算法，其基本思想是从图中的一个顶点开始，逐步添加边和顶点，直到形成最小树。
具体步骤如下：（1）初始化：选择一个顶点作为最小树的起点，将其加入最小树集合；（2）迭代：在最小树集合和非最小树集合之间，寻找一条权值最小的边，将其加入最小树集合；（3）重复步骤2，直到所有顶点都加入最小树集合。
2. Kruskal算法Kruskal算法同样是一种贪心算法，其基本思想是将图中的所有边按权值从小到大排序，然后依次选择权值最小的边，判断是否形成回路，若不形成回路，则将其加入最小树集合。
具体步骤如下：（1）初始化：将所有顶点视为独立的树；（2）按权值从小到大排序所有边；（3）迭代：选择权值最小的边，判断其是否形成回路，若不形成回路，则将其加入最小树集合；（4）重复步骤3，直到所有顶点都在同一棵树中。
三、最小树形图的定义及求解方法1. 定义：最小树形图，又称最优树形图，是指在给定的有向图中，找到一个包含所有顶点的树形结构，使得树中所有边的权值之和最小。
2. 求解方法：朱刘算法（Edmonds' Algorithm）朱刘算法是一种用于求解最小树形图的算法，其基本思想是通过寻找图中的最小权值环，进行收缩和扩展操作，最终得到最小树形图。
具体步骤如下：（1）寻找最小权值环；（2）对最小权值环进行收缩操作，将环中的顶点合并为一个新顶点；（3）在新图中寻找最小树形图；（4）将新图中的最小树形图扩展回原图，得到原图的最小树形图。
斯坦纳树算法
斯坦纳树算法，也称为“终极斯坦纳树算法”，是一种用于解决带权图中的最小树形图问题的算法。
该算法具有时间复杂度为O（n^3 * 2^n）的特点，因此适用于小型图和中等规模的图，但在大型图上会出现运行时间过长的问题。
斯坦纳树算法的基本思想是将原图中的顶点集合划分成若干个
子集，然后对每个子集构建一棵最小树形图，最后将所有子集的最小树形图合并成一棵最终的最小树形图。
该算法的核心在于如何构建子集的最小树形图，这通常使用DP（动态规划）的方式进行求解。
具体而言，斯坦纳树算法的步骤如下：
1.将所有边的权值取对数，并对原图做一些预处理，以提高算法效率。
2.对于每个子集S，使用DP的方式计算S中所有点到S中某个点的最短距离，记为d(S,v)，其中v是S中任意一个点。
3.对于每个子集S，将S中所有点连成一棵生成树，使得该树的根节点为S中某个点，且所有连边的权值之和等于d(S,v)。
4.通过枚举所有的子集S，计算每个子集的最小树形图，并记录下最小树形图的权值。
5.将所有子集的最小树形图合并成一棵最终的最小树形图。
需要注意的是，斯坦纳树算法只适用于有向图，且存在一些限制条件，如原图必须联通等。
此外，该算法在实际应用中，可能需要结合其他算法一起使用，以解决一些特殊情况下的问题。
图论是ACM竞赛中比较重要的组成部分，其模型广泛存在于现实生活之中。
因其表述形象生动，思维方式抽象而不离具体，因此深受各类喜欢使劲YY的Acmer的喜爱。
这篇文章引述图论中有关有向图最小生成树的部分，具体介绍朱刘算法的求解思路，并结合一系列coding技巧，实现最小树型图O（VE）的算法，并在最后提供了该算法的模版，以供参考。
关于最小生成树的概念，想必已然家喻户晓。
给定一个连通图，要求得到一个包含所有顶点的树（原图的子图），使之所构成的边权值之和最小。
在无向图中，由于边的无向性质，所以求解变得十分容易，使用经典的kruskal与prim算法已经足够解决这类问题。
而在有向图中，则定义要稍微加上一点约束，即以根为起点，沿给定有向边，可以访问到所有的点，并使所构成的边权值之和最小，于是问题开始变得不一样了，我们称之为最小树型图问题。
该问题是由朱永津与刘振宏在上个世纪60年代解决的，值得一提的是，这2个人现在仍然健在，更另人敬佩的是，朱永津几乎可以说是一位盲人。
解决最小树型图的算法后来被称作朱刘算法，也是当之无愧的。
首先我们来阐述下算法的流程：算法一开始先判断从固定根开始是否可达所有原图中的点，若不可，则一定不存在最小树形图。
这一步是一个很随便的搜索，写多搓都行，不加废话。
第二步，遍历所有的边，从中找出除根结点外各点的最小入边，累加权值，构成新图。
接着判断该图是否存在环。
若不存在，则该图便是所求最小树型图，当前权为最小权。
否则对环缩点，然后回到第二步继续判断。
这里存在一系列细节上的实现问题，以确保能够达到VE的复杂度。
首先是查环，对于新图来说只有n-1条入边，对于各条入边，其指向的顶点是唯一的，于是我们可以在边表中添加from，表示该边的出发点，并考虑到如果存在环，则对环上所有边反向，环是显然同构的，于是最多作V次dfs就能在新图中找到所有的环，并能在递归返回时对顶点重标号进行缩点，此步的重标号可以用hash数组映射。
最小生成树例题详解最小生成树(Minimum Spanning Tree,简称 MST)是一种图论中的算法,用于在一个加权连通图中找到一棵包含所有顶点且边权值之和最小的生成树。
下面是一个常见的最小生成树例题:给定一个由五只兔子和它们的家组成的奴隶图,如下图所示:```1 2 3 4 5/ / /6 7 8 9 10 11/ / /2 4 6 8 10 12```要求找到一棵包含所有顶点且边权值之和最小的生成树。
首先,我们需要遍历整个图,将每个节点的度数表示出来,度数等于该节点到其他节点的距离。
我们可以用度数最小的节点来代替这个节点。
接下来,我们需要计算每个节点到根节点的度数。
如果某个节点到根节点的度数大于等于它的度数,那么它就不是最小生成树的一部分,我们需要继续寻找。
最后,我们需要计算每个节点的边权值之和。
我们可以用度数最小的节点来代替这个节点,然后遍历该节点的邻居节点,计算它们的边权值之和。
以下是Python代码实现:```pythondef Minimum Spanning Tree(graph):# 遍历整个图,将每个节点的度数表示出来,度数最小为0for node in graph:度数 = [float(edge[node]) for edge ingraph.get_edges(node)]if度数[0] <= 0:return None# 找到最小生成树root = node = Nonefor node in graph.nodes():if root is None:if not any(edge[node] for edge in graph.get_edges(node)): root = nodebreakelse:# 度数最小的节点来代替该节点if not any(edge[node] for edge in graph.get_edges(node)): root = nodebreak# 计算该节点到根节点的度数度数 = [float(edge[node]) for edge ingraph.get_edges(node)]if度数[0] <= 0:return None# 找到连接到该节点的所有边neighbors = [node for edge in graph.get_edges(node) if edge[1] >= 0]# 计算该节点的边权值之和neighbors_sum = sum(度数)# 找到边权值之和最小的节点if neighbors_sum < neighbors_sum.min():root = nodebreakreturn root```在此算法中,我们使用了邻接表(neighbors table)来维护每个节点的邻居节点。
一．最小树形图最小树形图，就是给有向带权图中指定一个特殊的点root，求一棵以root为根的有向生成树T，并且T中所有边的总权值最小。
最小树形图的第一个算法是1965年朱永津和刘振宏提出的复杂度为O(VE)的算法。
判断是否存在树形图的方法很简单，只需要以v为根作一次图的遍历就可以了，所以下面的算法中不再考虑树形图不存在的情况。
在所有操作开始之前，我们需要把图中所有的自环全都清除。
很明显，自环是不可能在任何一个树形图上的。
只有进行了这步操作，总算法复杂度才真正能保证是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恢复为原图状态的时候，这个树形图的权仍然是新图树形图的权加环的权，而这个权值正是最小树形图的权值。
收稿日期;修回日期。
作者简介纪茉丽(3),女,山西洪洞人,硕士研究生,主要研究方向数字金融、W S ; 杨社堂(6),男,山西怀仁人,教授,主要研究方向金融信息化技术、网络支付安全。
文章编号:1001-9081(2009)03-0905-03基于绝对最小树形图的跨行资金归集模型纪茉丽,杨社堂(太原理工大学计算机与软件学院,太原030024)(ji moli 22003@)摘 要:跨行资金归集就是将集团内下级单位在非单一银行开设的账户内的资金上收至集团账户的过程。
其目的在于提高集团企业整体的资金使用率。
但是由于归集业务发生频繁,企业对银行间的手续费用支出骤增,企业获利也随之骤减。
提出了基于绝对最小树形图的跨行资金归集模型,并验证了企业采用此模型后,手续费用会降至最低,使企业在提高资金使用率时,有效控制了费用支出。
关键词:跨行资金归集;绝对最小树形图;降低费用中图分类号:TP311.1;TP202 文献标志码:AI n ter bank ca sh co n cen tra ti on m odel ba sed on ab solute m i n i m u m for k tr eeJ IMo 2li,Y ANG She 2tang(College of Computer and Soft ware,Taiyuan Un i versit y of Technol ogy,Taiyuan S hanxi 030024,Ch i na )Abstra c t:Ca sh concentra ti on is the cash fl ow t hat g oe s f r om the subordina t e accounts in diffe rent banks t o the head office account .Corporati ons ad op t interbank ca sh concentra tion t o i mp rove the cap ita l m anage m ent eff i c iency as a wh ole .B ut the handling charges throughout the i nte rbank transferring abrup tly i ncrease because of the frequent cash collec ti ons .Tha t re s ults in corpora te p r ofit deduc ti on .This paper introduced an alg o rith m nam ed absolute m ini m u m fork tree and designed an inte rbank ca sh concentrati on model .I n conc l usi on,due t o mode l πs availability st udy the cost could be reduced efficiently .Key word s:int e rbank ca sh concentrati on;absol ute m ini mu m fork tree;cost reducti on0 引言企业特别是大型的集团公司由于下属的成员公司众多且分布在不同的地域或行业[1],为了对下属公司的财务以及相关生产经营活动有一个清晰的掌控并使企业整体收益最大化,企业集团应建立一套完善的现金管理体系,并建立企业现金池(归集账户或主账户),做到资金的集中化管理和优化调度。
【转】【最⼩树形图】有向图的最⼩⽣成树【朱刘算法】这篇⽂章挺好的。
每⾏还有注释QAQ，kuangbin的模板⾥并没有万能节点；万能节点好像是在不定根的时候的拓展。
要点：1.求所有边权和sum;2.以0点为万能节点向所有点建⼀条权值为sum的边；3.记得sum++；保证⽐所有边权值总和⼤⼀点；4.判断条件为(ans==-1 || ans-sum>=sum) //ans-sum是除去虚根的最⼩树形图的最短路径，如果这个距离⽐所有的边权值和sum还⼤，说明还有另外的边由虚点发出，故说明此图不连通5.答案即为ans-sum；做了POJ的⼀道题，总是WA，不知道为什么，后来去看了，才知道，原来有向图的最⼩⽣成树与⽆向图不⼀样，它得是从某个点出发能遍历到其他所有点的才⾏，以此为条件，我们学习到了最⼩树形图。
与很多其他⼈的讲解不⼀样吧，我把我看了博客后⾃⼰的思路分享出来，关于什么是最⼩树形图。
我们知道的既然要建⽴最⼩树形图，就要理解什么是最⼩树形图，（概念好难懂啊，还是⾃⼰写的清楚明⽩），我们从某⼀点出发（或者是固定点），能通过它跑完所有点的最⼩花费，就是最⼩树形图了。
那么，怎么去搭建最⼩树形图？会有⼈看到关于最⼩弧这样的讲法，诶！确实是这样的，但是你们理解什么是最⼩弧吗？我们想构建⼀颗最⼩⽣成树的时候，就是找到这样的最优解的边逐条放进去的（Kruskal算法思想），但是这也是⼀样的，我们找到所有⾮根节点的最⼩⼊边，先把这样的所有⼊边给加进来，那么得到的⼀幅图，可能还真是不完全，要是遇到了个环，岂不是有趣，或者呢，压根就⾛不完！不就GG？所以，就这样就被我们想出了两个需要判断的条件了。
把所有的最⼩⼊边先加起来，我们得到了⼀个花⾥胡哨的图，可能它就是多个环的集合，也许恰好是答案，这都是不确定的，若是恰好是已经没有环了，那么这就是答案了；反之，就是有环，那么，我们得到的边，就不⼀定是所有的点构在⼀起的图（也许会成为森林这样的情况），那么，把环搜索起来吧，我们把⼀个环搜索成⼀个点，然后对于它（新点——即所谓的缩点）的⼊边，我们建⽴新边的时候，需要考虑到我们得删除原来在这幅图⾥的改点的⼊边（就是我们已经存⼊了这个原节点的⼊边了，但是，它却构成了环，说明不是我想要的解），所以，新边的权值就是原权值减去终点节点的最⼩⼊边。
一．
最小树形图
最小树形图，就是给有向带权图中指定一个特殊的点root，求一棵以root为根的有向生成树T，并且T中所有边的总权值最小。
最小树形图的第一个算法是1965年朱永津和刘振宏提出的复杂度为O(VE)的算法。
判断是否存在树形图的方法很简单，只需要以v为根作一次图的遍历就可以了，所以下面的算法中不再考虑树形图不存在的情况。
在所有操作开始之前，我们需要把图中所有的自环全都清除。
很明显，自环是不可能在任何一个树形图上的。
只有进行了这步操作，总算法复杂度才真正能保证是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)，然后最多会收缩几次呢？由于我们一开始已经拿掉了所有的自环，我门可以知道每个环至少包含2个点，收缩成1个点之后，总点数减少了至少1。
当整个图收缩到只有1个点的时候，最小树形图就不不用求了。
所以我们最多只会进行V-1次的收缩，所以总得复杂度自然是O(VE)了。
由此可见，如果一开始不除去自环的话，理论复杂度会和自环的数目有关
学了不少算法，终于第一次学会了以中国人的名字命名的算法，最小树形图的朱-刘算法。
前几天看过书、ppt和网上相关的blog，在收缩环关键的那块总看得稀里糊涂。
昨晚终于在威士忌的blog上看到了一幅最小树形图的构造流程图，登时大彻大悟。
有时一张恰当好处的图表的确胜过万千文字解说。
早上起来把它实现了，调试到现在，进一步把各种模糊的细节处理弄清楚了，也终于AC了POJ3164。
呵呵
网上关于算法的描述有一些，我总结成bin3版。
有固定根的最小树形图求法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)。
二．
学了不少算法，终于第一次学会了以中国人的名字命名的算法，最小树形图的朱-刘算法。
前几天看过书、ppt和网上相关的blog，在收缩环关键的那块总看得稀里糊涂。
昨晚终于在
威士忌的blog上看到了一幅最小树形图的构造流程图，登时大彻大悟。
有时一张恰当好处的图表的确胜过万千文字解说。
早上起来把它实现了，调试到现在，进一步把各种模糊的细节处理弄清楚了，也终于AC了POJ3164。
呵呵
网上关于算法的描述有一些，我总结成bin3版。
有固定根的最小树形图求法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教主有一巧妙方法。
摘录如下：
新加一个点，和每个点连权相同的边，这个权大于原图所有边权的和，这样这个图固定跟的最小树形图和原图不固定跟的最小树形图就是对应的了。
