题解 P3959 【宝藏】

· · 题解

戳这里

这道题应该是状压DP,这道题的题目就不多赘述了

用dp[i]来表示状态i下的最优方案,dis[j]表示j到根节点的距离（题目中所描述的K）用dfs来更新答案

实现代码貌似很简单的样子

下面直接上代码，代码附注释

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define inf 2147483647
using namespace std;
int dp[1<<13],dis[15],G[15][15],isG[15][15],n,m,ans=inf;
//isG表示x,y之间是否有边
//点只有十二个直接上邻接矩阵即可
void insert(int x,int y,int w){G[x][y]=w;G[y][x]=w;isG[x][y]=1;isG[y][x]=1;}
//插边函数
void dfs(int x){
    for(int i=1;i<=n;i++){
    //枚举你所选点集中的每个点
        if((1<<(i-1))&x){
            for(int j=1;j<=n;j++){
                if(!(1<<(j-1)&x)&&isG[i][j])
                //判断能否选
                    if(dp[1<<(j-1)|x]>dp[x]+dis[i]*G[i][j]){
                    //有没有更新的必要
                        int temp=dis[j];
                        dis[j]=dis[i]+1;
                        dp[1<<(j-1)|x]=dp[x]+dis[i]*G[i][j];//将此状态更新
                        dfs(1<<(j-1)|x);//从此状态开始dfs
                        dis[j]=temp;//回溯
                    }
            }
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    memset(G,63,sizeof(G));//赋较大初值
    for(int i=1;i<=m;i++){
        int x,y,w;scanf("%d%d%d",&x,&y,&w);
        if(w<G[x][y])insert(x,y,w);
    }
    for(int i=1;i<=12;i++){
        memset(dis,63,sizeof(dis));
        for(int j=1;j<=(1<<n)-1;j++)dp[j]=inf;
        //每枚举一遍根节点就重置一遍
        dis[i]=1;dp[1<<(i-1)]=0;
        dfs(1<<(i-1));
        ans=min(ans,dp[(1<<n)-1]);//看答案是否能更新
    }
    printf("%d",ans);
    return 0;
}