洛谷P3959 宝藏

题目

状压DP或者随机化贪心，DFS也能过，但需要掌握很多的搜索剪枝技巧。

本题的搜索剪枝技巧主要采用了减少重复的计算和最优化剪枝。

减少重复计算

由于原图被分为了两块，一块是已经被挖掘的点，一块是还未被挖掘的点。我们考虑每次枚举下一个要加上的点的时候，肯定要找到未被挖掘的点。为了枚举的时候快速的找到未被挖掘的点，我们肯定不能O(n)找没有枚举的点。我们记录被挖掘的点，枚举他们的出边，找到未被挖掘的点，然后更新答案。这里又有一个小技巧，出边的枚举不能每次都从零开始，而应该直接从上一次最后枚举的边开始，因为，此点之前枚举的边已经被挖掘了，进入被挖掘的集合了。所以我们用pos1，pos2作为搜索的状态，分别为最后一个被挖掘的点，该点最后一个被枚举的边，即可大幅提升运行速度。（这样枚举的优点还有一个当前被挖掘的集合里深度是有序的，因为后加入集合的点一定）

提示：在爆搜算法里，任何小小的步骤都会大幅影响整个程序的时间复杂度。

最优化剪枝

仅仅有减少重复计算还不够，主要还是要有最优化剪枝。

我们可以用\(mindis[i]\)记录\(i\)链接的所有边的最小值。

如果当前要枚举的未被挖掘的点的\(mindis\)和乘上当前最优深度还是比最优解大的话，则肯定无法取得最优解。

因此可以在搜索的时候维护mindis和，以及当前的深度，挖掘到一个点就减去该点的mindis，并且加入该扩展边的代价。

然后就可以枚举起点dfs搜索并更新最小值了。

#include <bits/stdc++.h>
#define inf 1061109567
using namespace std;
int n, m, mp, ans, now, totn, dis[101][101], to[101][101], vis[101], cnt[101], used[101], mindis[101];//used表示当前选择的点的编号
int minn = 2147483647; 
bool cmp(int a, int b) {return dis[mp][a] < dis[mp][b];}
void dfs(int pos1, int pos2)
{
    if (totn == n)
    {
        minn = min(ans, minn);
        return;
    }
    for (int k = pos1; k <= totn; k++)//直接搜索当前还没有搜索完边的点，搜索要减少重复计算，我们之前的点肯定都已经搜索过了，因此不许要在继续搜索了。 
    {
        int i = used[k];
        if (ans + now * vis[i] >= minn) return;//当前的最优长度乘上当前的最优深度即为最优解 
        for (int j = pos2; j <= cnt[i]; j++)
        {
            int t = to[i][j];
            if (vis[t]) continue;
            used[++totn] = t;
            vis[t] = vis[i] + 1;
            ans += dis[i][t] * vis[i];
            now -= mindis[t];
            dfs(k, j + 1);
            ans -= dis[i][t] * vis[i];
            now += mindis[t];
            vis[t] = 0;
            --totn;
        }
        pos2 = 1;
    }
}
inline void init()
{
    memset(dis, 0x3f, sizeof(dis));
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        if (dis[a][b] == inf)
            ++cnt[a], to[a][cnt[a]] = b, ++cnt[b], to[b][cnt[b]] = a;
        dis[a][b] = dis[b][a] = min(dis[a][b], c);
    }
    for (int i = 1; i <= n; i++)
        mp = i, sort(to[i] + 1, to[i] + cnt[i] + 1, cmp); 
    for (int i = 1; i <= n; i++)
        mindis[i] = dis[i][to[i][1]], now += mindis[i];
}
int main()
{
    init();
    for (int i = 1; i <= n; i++)
    {
        ans = 0;
        used[totn = 1] = i;
        vis[i] = 1;
        now -= dis[i][to[i][1]];
        dfs(1, 1);
        now += dis[i][to[i][1]];
        vis[i] = 0;
    }
    printf("%d", minn);
    return 0;
}

洛谷P3959 宝藏

原文：https://www.cnblogs.com/liuwenyao/p/11837287.html