road

黄色的树林里分出两条路 可惜我不能同时去涉足 我在那路口久久伫立 我向着一条路极目望去 直到它消失在丛林深处 但我却选择了另外一条路 它荒草萋萋，十分幽寂 显得更诱人，更美丽 虽然在这条小路上 很少留下旅人的足迹 那天清晨落叶满地 两条路都未经脚印污染 呵，留下一条路等改日再见 但我知道路径延绵无尽 ......

题意：有一个旅游区，旅游区有很多的景点，景点间需要开通缆车，使得任意两个景点可以互相到达。现在给出一些点间的缆车线路制造成本，两个景点之间可能有多重制造方式。问最少的花费是多少。 分析：连通+最少的花费 = 最小生成树。 Prim算法适用于稠密图, Kruskal适用于稀疏图 好家伙，两个 runt ......

~~看到 $n\le 70$，想到状压 DP。~~ 首先，显然对于一棵最小生成树，每个轻边连通块内部都是一棵树，轻边连通块缩点后点之间的重边也是一棵树。也就是说，缩点后不存在重边组成的环（包括自环），路径一旦离开了一个轻边连通块就再也不会回来了。 于是先洪水填充求出连通块，设共有 $k$ 个连通块。 ......