[NOIP2017] 宝藏

迈不过友情╰ 2021-12-19 04:59 186阅读 0赞

[题目链接][Link 1]

**题意**

题面过长，自行传送...

**分析**

乍一看就是个搜索剪枝，然而正解是状压DP

我们用二进制表示可以到达的点的集合，设 $d\[i\]\[s\]$ 表示从点集 $s$ 直接到达点 $i$ 的最短路径长度，$f\[i\]\[s\]$ 表示加入深度为 $i$ 的点后点集 $s$ 所需的最小代价（深度为起点到该点最少经过的点数）

首先枚举 $s$ 处理出 $d$ 数组，然后按照深度依次更新 $f$ 数组，每个深度下枚举 $s$ ，取其所有子集直接到达其的最小代价，最后得到答案

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    #include <cmath>
    using namespace std;
    #define ll long long
    #define inf 6000000
    #define N 13
    
    int n, m, u, v, w, all;
    int g[N][N], f[N][1 << N], d[N][1 << N];
    
    int main() {
        scanf("%d%d", &n, &m);
        all = (1 << n) - 1;
        for (int i = 1; i <= n; i++)
            for (int j = 0; j <= all; j++)
                d[i][j] = f[i][j] = inf;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                g[i][j] = inf;
        for (int i = 1; i <= n; i++) g[i][i] = 0;
        for (int i = 1; i <= m; i++) {
            scanf("%d%d%d", &u, &v, &w);
            g[u][v] = g[v][u] = min(g[u][v], w);
        }
        for (int s = 0; s <= all; s++)
            for (int i = 1; i <= n; i++)
                if ((1 << (i - 1)) & s)
                    for (int j = 1; j <= n; j++)
                        if (!((1 << (j - 1)) & s))
                            d[j][s] = min(d[j][s], g[i][j]);
        for (int i = 1; i <= n; i++) f[1][1 << (i - 1)] = 0;
        for (int i = 2; i <= n; i++)
            for (int s = 0; s <= all; s++)
                for (int k = s; k; k = (k - 1) & s) {
                    int tot = 0;
                    for (int j = 1; j <= n; j++)
                        if ((1 << (j - 1)) & (k ^ s))
                            tot += d[j][k];
                    f[i][s] = min(f[i][s], f[i - 1][k] + (i - 1) * tot);
                }
        printf("%d\n", f[n][all]);
    
        return 0;
    }

转载于:https://www.cnblogs.com/Pedesis/p/10991150.html

[Link 1]: https://www.luogu.org/problemnew/show/P3959
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211218/d114ac85e3d94e388a1c576a6de3f49b.png