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

让我们病娇地学习 QvQ

1. 题目

传送门=￣ω￣=

2. 题解

这题状态比较妙。。。

题目要生成树嘛。。。

首先可以想到枚举根节点，也就是直接从地面打通哪个点。

然后设 $f[i]$表示状态为 $i$时的最小花费。

枚举 $i$的超集 $j$（准确地说是 “真超集”），然后从 $i$转移到 $j$

但是你会发现转移不是很好搞——相同的 $i$集合中的每个点到根的距离有不同的可能。

因此我们给状态添加一维，状态变成：

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

那么枚举 $j$的超集 $k$，使得那些包含在 $k$中却不包含在 $j$中的点都接在第 $i + 1$层，这样新加入的点的贡献就都能算了。

为什么这样是正确的呢？

因为很显然这个状态的设置覆盖了所有可能情况，那些新加入的点如果能放在比 $i + 1$层更浅的层的情况一定会在别的转移中考虑到。

这样就能这样转移了：

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

其中 $v[j][k]$表示从状态 $j$转移到状态 $k$的最短路之和。

即 $k$比 $j$多出的那些点到点集 $j$的最短路之和。

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

总复杂度 $O(n ^ 2 \times 3 ^ n)$

需要卡卡常。

我就懒得卡了，开个 pragma 完事。

（卡常比如可以用 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;
}