【洛谷-P3959】[NOIP2017 提高组] 宝藏

位运算技巧#

位运算	功能	示例
$\texttt{x>>k}$	去掉最后 $k$ 位	$101101\rightarrow 101, k=3$
$\texttt{x<<k}$	在最后加 $k$ 个 $0$	$101101\rightarrow 101101000, k=3$
$\texttt{x<<1	1}$	在最后加一个 $1$
$\texttt{x	1}$	把第 $1$ 位变成 $1$
$\texttt{x	(1<<(k-1))}$	把第 $k$ 位变成 $1$
$\texttt{x	((1<<k)-1)}$	把末 $k$ 位变成 $1$
$\texttt{x\&(-2)}$	把第 $1$ 位变成 $0$	$1010111\rightarrow 1010110$
$\texttt{x \& (~(1<<(k-1)))}$	把第 $k$ 位变成 $0$	$1010110\rightarrow 1000110, k=5$
$\texttt{x\&(-(1<<k))}$	把末 $k$ 位变成 $0$	$1010110\rightarrow 1000000, k=5$
$\texttt{x \^{} 1}$	把第 $1$ 位取反	$101101\rightarrow 101100$
$\texttt{x \^{} (1<<(k-1))}$	把第 $k$ 位取反	$101001\rightarrow 101101, k=3$
$\texttt{x \^{} ((1<<k)-1)}$	把末 $k$ 位取反	$1101101\rightarrow 1100010, k=4$
$\texttt{x\&7}$	取末 $3$ 位	$1101101\rightarrow 101$
$\texttt{x\&(1<<(k-1))}$	取末 $k$ 位	$1101101\rightarrow 01101, k=3$
$\texttt{(x>>(k-1))\&1}$	取第 $k$ 位	$1101101\rightarrow 1, k=4$
$\texttt{x\&(x+1)}$	把末尾连续的 $1$ 变成 $0$	$100101111\rightarrow 100100000$
$\texttt{x	(x+1)}$	把右边第一个 $0$ 变成 $1$
$\texttt{x	(x-1)}$	把末尾连续的 $0$ 变成 $1$
$\texttt{(x \^{} (x+1))>>1}$	取末尾连续的 $1$	$100101111\rightarrow 1111$
$\texttt{x\&(-x)}$	取右边第一个 $1$ 及其右侧	$100101000\rightarrow 1000$

枚举子集、子集的子集#

枚举子集#

用 $T$ 表示 $S$ 的子集，则一种枚举子集的方式是：

$$\begin{array}{ll} 1& \textbf{for }( \textbf{int } \text{T = S; T; T=(T - 1) \& S)}\\ 2& \qquad \text{Do Something (T is a nonempty subset of S)} \end{array}$$

单次枚举 $T$ 的复杂度是 $\mathcal{O}(2^{|S|})$ 的。

枚举子集的子集#

若要枚举 $S$ 的所有子集的子集，可以证明复杂度为 $\mathcal{O}(3^n)$.

组合意义天地灭，代数推导保平安。

复杂度为：

$$\begin{aligned} \sum_{T\subseteq S}2^{|T|}=\sum_{i=1}^n\binom{n}{i} 2^i&=\sum_{i=1}^n\binom{n}{i}2^i1^{n-i}\\ &=(1+2)^n-1\Rightarrow \mathcal{O}(3^n) \end{aligned}$$

证毕，参考 枚举子集为什么是 O(3^n) 的 - Jijidawang - 博客园 ↗。

题意#

参与考古挖掘的小明得到了一份藏宝图，藏宝图上标出了 $n$ 个深埋在地下的宝藏屋， 也给出了这 $n$ 个宝藏屋之间可供开发的 $m$ 条道路和它们的长度。

小明决心亲自前往挖掘所有宝藏屋中的宝藏。但是，每个宝藏屋距离地面都很远，也就是说，从地面打通一条到某个宝藏屋的道路是很困难的，而开发宝藏屋之间的道路则相对容易很多。

小明的决心感动了考古挖掘的赞助商，赞助商决定免费赞助他打通一条从地面到某个宝藏屋的通道，通往哪个宝藏屋则由小明来决定。

在此基础上，小明还需要考虑如何开凿宝藏屋之间的道路。已经开凿出的道路可以 任意通行不消耗代价。每开凿出一条新道路，小明就会与考古队一起挖掘出由该条道路所能到达的宝藏屋的宝藏。另外，小明不想开发无用道路，即两个已经被挖掘过的宝藏屋之间的道路无需再开发。

新开发一条道路的代价是 $\mathrm{L} \times \mathrm{K}$。其中 $L$ 代表这条道路的长度，$K$ 代表从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的宝藏屋的数量（包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋） 。

请你编写程序为小明选定由赞助商打通的宝藏屋和之后开凿的道路，使得工程总代价最小，并输出这个最小值。

对于 $100\%$ 的数据： $1 \le n \le 12$，$0 \le m \le 10^3$，$v \le 5\times 10^5$。

题解#

状压DP。

找个生成树，代价和最小。

设 $f_{S, i}$ 表示当前包含的点集是 $S$，树高是 $i$，此时的最小代价和。

则：

$$f_{S, i}=\min_{T\subseteq S} \{f_{T, i-1}+w(T, S)\}$$

其中 $w(T, S)$ 代表从 $T$ 变到 $S$ 的代价，预处理。

预处理时，先找新增加的点，再找从 $T$ 连到这个点的最小边权，求和即可。顺便判断不合法的 $(T, S)$ 组合。