「学习笔记」朱 - 刘算法求解最小树形图

什么是最小树形图

无向图上有最小生成树，那么有向图上呢？有向图上的最小生成树称为 “最小树形图”，英文叫 Directed Minimum Spanning Tree。

如果把一个树形图的有向边替换成无向边，它会变成一棵生成树。但与生成树不同的是，树形图中会确定一个根，它必须满足根能够到达每个结点。最小树形图是所有树形图中边权和最小的一个。

朱 - 刘算法简介

一般来讲在图中求最小树形图时会确定一个根结点。有一个时间复杂度为 $O(nm)$ 的算法可以解决这个问题：朱 - 刘算法（英文 Chu - Liu Algorithm），是两个中国人一起发明的算法。

朱 - 刘算法的基本思想是每次贪心地选出每个点最小的父亲，得出的图如果不是树形图，那么将选出的环进行缩点，对边权进行修改，然后迭代这个过程，直到图变为最小树形图为止。

朱 - 刘算法模版

建议看一下「模板」最小树形图（Luogu 4716） 这题的题解，里面有确定根结点的最小树形图详细的讲解。注意大部分题解的时间复杂度都是 $O(n^3)$ 而不是 $O(nm)$ 的，问题出在它们找环的过程不能保证复杂度。如果不会找环的话可以看看「NOIP 2015」信息传递（Luogu 2661）这题，题解中的复杂度都是正确的。

#include <cstdio>

朱 - 刘算法的应用

不确定根的最小树形图

这次我们不规定树形图的根，要求最小树形图。

容易发现我们建立一个超级源点，然后向每一个结点连长度为 $\inf$ 的边，最后算出答案后减去 $\inf$ 即可。发现为了使答案更优，最多只会从超级源点连出一条边，从而保证了去掉超级源点后的根是唯一的。

时间复杂度 $O(nm)$。

「BZOJ 4349」最小树形图

题目大意

「BZOJ 4349」最小树形图

有 $n$ 个堡垒，第 $i$ 个堡垒的防御力是 $A_i$，一共要打 $B_i$ 次。有 $m$ 组关系，每组形如 “打了 $x$ 号堡垒以后 $y$ 号堡垒的防御力都会降低为 $z$”，问打完所有堡垒的最小代价。

数据范围：$n \le 50$。

思路分析

容易发现最优策略是所有堡垒打完一遍再慢慢打剩下的，现在问题变成了决定第一次打堡垒的顺序。建立超级源点，向每个堡垒连权值为 $A_i$ 的边。对于每一条关系，从 $x$ 号堡垒向 $y$ 号堡垒连权值为 $z$ 的边即可。根据建图方式容易证明算法正确性。

时间复杂度 $O(nm)$。

代码实现

#include <cstdio>

「SCOI 2012」滑雪

题目大意

「SCOI 2012」滑雪（Luogu 2573）

给定 $n$ 个地点 $m$ 条边，每个地点有高度，每条边有通过时间，且起点高度大于等于终点高度。问这个图以 $1$ 为根的最小树形图。

数据范围：$n \le 10^5, m \le 10^6$。

思路分析

朴素算法不能通过，考虑利用这题的性质。

我们先搜出能够到达的所有点，再将边以终点高度为第一关键字，边权为第二关键字排序后，跑 Kruskal 即可。

时间复杂度 $O(m \log m)$。

代码实现

#include <cstdio>