//为了证明自己还活着赶紧写一篇文章.jpg

# 2. 题解

$f[i][j]$表示当前生成树的高度为 $i$，已选点的集合为 $j$

$f[i][k] = min(f[i – 1][j] + v[j][k] \times i)$

$v[j][k]$可以预处理。

（卡常比如可以用 Bfs 来 Dp 省掉不少没用的转移）

#pragma GCC optimize("Ofast,no-stack-protector")

#include <bits/stdc++.h>

#define NS (12)

using namespace std;

template <typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

typedef long long LL;

int n, m, d[NS][NS], dis[NS];

int v[1 << NS][1 << NS], f[NS][1 << NS], ans = INT_MAX;

int main(int argc, char const* argv[])
{
IN(n), IN(m), memset(d, 63, sizeof(d)), memset(v, 63, sizeof(v));
if (n == 1) puts("0"), exit(0);
for (int i = 1, a, b, c; i <= m; i += 1)
{
IN(a), IN(b), IN(c), a--, b--;
d[a][b] = d[b][a] = min(d[a][b], c);
}
for (int i = (1 << n) - 1; i > 1; i -= 1)
for (int j = ((i - 1) & i); j; j = ((j - 1) & i))
{
memset(dis, 63, sizeof(dis)), v[j][i] = 0;
for (int x = 0; x < n; x += 1) if ((j >> x) & 1)
for (int y = 0; y < n; y += 1)
if (((i >> y) & 1) && !((j >> y) & 1))
dis[y] = min(dis[y], d[x][y]);
for (int y = 0; y < n; y += 1)
if (((i >> y) & 1) && !((j >> y) & 1))
{
if (dis[y] > 1e9) {v[j][i] = 1e9; break;}
else v[j][i] += dis[y];
}
}
for (int x = 0; x < n; x += 1)
{
memset(f, 63, sizeof(f)), f[0][1 << x] = 0;
for (int i = 1; i < n; i += 1)
{
for (int s = (1 << n) - 1; s > 1; s -= 1)
for (int z = ((s - 1) & s); z; z = ((z - 1) & s))
f[i][s] = min((LL)f[i][s], (LL)f[i - 1][z] + (LL)i * v[z][s]);
ans = min(ans, f[i][(1 << n) - 1]);
}
}
printf("%d\n", ans);
return 0;
}


### 1 条评论

#### 【题解】 NOIP 2017 题解 – K-XZY · 2018年10月23日 10:52 下午

[…] 题解见：https://www.k-xzy.xyz/archives/9443 […]