NOIP2017提高组Day2T2 宝藏 洛谷P3959 状压dp

原文链接https://www.cnblogs.com/zhouzhendong/p/9261079.html

题目传送门 - 洛谷P3959

题目传送门 - Vijos P2032

题意

给定一个 $n$ 个节点 $m$ 条边的无向图。

现在请你在这个图之上生成一个有根树。

记 $d_i$ 为节点 $i$ 的深度 $(d_{root}=0)$ ，记 $fadis_i$ 为节点 $i$ 到其父亲节点的连边中的最小边权。

则这棵树的代价为

$$\sum_{i=1}^{n}(d_i\times fadis_i)$$

问所有生成树中最小代价为多少。

$1\leq n\leq 12,0\leq m\leq 1000, 边权\leq 500000$

题解

我们记 $dp[x][d][s]$ 表示以 $x$ 为子树根，其深度为 $d$ ，要在该子树内完成集合 $s$ 中节点的连接，所需要花费的最小代价。

则显然可以写出 DP 方程：

（其中 $g[x][y]$ 代表 $x$ 到 $y$ 的最小边权）

$$dp[x][d][s]=\min(dp[y][d+1][s1 \backslash \{y\}]+g[x][y]\times (d+1)+dp[x][d][s-s1]\bigg| s1\subset s)$$

至于集合 $s,s2$ 我们可以状压表示。

现在我们来分析一下时间复杂度。

首先我们看到前两维以及枚举 $y$ ，每一维一个 $O(n)$。

最重要的是最后一维。

这维的复杂度要和剩下的转移复杂度一起算，因为转移复杂度与这一维的数字有关。

如果这一维集合 $|s|=i$ ，则有 $2^i$ 种子集。满足 $|s|=i$ 的 $s$ 有 $\binom{n}{i}$ 个。

所以这两部分总的复杂度为：（其中要用到：二项式定理）

$$\begin{eqnarray*}\sum_{i=0}^{n}\binom{n}{i}2^i&=&\sum_{i=0}^{n}\binom{n}{i}2^i\times 1^{n-i}\\&=&(1+2)^n\\&=&3^n \end{eqnarray*}$$

所以总的复杂度为 $O(n^33^n)$ ，注意常数大会被卡。

写到这里不禁让我想起某猪。某猪他去年联赛当场写出 $O(n^23^n)$ 的做法，而我至今做出了这个做法，却懒得去做更好的。

写到这里不禁让我想起某猪。Orz

写到这里不禁让我想起某猪。我的洛谷本题提交记录的最前面永远的留下了他的代码，永远的留下了当年赌NOIP分数吃全家桶的记忆……

写道这里，我不禁想起当年那些又吵又闹有骂有笑有他和他的开心的时光。

写到这里，我又想起了当年天真的笑容们。过去的都过去了，他是否仍然是他？但愿如此，愿他一路顺风。

不写下去了，不再憋着那泪，空自伤心罢。

代码

！！！！！本代码在洛谷被卡常，需要开 $O2$ 才可以通过。！！！！！