状压 + 转移辅助
宝藏
思路
看 $n$ 的范围显然状压，考虑直接枚举起点，主要问题是转移时每个点的距离不知道，而且无法压缩记录
考虑从转移入手，每次直接拓展一层，具体的：定义 $d[i, j]$ 表示“当前在 $i$ 层且已经联通的集合为 $j$ 的最小代价”，再记 $val[i, j]$ 表示“从集合 $j$ 转移到集合 $i$ 的最小路径长度和”，那么就有转移 $d[i, j] = \min(d[i - 1, k] + val[j, k] * (i - 1))$ ，我们巧妙的利用更改转移方式来解决状态无法描述的问题
这里还有一个问题： $val[j, k]$ 中的连接方式可能无法保证所有新加的节点都在第 $i$ 层，但其实不要紧，因为我们求的是最优而不是计数，把代价多算的答案显然会被正确的答案淘汰
代码
小技巧是枚举子集可以 T = (T - 1) & S ，以及注意 $INF$ 加多了会炸 long long
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #include <bits/stdc++.h>
using LL = long long;
const int N = 12 + 5, inf = 0x3f3f3f3f, NN = (1 << 12) + 100;
const LL INF = 1e18;
int n, m, G[N][N];
LL d[N][NN], ans = INF, val[NN][NN];
void dp(int st)
{
for (int i = 1; i <= n; ++i)
for (int j = (1 << n) - 1; j; --j) d[i][j] = INF;
d[1][1 << (st - 1)] = 0;
for (int i = 2; i <= n; ++i)
for (int j = (1 << n) - 1; j; --j)
for (int k = j; k; k = (k - 1) & j) if (d[i - 1][k] < INF && val[j][k] < INF) d[i][j] = std::min(d[i][j], d[i - 1][k] + val[j][k] * (i - 1));
for (int i = 1; i <= n; ++i) ans = std::min(d[i][(1 << n) - 1], ans);
}
int main()
{
scanf("%d %d", &n, &m);
std::memset(G, 0x3f, sizeof G);
for (int i = 1, u, v, w; i <= m; ++i)
{
scanf("%d %d %d", &u, &v, &w);
G[u][v] = G[v][u] = std::min(G[u][v], w);
}
for (int i = (1 << n) - 1; i; --i)
for (int j = i; j; j = (j - 1) & i)
for (int k = 1; k <= n; ++k) if (((i >> (k - 1)) & 1) && !((j >> (k - 1)) & 1))
{
int t = inf;
for (int p = 1; p <= n; ++p) if ((j >> (p - 1)) & 1) t = std::min(t, G[k][p]);
if (t == inf)
{
val[i][j] = INF;
break;
}
val[i][j] += t;
}
for (int i = 1; i <= n; ++i) dp(i);
printf("%lld\n", ans);
return 0;
}
|