[NOIP2017 提高组] 宝藏
状态压缩好题。下面我们来一一分析一下这道题的总体想法。
容易发现，\(n\leq12\)暗示这道题时间复杂度为指数级别的。
由于题目表明
两个已经被挖掘过的宝藏屋之间的道路无需再开发。
所以，我们开发的路径构成的只能是一棵树，不能是有环的图。
因此，我们可以将题目抽象成：给定一张有\(n\)个点的图，求出一棵生成树（根节点任意）使 \(\sum_{u\in G,fa_u\in G} dep_u\times w(u,fa_u)\)最小。
由于\(n\)很小，不难想到可以使用状态压缩。
我最开始的想法是：枚举根节点\(root\)，并定义以当前的根为根节点的状态：\(d(i,j,S)\)代表当前叶子结点\(j\)距\(root\)距离为\(i\)时，正处理的点集是\(S\)的最小值。
那么\(i\geq2\)时有如下转移：\(dp(i,j,S)=min(dp(i-1,k,S\setminus\{i\})+i\times d(i,k))\)。
而\(j=1\)有：\(dp(i,j,S)=min(dp(x,k,S\setminus\{i\})+d(j,root))\)。
初始化：让\(dp(0,root,0)=0\)，其余\(\infty\)。
这样的做法效率大约是：\(O(n^42^{n})\)，实际测试中所有的状态是跑不满的，故这种做法是可以通过本题目的时间限制的。
我们注意到刚刚那个转移是相当混乱的，并且它会重复计算状态值。
我们上述做法本质上是利用叶子结点向上逆推推的过程。那么，我们是否可以反过来想——从一个结点向它的子结点扩展，考虑剩下的子结点集合的代价。
根据此，我们来重新定义之前的状态表示：
\(dp(i,j,S)\)代表距离根节点距离\(i\)考虑到的当前结点为\(j\)，从\(j\)开始“挖”的点集为\(S\)的最小代价和。换句话来讲，我们只考虑以\(j\)为根的子树的代价。
那么有：\(dp(i,j,S)=min(dp(i+1,k,S'\setminus\{k\})+dp(i,j,S\setminus{S'})+d(j,k))\)，这里面的\(S'\)代表的是\(S\)中的子集，而k是S‘中的元素。
不难观察到，方程类似于树形DP中子树合并该重要思想。事实上，我们利用它解决树形依赖关系的一类问题（背包九讲）。
初始化，我们让\(dp(i,j,0)=0\)，其余正无穷，最终答案为\(min(dp(0,i,U\setminus\{i\}))\)。时间复杂度为\(O(n^32^n)\)，具体计算过于复杂，在此不展开。
在实现的过程中，为优化常数，我们可以预处理出所有状态下的元素个数、最小元素下标，以及将所有的点的下标平移。
另外，要注意边界条件。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define RE register
#define CLR(x, y) memset(x,y,sizeof x)
#define FOR(i, x, y) for(RE int i=x;i<=y;++i)
#define ROF(i, x, y) for(RE int i=x;i>=y;--i)
using namespace std;
const int N = 13, S = 1 << N, INF = 1e9 + 5;
typedef long long LL;
template <class T>
void read(T &x)
{
bool mark = false;
char ch = getchar();
for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') mark = true;
for(x = 0; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
if(mark) x = -x;
return;
}
int n, m, t, siz[S] = {}, tt[S] = {};
LL ans = INF, d[N][N], dp[N][N][S];
int main()
{
read(n), read(m);
t = 1 << n, -- t;
FOR(i, 0, n)
{
d[i][i] = 0;
FOR(j, i + 1, n) d[i][j] = d[j][i] = INF;
}
LL u, v, w;
FOR(i, 1, m)
{
read(u), read(v), read(w);
-- u, -- v;
d[u][v] = d[v][u] = min(d[u][v], w);
}
FOR(i, 1, t) siz[i] = siz[i & (i - 1)] + 1;
for(int i = 0; i < n; ++ i) tt[1 << i] = i;
FOR(i, 1, t) tt[i] = tt[i & (-i)];
CLR(dp, 0x3f);
for(int i = 0; i < n; ++ i)
for(int j = 0; j < n; ++ j)
dp[i][j][0] = 0;
for(int i = n - 2; i >= 0; -- i)
{
for(int j = 0; j < n; ++ j)
{
FOR(s, 1, t)
{
if((s & (1 << j)) || siz[t ^ s] <= i) continue;
for(int S1 = s; S1; S1 = (S1 - 1) & s)
{
for(int tmp = S1, k = tt[S1]; tmp; k = tt[tmp ^= tmp & (-tmp)])
if(d[j][k] < INF) dp[i][j][s] = min(dp[i][j][s], dp[i + 1][k][S1 ^ (1 << k)] + dp[i][j][s ^ S1] + (i + 1) * d[j][k]);
}
}
}
}
for(int i = 0; i < n; ++ i) ans = min(ans, dp[0][i][t ^ (1 << i)]);
printf("%lld\n", ans);
return 0;
}
总结：
- 当数据规模很小的时候，可以考虑状态压缩；
- 在考虑树上问题时往往从根节点开始考虑（像倍增一类的题目是从自己点开始考虑）；