题解 P3959 【宝藏】

· · 题解

这题千万不要去装逼写模拟退火。老老实实写DFS或DP。

关于dp，状态压缩是个很重要的知识点，可以帮助记忆化搜索骗分，帮助dp确定状态。

此题中一个很重要的东西就是距离K，K的存在使贪心的最小生成树不成立。

如果我们把起点看做根节点，记根节点的层数Deep为1，每次选取一部分点，与上一层的点相接，而在这个接起来的过程中，K是恒定的，就是等于上一层层数。

那么得到转移方程：

我们用01串来表示点，那么就可以化作二进制，$n$很小，$2^{12}$可以接受。 接下来就是求出一堆点$S_1$接上另外一堆$S_2$的代价了。 我们可以拆开来看，对于一堆点里的每一个点$i$，如果我们求出它与它要接上去的那堆点的代价，就可以求和一下算出总代价。 那么一个点拼接上的代价是什么呢？很明显，最小的边长啊！ 那么可以得到，如果$i$属于$S_1$，$j$属于$S_2$，那么$i$到$S_2$的最小代价$w_{iS_2}=min(v_{ij})$，$v$是$i$到$j$的边长。 于是转移方程就是：$dp_{kS_2}=dp_{k-1S_1}+(k-1)*\sum w_{iS_2}

代码：

#include <bits/stdc++.h>
using namespace std;

int n,mm;

long long m[14][15];
long long w[15][4100];
long long dp[15][4100];

//1<<(i-1)表示第i位为1
//j&(j-1)表示把自己所有子集都枚举一遍
//若j是i的子集,i-j是j的补集
//1<<n==2^n
//1<<n-1==2^0+2^1...+2^(n-1)

int main()
{
    memset(dp,0x3f,sizeof(dp));
    memset(m,0x3f,sizeof(m));
    memset(w,0x3f,sizeof(w));
    scanf("%d%d",&n,&mm);

    for(int i=1;i<=n;i++)
        dp[1][1<<(i-1)]=0;
    for(int i=1;i<=mm;i++)
    {
        int x,y;
        long long z;
        scanf("%d%d%lld",&x,&y,&z);
        m[x][y]=min(z,m[x][y]);
        m[y][x]=m[x][y];
    }

    for(int i=1;i<=n;i++)
    {
        for(int k=1;k<=(1<<n)-1;k++)
        {
            for(int j=1;j<=n;j++)
            {
                if((1<<(j-1)&k)&&(!(1<<(i-1)&k)))
                {
                    w[i][k]=min(w[i][k],m[i][j]);
                }
            }
            //cout<<w[i][k]<<"   "<<i<<"   "<<k<<endl;
        }
    }

    long long ans=0x3f3f3f3f3f3f;
    for(int i=1;i<=(1<<n)-1;i++)
    {
        for(int j=i&(i-1);j!=0;j=i&(j-1))
        {
            long long nw=0;
            for(int k=1;k<=n;k++)
            {
                if(1<<(k-1)&(i-j))
                {
                    if(w[k][j]>ans)
                        nw=0x3f3f3f3f3f3f;
                    else nw+=w[k][j];
                }
            }
            for(int k=2;k<=n;k++)
            {
                dp[k][i]=min(dp[k-1][j]+nw*(k-1),dp[k][i]);
            }
        }
    }
    for(int i=2;i<=n;i++)
    {
        ans=min(ans,dp[i][(1<<n)-1]);
    }
    if(ans>=0x3f3f3f3f3f3f)
    {
        printf("0\n");
    }
    else printf("%lld\n",ans);
}