不怪那天太冷 泪滴水成冰；春风也一样 没吹进凝固的照片。
arundo
·
·
题解
P3552 [POI2013]SPA-Walk 题解。
主要是补充一下第一个定理的证明。
还是先简述总流程。
定理 1. 对于 n 维超立方体上的点，将其划分为两个不交集合，则两个集合之间的边数不少于两集合大小的 \min。
定理 2. 在 n 维超立方体上删去 k 个点后最多只有一个点数大于 n\times k 的连通块。
根据以上两个定理，尝试从 S 和 T 分别出发 dfs，如果找到 n\times k+1 个点，说明其在大连通块内，退出。否则说明在小连通块内，看找到 T 没有即可。如果两边都没找到退出，那么若 S 和 T 都找到至少 n\times k+1 个点则均在唯一大连通块内，否则不在同一连通块。
最后证明两个定理。
证明 1. 对于两个超立方体上的点，定义其之间的特殊路径为将其二进制表示后，从前往后依次更改不相同的维度所形成的路径。
例如 \text{SP}(1001\to 0100) = 1001\to 0001\to 0101\to 0100。
对于任意一条边 x\to y，经过其的特殊路径数为 2^{n-1}。因为边只改了一个维度，且起点在该维度及其后与 x 相同，终点在该维度及其后与 y 相同，所以有 n-1 个位置可以自由选择。
对于两个不交集合 S、T，不妨设 |S|\le |T|，则集合间的特殊路径数为 |S||T|=|S|(2^n-|S|) 且 |S|\le {2^n\over 2}，每条特殊路径至少经过一条集合之间的边，所以边数 \ge {|S|(2^n-|S|)\over 2^{n-1}}\ge {|S|2^{n-1}\over 2^{n-1}}=|S|。
证明 2. 考虑反证法。设存在两集合都大于 n\times k 个点，根据前述结论它们之间至少有 $n\times k+1