标签 斯坦纳树 下的文章

洛谷4294 [WC2008]游览计划

Luogu 分析 斯坦纳树模板题。 设 $f_{i, S}$ 表示 $i$ 号结点，与其它节点连通性为 $S$ 时的最小代价。 转移分两种情况： 由子集转移而来 第二个方程是有后效性的，但是它长得很像三角形不等式，所以可以跑最短路转移。 代码 //It is made by M_sea #include <algorithm> #include <iostream...