下载文档原格式
最⼩树形图——朱刘算法学习笔记问题描述给定⼀张⽆向图和⼀个根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;}。
最小生成树和最短路径-回复什么是最小生成树和最短路径？如何确定它们？这两个概念通常在计算机科学中被广泛应用于解决图论中的相关问题。
在这篇文章中，我们将一步一步地回答这些问题。
首先，让我们来了解最小生成树是什么。
在图论中，最小生成树是一个连通无向图的生成树，其所有边的权重之和最小，并且包含该图的所有顶点。
生成树是一种树状结构，它是由图中所有的顶点以及它们之间的一些边组成，并且这些边必须满足以下条件：它们连接图中的不同顶点，并且不形成环。
为了更好地理解这个定义，让我们通过一个简单的例子来说明最小生成树的概念。
假设我们有一个城市网络，城市之间的路径可以用边来表示，边上的权重表示两个城市之间的距离。
现在我们的目标是建设一条最小的路径，连接这些城市，使得整个网络的总距离最小。
这条路径就是最小生成树。
那么如何确定最小生成树呢？在解决这个问题时，我们可以使用一些经典的算法，其中最著名的是普里姆算法和克鲁斯卡尔算法。
普里姆算法是一种贪心算法，在每一步中选择一个顶点并将其加入最小生成树中，然后选择一个连通该顶点的边权重最小的顶点，将其也加入最小生成树中。
这个过程会一直重复，直到所有的顶点都被添加到最小生成树中。
克鲁斯卡尔算法也是一种贪心算法，它首先将所有的边按权重进行排序，然后从最小权重的边开始，依次将边添加到最小生成树中，直到所有的顶点都被连接起来。
在添加每一条边时，需要判断是否会形成环，如果会形成环，则不选择该边。
当然，最小生成树不止有普里姆算法和克鲁斯卡尔算法这两种求解方法，还有其他一些算法，例如克鲁斯卡尔算法的变体Prim-Dijkstra算法和Boruvka算法等等。
每种算法都有其自身的特点和适用场景，根据具体的问题需求选择合适的算法进行求解。
接下来，让我们来了解最短路径是什么。
在一个加权有向图中，最短路径是指两个顶点之间的路径，其边的权重之和最小。
最短路径问题在计算机科学中有许多应用，例如导航系统、网络路由以及大规模数据处理等领域。
最小树与最小树形图（数学建模）讲解一、最小树的定义及性质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）将新图中的最小树形图扩展回原图，得到原图的最小树形图。
图论是ACM竞赛中比较重要的组成部分，其模型广泛存在于现实生活之中。
因其表述形象生动，思维方式抽象而不离具体，因此深受各类喜欢使劲YY的Acmer的喜爱。
这篇文章引述图论中有关有向图最小生成树的部分，具体介绍朱刘算法的求解思路，并结合一系列coding技巧，实现最小树型图O（VE）的算法，并在最后提供了该算法的模版，以供参考。
关于最小生成树的概念，想必已然家喻户晓。
给定一个连通图，要求得到一个包含所有顶点的树（原图的子图），使之所构成的边权值之和最小。
在无向图中，由于边的无向性质，所以求解变得十分容易，使用经典的kruskal与prim算法已经足够解决这类问题。
而在有向图中，则定义要稍微加上一点约束，即以根为起点，沿给定有向边，可以访问到所有的点，并使所构成的边权值之和最小，于是问题开始变得不一样了，我们称之为最小树型图问题。
该问题是由朱永津与刘振宏在上个世纪60年代解决的，值得一提的是，这2个人现在仍然健在，更另人敬佩的是，朱永津几乎可以说是一位盲人。
解决最小树型图的算法后来被称作朱刘算法，也是当之无愧的。
首先我们来阐述下算法的流程：算法一开始先判断从固定根开始是否可达所有原图中的点，若不可，则一定不存在最小树形图。
这一步是一个很随便的搜索，写多搓都行，不加废话。
第二步，遍历所有的边，从中找出除根结点外各点的最小入边，累加权值，构成新图。
接着判断该图是否存在环。
若不存在，则该图便是所求最小树型图，当前权为最小权。
否则对环缩点，然后回到第二步继续判断。
这里存在一系列细节上的实现问题，以确保能够达到VE的复杂度。
首先是查环，对于新图来说只有n-1条入边，对于各条入边，其指向的顶点是唯一的，于是我们可以在边表中添加from，表示该边的出发点，并考虑到如果存在环，则对环上所有边反向，环是显然同构的，于是最多作V次dfs就能在新图中找到所有的环，并能在递归返回时对顶点重标号进行缩点，此步的重标号可以用hash数组映射。
图论中的最小树及其应用在我们日常的生活中，我们会遇到很多关于优化问题的场景，如网络中的最小生成树问题、高速路网中的最短路径问题以及生产调度中的最优方案问题等等。
这些问题可能由多个因素影响而产生，而图论中的最小树正是一种解决这类问题的有效方法。
最小树，又称为生成树，是指一个无向图的一个子图，该子图包含了该图所有的节点，并且是一棵树。
最小树中的边权值总和是最小的，也即最小生成树。
最小树的生成方法有很多种，其中最典型的是Kruskal算法和Prim算法。
Kruskal算法Kruskal算法是一种贪心算法，其基本思想是“按边权值从小到大依次选择边，如果该边的两个端点不在同一个连通块中，则加入该边，将这两个连通块合并为一个”。
具体实现方法如下：1. 将待处理的边按照边权值从小到大排序；2. 初始化为每个节点构成一个单独的连通块；3. 从小到大地选择各个边，当且仅当选择这条边不会形成回路时，将它加入最小生成树，并合成一个连通块。
Prim算法Prim算法同样是一种贪心算法，其基本思路是“从一个点出发，每次选择一条边权值最小的边与当前生成树相连，直到生成树中包含了图的所有节点”。
具体实现方法如下：1. 选择一个起点加入最小生成树，并标记为已访问；2. 找到能够与该起点相连的所有边，并选择边权值最小的那一条边加入最小生成树；3. 将新加入的节点标记为已访问，重复步骤2，直至所有的节点都被访问过。
最小树的应用最小树的一个显著的应用是在网络中，如建立一颗覆盖广域网中所有节点的最小生成树。
这样的最小树可以帮助我们找到最少的路由器连接方法，从而减少数据包的传输时间和网络的延迟。
最小树还可以应用于电路布线中。
电路布线是一个布置和连接一系列元器件的过程。
在布线时，往往需要满足一些限制条件，如避免高频电流、防止电磁干扰等因素。
如果将布线问题转换成无向图的最小树问题，可以帮助我们找到一种最少的连接方式，从而降低布线过程中的成本和时间消耗。
七年级上数学知识点树形图树形图是一种用于展示层级关系的图表，可以清晰地表示一个层级内物品之间的结构，同时也具有较好的可视化效果。
在七年级上的数学学习中，掌握树形图是非常重要的，因为它涉及到很多数学概念。
本文将介绍七年级上数学知识点树形图的相关内容。
一、树形图的概念树形图是一种由节点和线条组成的图表，它可以表示多层级的物品结构。
通常树形图的最顶端为根节点，紧接着下面是其子节点，子节点又可以接着延伸分支，形成更多的子节点。
这样的层级系统可以很好地表示一个结构的层次关系。
二、树形图的应用在七年级上的数学学习中，树形图有很多应用。
例如，它可以用来表示有向图结构。
有向图指的是从一个起点出发，经过线条到达终点的过程。
树形结构可以很好地表示这个过程中的每一个节点和线条，从而清晰地表示有向图的结构。
此外，树形图还可以用来表示集合的结构。
集合是数学中非常重要的概念，有很多与之相关的专业术语。
利用树形图可以很好地表示一个集合中的成员关系，从而方便进行相关的计算。
三、树形图的绘制方法在绘制树形图时，需要注意以下几个问题：1. 根据树形图的结构，需要从上至下逐层绘制每一个节点和线条。
2. 节点的位置和大小需要根据实际情况进行调整，以充分展示层级关系。
3. 线条的绘制需要遵循特定的规则，例如箭头的方向要清晰地表示出有向图的方向。
4. 需要确保树形图的整体比例协调，以保证图表清晰易懂。
以上几点是绘制树形图时需要注意的一些关键问题。
四、树形图的应用案例下面我们以集合的结构为例，介绍树形图在数学中的应用。
例如，对于一个有30个人的班级，我们可以用树形图来展示每个人的性别、身高、体重等信息。
其中，性别可以用以下两个节点表示：男性女性身高可以用以下三个节点表示：小于1.6米1.6-1.8米大于1.8米体重可以用以下两个节点表示：小于60kg大于等于60kg这样我们就可以用树形图将这些节点连接成一个集合结构，清晰地表示出每个人的性别、身高、体重等信息。
最小生成树和最短路径
最小生成树和最短路径都是图论中常见的概念，用于解决不同类型的图问题。
1. 最小生成树（Minimum Spanning Tree，MST）：
最小生成树是指在一个连通加权无向图中找到一棵包含图中所有顶点的树，并且边的权重之和最小。
常用的算法有Prim算法和Kruskal算法。
- Prim算法：从一个初始顶点开始，逐步将与当前树集合相邻的具有最小权值的边加入，直至覆盖所有顶点为止。
- Kruskal算法：按边的权值从小到大的顺序考虑，逐步加入不构成回路的边，直到生成树中含有所有顶点为止。
2. 最短路径（Shortest Path）：
最短路径是指在一个加权有向图或无向图中找到两个顶点之间权重和最小的路径。
常用的算法有Dijkstra算法和Bellman-Ford算法。
- Dijkstra算法：用于求解单个源点到图中所有其他顶点的最短路径，前提是图中不存在负权边。
- Bellman-Ford算法：可以处理存在负权边的情况，用于求解单个源点到图中所有其他顶点的最短路径。
这两个概念都涉及到图的遍历和路径查找，但目标和应用场景有所不同。
最小生成树着重于构建一个覆盖图所有顶点的树且总权值最小，而最短路径则是找到两点之间权重和最小的路径。
这些算法在网络规划、路径优化、通信网络等领域有着广泛的应用。
伯克霍夫遍历定理
伯克霍夫遍历定理（Berkhoff's theorem），也称为柏氏定理，是图论中的一个定理，它给出了有向图的生成树个数的计算方法。
伯克霍夫遍历定理的表述为：一个n个节点的有向图G，如果用行列式D(G)表示G的拉普拉斯矩阵的行列式（度矩阵减去邻接矩阵），那么G的生成树的个数等于D(G)中任意一个代数余子式的值。
具体来说，如果G的拉普拉斯矩阵的行列式D(G)中去掉第i 行和第j列，形成的新的矩阵的行列式为D_ij，那么G的生成树的个数等于D_ij的值。
伯克霍夫遍历定理的一个重要应用是计算有向图中的最小树形图，即以一个节点作为根节点的最小生成树。
利用伯克霍夫遍历定理，可以将最小树形图问题转化为计算有向图的生成树个数的问题，从而求解最优解。
总结起来，伯克霍夫遍历定理是一个用于计算有向图的生成树个数的定理，它通过拉普拉斯矩阵的代数余子式求解生成树个数，具有重要的理论和实际应用价值。
一．最小树形图最小树形图，就是给有向带权图中指定一个特殊的点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恢复为原图状态的时候，这个树形图的权仍然是新图树形图的权加环的权，而这个权值正是最小树形图的权值。
【转】【最⼩树形图】有向图的最⼩⽣成树【朱刘算法】这篇⽂章挺好的。
每⾏还有注释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？所以，就这样就被我们想出了两个需要判断的条件了。
把所有的最⼩⼊边先加起来，我们得到了⼀个花⾥胡哨的图，可能它就是多个环的集合，也许恰好是答案，这都是不确定的，若是恰好是已经没有环了，那么这就是答案了；反之，就是有环，那么，我们得到的边，就不⼀定是所有的点构在⼀起的图（也许会成为森林这样的情况），那么，把环搜索起来吧，我们把⼀个环搜索成⼀个点，然后对于它（新点——即所谓的缩点）的⼊边，我们建⽴新边的时候，需要考虑到我们得删除原来在这幅图⾥的改点的⼊边（就是我们已经存⼊了这个原节点的⼊边了，但是，它却构成了环，说明不是我想要的解），所以，新边的权值就是原权值减去终点节点的最⼩⼊边。
