题解 P3552 【[POI2013]SPA-Walk】

Lemma 1：对于一个 $n$ 维超立方体，将其分为两个点集，点集之间的边个数必不少于较小点集的大小。 证明：不会。 Lemma 2：对于一个 $n$ 维超立方体，去掉 $k$ 个点后最多形成一个大小大于 $nk$ 的连通块。 证明： 设有两个集合 $S_1, S_2$ 的大小均大于 $nk$。 设 $S$ 为所有点构成的集合，则$S_2\subset S-S_1$ 根据 Lemma1, 容易知道 $S_1, S-S_1$ 之间边数大于等于二者较小者大小，即 $nk+1$。 然后我们惊奇的发现我们只删了 $k$ 个节点，总共删了 $nk$ 条边，并无法将这两个连通块断开。 故得证。 故爆搜即可。注意常数。 Q：我也不知道 Lemma 1 我怎么会做呢？ A：原题题面中给了 Lemma 1。但是这儿没有。