题解 P3959 【宝藏】
_rqy
2017-11-13 18:02:33
qwq首先，prim是错误的，可以被这组数据卡掉：[数据](https://paste.ubuntu.com/25953020/)
然后，据说正解$O(4^n)$，而我的做法是$O(n^33^n)$，渐进意义上小但是$n \leq 12$的时候大。
然后，我的常数小至$\frac{1}{27}$，极限数据（就是12个点之间全有边）在sd的辣鸡WinXp上跑了0.8秒。luogu自测过了。
我的想法是dp。
状态：
$f_{i,j,S}(j \not\in S)$，表示从起点到节点j的距离为i，我现在要从j开始挖边，挖通集合S的最小代价。
转移时，我枚举从节点j打出的第一条边，假设它是j->k，再枚举从k要打到的子集$S_2\subset S$，那么
$$f_{i, j, S} = \min_{k \in S_2 \subset S} (d[j][k] * (i + 1) + f_{i + 1, k, S_2 - \{k\}} + f_{i, j, S - S_2})$$
最后取所有$f_{0,i,U-{i})$的最小值即可，其中$U$是全集。
时间复杂度。。。这个太难算，用了好多二项式系数恒等式，这里略去。
程序中先枚举的$S_2$后枚举的$k \in S_2$，并且预处理了每个集合的最小元素以加快枚举。
代码：
```cpp
#include <algorithm>
#include <cstdio>
#include <cstring>
namespace rqy{
const int N = 13;
const int INF = 0x3f3f3f3f;
int f[N][N][1 << N];
int siz[1 << N], ttt[1 << N];
int d[N][N];
void main() {
int n, m, x, y, z;
scanf("%d%d", &n, &m);
memset(f, 0x3f, sizeof f);
memset(d, 0x3f, sizeof d);
while (m--) {
scanf("%d%d%d", &x, &y, &z);
--x; --y;
d[y][x] = d[x][y] = std::min(d[x][y], z);
}
int up = 1 << n;
for (int i = 1; i < up; ++i) siz[i] = siz[i & (i - 1)] + 1;
for (int i = 0; i < n; ++i) ttt[1 << i] = i;
for (int i = 1; i < up; ++i) ttt[i] = ttt[i & -i];
for (int i = 0; i < n; ++i)
f[n - 1][i][0] = 0;
for (int j = n - 2; ~j; --j)
for (int i = 0; i < n; ++i) {
f[j][i][0] = 0;
for (int S = 1; S < up; ++S) if (((~S >> i) & 1) && (siz[S] <= n - j - 1))
for (int S2 = S; S2; S2 = (S2 - 1) & S) if (f[j][i][S & ~S2] < f[j][i][S]) {
int tmp = S2;
for (int k = ttt[tmp]; tmp; k = ttt[tmp &= ~(1 << k)])
if (d[i][k] < INF)
f[j][i][S] = std::min(f[j][i][S],
(j + 1) * d[i][k] + f[j + 1][k][S2 & ~(1 << k)] + f[j][i][S & ~S2]);
}
}
int ans = INF;
for (int i = 0; i < n; ++i) ans = std::min(ans, f[0][i][(up - 1) & ~(1 << i)]);
printf("%d\n", ans);
}
};
int main() {
rqy::main();
return 0;
}
```