题解 P3959 【宝藏】

[戳这里](http://www.vixbob-lwc.pw/index.php/archives/92/) 这道题应该是状压DP,这道题的题目就不多赘述了 用dp[i]来表示状态i下的最优方案,dis[j]表示j到根节点的距离（题目中所描述的K）用dfs来更新答案 ~~实现代码貌似很简单的样子~~ 下面直接上代码，`代码附注释` ```cpp #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; } ```