斯坦纳树

不看 $c9$ 的博客我都不知道有这玩意儿。属实是菜到某种境界了。

目标是，在非负边权的无向图中，选出边权和最小的连通子图，使得 $k$ 个给定点在图中。显然只会选出树，树则有根。于是可以 $\mathtt{dp}$，记 $f(x,S)$ 为 $x$ 为根的树去连通 $S$ 内的关键点的最小代价。

根只有一个儿子则 $f(x,S)\leftarrow f(y,S)+w(x,y)$，有多个儿子则 $f(x,S)\leftarrow f(x,T)+f(x,S\setminus T)(T\ne \varnothing ,T⫋S)$ 。

转移顺序，显然可以按照 $|S|$ 升序。或者按照 $S$ 升序，二进制值意义下。然后做第二类转移是容易的，子集枚举嘛。

第一类转移就是最短路转移，可以直接 $\text{dijkstra}$ 等。

卡常术：应让 $S$ 为数组的第一个维度，这样最短路时的内存访问很连续。同时，第二类转移也该先枚举 $T$ 再枚举 $i$ 。

最小直径生成树

枚举直径的中点，则答案是它到所有点的最远距离乘 $2$ 。如果这不是中点，则该值偏大。

故只需找到图的中点，即最小化它到所有点的最远距离。

求出全源最短路，然后在每条边上找最优点。是个 $\mathcal{O}(n)$ 段分段函数，每段的 $\min$ 易求。复杂度 $\mathcal{O}(nm)$ 。

最小树形图

目标是，在带权有向图上，找出边权和最小的子图满足 $r$ 到每个点都存在唯一路径（即树形图）。边权是否非负不重要，因为给所有边加上大正数即可。

因为它比较像最小生成树，所以可以贪心。有点不自然？但是逻辑是相对严谨的。这被称作朱刘算法。

树形图等价于给除了 $r$ 的每个点选择入边，使得图中无环。因此，给 $r$ 以外的点选择最小权入边，如果这可以构成树形图，那肯定是最优解。

否则（存在最优解使得）该环上必有恰好一条边不选。因为一条边不选，说明无法调整，说明两侧的点有与这条边相反的可达关系；若环上有至少两条边不选，就能推出环形的可达关系，矛盾。

因此该环可以缩为单点，外部向内的连边变为要替换原定入边，即减去原定入边的边权。这个新的单点也只选择一个入边，即替换一条边，符合预期。

每轮缩点至少能缩掉一个点（并不是所有点都在环中，可能只有两个点成环，其余点构成树形图），总复杂度 $\mathcal{O}(nm)$，实际运行应该跑不满。

还有个 $\text{tarjan}$ 算法。让所有点向 $r$ 的连边，边权为 $+\infty$，不难验证这个流程是正确的：维护一个栈，初始时其中有任意点 $a$，每次取出栈顶与其最小入边，选择该入边。若已选择的入边构成环，显然是栈顶的若干点，缩点（新点仍放于栈顶），继续该流程直到整张图只剩一个点。

用并查集处理缩点，用可并堆（带标记）维护每个点的入边即可。复杂度 $\mathcal{O}(m\log m)$ 。

Comment. 奶奶滴，为什么我算出来的复杂度和 $\text{OI-wiki}$ 里写的不一样