题解 P3552 【[POI2013]SPA-Walk】

YLWang · 2020-08-21 17:42:04 · 题解

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。但是这儿没有。