本文主要介绍最小树图算法(最小树图假设)，下面一起看看最小树图算法(最小树图假设)相关资讯。
最小树图真的是一个比较模板的题目，一般不常见。其本质是贪婪算法。
小问题:在引出有向无环图的最小树图算法之前，让 让我们先考虑一个问题。我们如何求有向无环图的最小树图？
因为图上没有圈，所以我们可以直接为每个点(非根节点)找到它的最小边。
而且因为是无环的，所以必须只有一个根节点(即只有一个度为0的节点)，否则就和无环矛盾了。
1.朱刘算法(edmonds algorithm)有向图上的最小生成树(dmst)也称为最小树图。
朱刘算法可以在时间复杂度为o(n*m)的范围内解决这个问题。
具体流程如下:
对于每个点，从所有传入的边中选择边权重最小的边，并记录下来。如果所有选定的边没有形成一个循环，那么dmst是好的。如果形成了一个环，那么就把环收缩成一个点(在此之前，需要更新图上其他边的边权)，在新图上运行朱刘算法(这里的收缩环并没有收缩所有的环，所以图上可能还有环)。下面是算确性的证明(详见yybakioi的解法):
简单证明1。考虑为每个节点(根节点除外)选择一条最小边。如果没有圈，那么这个图一定有最小的权。
2.如果有一个环，因为这个环是由最小的边构成的，所以最小树图的存在只使环缺少一条边。那么应该如何考虑哪条边缺失了呢？
首先将环收缩成点，然后在收缩环后更新图上边的边权[let \(in[x]_w是x的最小边\)，\(edge[x]_ w-= in[x]_ w \]。如果x在环上，那么所有指向x的边都需要被减去\(在[x]中我们的问题变成:在收缩环后求图的最小树图。
这一步是贪婪:考虑到环上边的边权，如果有环外的边要选，对答案的贡献是\(edge[x]_w-in_w\)。先选，再换(贪得无厌后悔)]
3.既然已经变成了一个新图的问题，我们可以直接继续1和2的过程，直到找到一个没有圈的图。
2.2.tarjan s优化的朱刘算法(并行堆优化的朱刘算法)【某推荐博客】朱刘算法为o(n*m)，因为每次都需要枚举所有边来寻找最小边，导致复杂度can 不要减少。
那么让我们 让我们来看看优化算法的具体过程。
定义一个名词:搜索链是当前搜索的节点的链。(it 这只是作者的一种理解，并非论文的原始内容)
一、合同流程:\(复杂度:o(m*logn)\)。
第一步是为每个节点的边集建立一棵左斜树。第二步是从图中随机选择一个节点(默认为1)并将其推到搜索链的末尾。第三步，选择搜索链的最后一个节点(可能是收缩点之后的节点)，然后取出它的最小边，让边的另一端的节点为x，如果x不在链中，就放在搜索链的末端。如果x已经在搜索链中，说明有一个环，那么你需要收缩这个环。缩环的具体过程如下:1。newnode_id = circle_num获得了新的收缩点数。2.取出环上的所有节点y(①记录fa[t]=newnode_id形成环收缩点之间的树结构)(②记录此过程中与nxt数组的连接关系，提取过程中会用到)，合并它们的左偏树。3.最后，将新的夹点放在搜索链的末端(环上的节点已经在2中弹出搜索链。)并重复第三步，直到整个图收缩成一个点(这也是为什么事先加n条边，图就成了强连通块)。二、提取过程:直接调用extract(root，n)函数。\(复杂度:o(n)\)
上面的契约过程形成了一棵树。什么？;这棵树有什么用？
回顾构建这棵树的过程，我们实际上把所有有用的边都放在了这棵树上，所以我们可以推导出以下性质:
1.假设有n个原点和t个收缩点，那么树有nt个点和n条t-1边，最小树图的边一定在这些边中。
2.因为有t个收缩点，所以一定有t环。(因为每个收缩过程都会产生一个收缩点，而且它们的数量是一样的)。
3.最小树图有n-1条有向边，即从n个t-1条边中删除t条边(每个t环只删除一条边)。
有了上面的解释，我们就可以理解提取过程了(假设top是最后一个凝聚点的编号)。
第一步是在root上调用extract(root，top)函数。(设x =根)第二步，取出x所在的环(假设是c_id)加上除x的传入边以外的所有边的边权值..第三步，调用extract(v，c_id)函数到环上的其他节点。第四步，使x=fa[x]，继续第二步和第三步，直到x=top。仔细考虑这个过程，发现有点像从根开始dfs，每个环去掉一条边，最后得到dmst的权重。
算法是聪明的，我仍然有一些我不 写完这些我就不懂了。。。。这个树形结构真的很奇妙，搜索也很混乱。
三、区别(理解不同):
在实现/思路上，朱刘算法更像最小生成树的boruvka算法，而tarjan优化更像prim算法的实现(每次从更新链的末端增加一个点，看是否形成回路)，可能是因为回路是通过优化后搜索一条路径找到的。
1.固定根节点的模板代码:(之前模板的一些细节没有调整——注意:在契约函数中，a==b和！堆退出)
检查代码结构edge {int u，v；ll w；};命名空间左侧{ struct data { edge * e；ll val} dat[maxn]；//数据结构int top，heap [maxn]，lc [maxn]，rc [maxn]，dep [maxn]，tag[maxn]；// maxn需要设置为m n，因为边是复用的，空间不大，设置为2*m void initheap(int n) {top = 0也可以；for(int i = 0；i = n；i)heap[i]= 0；}int newheap(edge* e) { top，dat[top] = {e，e-w }；//将e-w赋值给valtag[top]= dep[top]= lc[top]= rc[top]= 0；返回顶部；}void add(int x，int v) { dat[x]。val = v，tag[x]= v；} void push _ down(int x){ if(lc[x])add(lc[x]，tag[x])；if (rc[x]) add(rc[x]，tag[x])；tag[x]= 0；}int merge(int x，int y) { if(！x ||！y)返回x | y；if (dat[x].val dat[y]。val) swap(x，y)；push _ down(x)；//降标rc[x] = merge(rc[x]，y)；if(dep[rc[x]]dep[lc[x]])swap(lc[x]，rc[x])；dep[x]= dep[rc[x]]1；返回x；}数据*pop(int x){ data * ret = dat[x]；x = merge(lc[x]，rc[x])；返回ret}};//命名空间leftist使用命名空间leftistvectorvector: id(id[x])；} void contract{ init h:已经完成缩分，退出循环if(！vis[a]继续；//符合对于未满足的新点，加链尾//满足环，缩环，n为(a = b，n；答！= n；a = p) {// p是下一个点的id[a]= fa[a]= n；if (h: p]= a；//记录环中下一个节点是谁}} intextract (int x，int t){ int ret = 0；for(；x！= t；x = fa[x]) {//展开节点for (int u = nxt[x]，tmpu！= x；u = nxt[u]) {//这里u是v的祖先节点，也就是u是v节点所在的收缩点(但是id(v)！=u，因为最后id(v)= n)if(ed[u]-e-w = inf _ int |(tmp = extract(ed[u]-e-v，u)) = inf _ int)返回inf _ int；ret = tmp ed[u]-e-w；//edge . emp(e)；//记录选择此边}}返回ret} void solve{ cin n m rt；inedge . assign(n ^ 2，{ })；//注意n ^ 2，需要多开一个(而不是n ^ 1)for(int i = 1，x，y，w；i = m；i ) cin x y w，inedge[y]。emp(edge{x，y，w })；for(int i = 1；i = n；i)i edge[i % n 1]。emp(edge{i，i % n 1，inf _ int })；合同；ll ans = extract(rt，n)；if(ans = inf _ int)cout-1 endl；else cout ans endl}2.不定根最小dmst模板-模板问题:
把一个数字当作超级源点，超级源点到其他点的距离是所有边权重之和，保证只使用一条这样的边。
最后的结果是不定根dmst。(注意题目是否需要输出相同边权重下最小数的根)
检查代码结构edge {int u，v；ll w；};namespace leftist {// val可以输出最小根数的结构数据{ edge * e；pll val} dat[maxn]；int top，heap[maxn]，lc[maxn]，rc[maxn]，dep[maxn]，tag[maxn]；void init heap(int n){ top = 0；for(int i = 0；i = n；i)heap[i]= 0；}int newheap(edge* e) { top，dat[top] = {e，{e-w，e-v } }；tag[top]= dep[top]= lc[top]= rc[top]= 0；返回顶部；}void add(int x，int v) { dat[x].val.fi = v，tag[x]= v；} void push _ down(int x){ if(lc[x])add(lc[x]，tag[x])；if (rc[x]) add(rc[x]，tag[x])；tag[x]= 0；}int merge(int x，int y) { if(！x ||！y)返回x | y；if (dat[x].val dat[y]。val) swap(x，y)；push _ down(x)；//降标rc[x] = merge(rc[x]，y)；if(dep[rc[x]]dep[lc[x]])swap(lc[x]，rc[x])；dep[x]= dep[rc[x]]1；返回x；} data * pop(int x){ data * ret = dat[x]；x = merge(lc[x]，rc[x])；返回ret}};//命名空间leftist使用命名空间leftistvectorvector: id(id[x])；} void contract{ init h: p]= a；//记录环中下一个节点是谁}} intextract (int x，int t){ int ret = 0；for(；x！= t；x = fa[x]) {//展开节点for (int u = nxt[x]，tmpu！= x；u = nxt[u]) {//这里u是v的祖先节点，也就是u是v节点所在的收缩点(但是id(v)！=u，因为最后id(v)= n)if(ed[u]-e-w = inf _ int |(tmp = extract(ed[u]-e-v，u)) = inf _ int)返回inf _ int；ret = tmp ed[u]-e-w；//edge . emp(e)；//记录选择这条边//if(ed[u]-e-u = = rt)root _ v = ed[u]-e-v-1；//也可以在这里记录答案} } ret ret；} void solve{ cin n m；sum = 0；inedge.assign(2 n，{ })；//因为多了一个节点，所以需要为(int i = 1，x，y，w；开n 2个桶(hdu数据卡住了我；i = m；i ) cin x y w，x，y，inedge[y]。emp(edge{x，y，w})，sum = w；rt = n；for(int i = 1；i = n；i)i edge[i % n 1]。emp(edge{i，i % n 1，inf _ int })；for(int i = 1；i n；i ) inedge[i]。emp(edge{rt，i，sum 1 })；合同；ll ans = extract(rt，n)-sum-1；root _ v = ed[nxt[rt]]-e-v-1；如果(答案= sum 1 | | ans = inf _ int)cout 不可能的else cout ans root _ v \ n \ n }
3.练习(1)ggs_ddu【经典画法】
看题目给出的条件，题目分析知道构建有向图，但状态不会设计。以前遇到这种问题的时候，我只是用压力来表达状态。我没有。;don’不要指望这个问题能把所有的主题作为一个点分开。
解题思路:把每门课程的每个阶段都当作一个节点，总共不超过500个节点。当且仅当从源点到一个状态至少有一条路径时，才能达到该状态。因为题目要求的代价最小，这条路径显然应该是权重最小的一条，只需要一条路径。
如果我的主体a到达阶段100，我可以到达小于阶段100的所有节点，所以我添加一个权重为(i1-i)0的边。最后，运行一次最小树形图。如果每个叶节点都在图上，则计算最小答案，否则无解。
标签:
节点最小值
了解更多最小树图算法(最小树图假设)相关内容请关注本站点。