洛谷3959 宝藏

原题链接

这题我是用了个玄学的\(dfs\)剪枝跑过，如果要看正解状压\(DP\)，可以移步机房大佬的博客（传送门）
关于剪枝，具体的直接在代码里说吧。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 20;
int ne[N][N], dis[N][N], chu[N], de[N], q[N], lev[N], l, o, rem, mi = 1e9, n;
//邻接矩阵存图，ne表示该点所指向的点，chu是该点的出度，dis是该点与下一个点之间的距离
//q是dfs搜索的队列，即已经拓展的点，l是队列q的长度，lev是点的深度，即题面中的K，rem用于关键剪枝
//mi储存最优解，o为sort的compare函数里所用
inline int re()//快读
{
    int x = 0;
    char c = getchar();
    bool p = 0;
    for (; c < '0' || c > '9'; c = getchar())
        p |= c == '-';
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    return p ? -x : x;
}
bool comp(int x, int y)//sort的compare函数，根据两点间距离进行排序
{
    return dis[o][x] < dis[o][y];
}
inline int minn(int x, int y)
{
    return x < y ? x : y;
}
void dfs(int fir, int nxt, int s, int po)
{
    if (!(po ^ n))//如果n个点都被拓展了，就更新答案
    {
        mi = minn(mi, s);
        return;
    }
    if (s >= mi)//最优解剪枝
        return;
    int i, j, x, y;
    for (i = fir; i <= l; i++)//从队列的第fir个点开始尝试
    {
        if (s + rem * lev[x = q[i]] >= mi)//若当前解加上理论最优解依然不能更新答案，那么舍去
            continue;
        for (j = nxt; j <= chu[x]; j++)//从这个点能到达的点中的第nxt个点开始尝试拓展
            if (!lev[y = ne[x][j]])//如果没有被拓展
            {
                lev[y] = lev[x] + 1;//将该点拓展
                q[++l] = y;
                rem -= dis[y][ne[y][1]];//更新理论最优解
                dfs(i, j + 1, s + dis[x][y] * lev[x], po + 1);
                l--;//回溯
                lev[y] = 0;
                rem += dis[y][ne[y][1]];
            }
        nxt = 1;//注意要搜下一个点的时候需重新从第1个点开始尝试
    }
}
int main()
{
    int i, m, x, y, z;
    n = re();
    m = re();
    memset(dis, 60, sizeof(dis));
    for (i = 1; i <= m; i++)
    {
        x = re();
        y = re();
        z = re();
        if (dis[x][y] > 1e9)
        {
            ne[x][++chu[x]] = y;
            ne[y][++chu[y]] = x;
        }
        dis[x][y] = dis[y][x] = minn(dis[x][y], z);
    }
    for (o = 1; o <= n; o++)
    {
        sort(ne[o] + 1, ne[o] + chu[o] + 1, comp);//根据距离对点o所能到达的点进行排序
        rem += dis[o][ne[o][1]];//将每个点到其它点的最近距离累加起来，就是取n条边的理论最优解
    }
    for (i = 1; i <= n; i++)
    {
        q[1] = i;//将第i个点作为出发点，加入队列
        rem -= dis[i][ne[i][1]];//要减去该点到其它点的最近距离，剩下的才是对于未拓展点的理论最优解，即假设剩下每个点到其它点的最近距离都是连在该点上
        l = lev[i] = 1;//初始化队列长和深度
        dfs(1, 1, 0, 1);
        lev[i] = 0;//回溯
        rem += dis[i][ne[i][1]];
    }
    printf("%d", mi);
    return 0;
}

洛谷3959 宝藏

原文：https://www.cnblogs.com/Iowa-Battleship/p/9723253.html