下载文档原格式
最⼩树形图——朱刘算法学习笔记问题描述给定⼀张⽆向图和⼀个根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数组映射。
一．
最小树形图
最小树形图，就是给有向带权图中指定一个特殊的点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教主有一巧妙方法。
摘录如下：
新加一个点，和每个点连权相同的边，这个权大于原图所有边权的和，这样这个图固定跟的最小树形图和原图不固定跟的最小树形图就是对应的了。
