最小生成树和动态规划

最小生成树 X 动态规划

/ \

F1: xxxx oooo

…………

常用算法有 Kruscal 和 Prime，以下会谈一些 MST 的性质和两种算法的证明

核心思路是证明任意时刻边集均为一颗 MST 的子集。

归纳的，令当前边集 $F$ 属于的 MST 为 $T$，考虑新加入的一条边 $e$，如果 $e\in T$，自然成立。

如果 $e\notin T$，那么 $e+T$ 构成了一个环，考虑该环上所有边 $E_i$，一定满足 $w_{E_i} \le w_e$，否则 $e$ 应该在 $T$ 中，得到更优的 MST，所以 $E_i$ 已经在 $e$ 之前被加入，构成了一条完整的链。

所以不会加入 $e$，进行下一步。

一般这种题都是指数级的题，有这道，这道，和这道

给你一张图，问任选 $i$ 条边，使得图联通的方案数有多少种。

记录联通性动态规划

考虑 $dp[mask][i]$ 表示子图 $mask$ 的答案，转移时发现重复了，因为两种不同的子图分配方案最后可能对应到同一种选边方式，所以我们需要一个顺序一类的东西来保证不重复。

一种比较可行的方式是计算记录顺序的情况下的方案，这样可以钦定枚举的两个子图一定是最后连上的，最后除以一个阶乘。

另一种方式是直接容斥，考虑计算选 $k$ 条边后不联通的答案，枚举得到的两个连通块就是断开的，还是有重复的问题，但是我们可以钦定每种图只会在与 $1$ 相连的连通块处被统计，这是经典的连通图计数方式。