题解 | 宝藏-NOIP2017提高组复赛

算法知识点: 状态压缩DP

复杂度：

解题思路：

参考这篇题解所写。

状态压缩DP，下文中i是一个 位二进制数，表示每个点是否存在。

状态f[i][j]表示：

• 集合：所有包含i中所有点，且树的高度等于j的生成树
• 属性：最小花费

状态计算：枚举i的所有非全集子集S作为前j - 1层的点，剩余点作为第j层的点。
核心： 求出第j层的所有点到S的最短边，将这些边权和乘以j，直接加到f[S][j - 1]上，即可求出f[i][j]。

证明：
将这样求出的结果记为f'[i][j]

• f[i][j]中花费最小的生成树一定可以被枚举到，因此f[i][j] >= f'[i][j]；
• 如果第j层中用到的某条边(a, b)应该在比j小的层，假设a是S中的点，b是第j层的点，则在枚举S + {b}时会得到更小的花费，即这种方式枚举到的所有花费均大于等于某个合法生成树的花费，因此f[i][j] <= f'[i][j]

所以有f[i][j] = f'[i][j]。

C++ 代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 12, M = 1 << 12, INF = 0x3f3f3f3f;

int n, m;
int d[N][N];
int f[M][N], g[M];

int main()
{
    scanf("%d%d", &n, &m);

    memset(d, 0x3f, sizeof d);
    for (int i = 0; i < n; i ++ ) d[i][i] = 0;

    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        a --, b --;
        d[a][b] = d[b][a] = min(d[a][b], c);
    }

    for (int i = 1; i < 1 << n; i ++ )
        for (int j = 0; j < n; j ++ )
            if (i >> j & 1)
            {
                for (int k = 0; k < n; k ++ )
                    if (d[j][k] != INF)
                        g[i] |= 1 << k;
            }

    memset(f, 0x3f, sizeof f);
    for (int i = 0; i < n; i ++ ) f[1 << i][0] = 0;

    for (int i = 1; i < 1 << n; i ++ )
        for (int j = (i - 1); j; j = (j - 1) & i)
            if ((g[j] & i) == i)
            {
                int remain = i ^ j;
                int cost = 0;
                for (int k = 0; k < n; k ++ )
                    if (remain >> k & 1)
                    {
                        int t = INF;
                        for (int u = 0; u < n; u ++ )
                            if (j >> u & 1)
                                t = min(t, d[k][u]);
                        cost += t;
                    }

                for (int k = 1; k < n; k ++ ) f[i][k] = min(f[i][k], f[j][k - 1] + cost * k);
            }

    int res = INF;
    for (int i = 0; i < n; i ++ ) res = min(res, f[(1 << n) - 1][i]);

    printf("%d\n", res);
    return 0;
}