Connectivity 2

题意

Link

题解

比较有趣。

如果从单纯的做题角度，这个题似乎就没有那么有趣了，对我而言。

大意，给你个图，每条边都可以保留或切断，问有多少种方式，使得最终 \(1,k\) 联通。

---

\(n\leq 17\) 很容易想到bitmask(状压)。

如果对于边的状压，不好处理连通性，也有太多状态。

那么就从连通性直接状压。

\(f(S)\) 表示提取 \(S\) 点集，在 \(S\) 中点联通的方案数。

由于只考虑子图，为了叙述方便记录 \(cnt(S)\) 表示上述 \(S\) 子图的边的个数。

---

全部联通这个要求显然是难的。

正难则反，朴素容斥一下。

算出随意切边的情况减去不连通。

接下来的转移比较巧妙，通过枚举任一 \(x\in S\)。

考虑 \(x\) 在什么连通块中，若 \(x\) 恰好在 \(T\subset S\) 中，那么 \(T\) 与 \(\overline T\) 之间一定没有边，此时可以让 \(\overline T\) 随机连边。

仔细思考这样所枚举不连通的一定不重不漏。 \[ \text{trans : }f(S)=\sum_{x\in T\subset S} f(T)2^{cnt(\overline T)} \]

\[ \text{calculate ans : } a_k=\sum_{1\in T,k\in T} f(T)2^{cnt(\overline T)} \]

$ $