题解 P2196 【挖地雷】

[题目传送门](https://www.luogu.org/problem/P2196) 直接上状压DP！！！ 令$f_{i,j}$表示取过的点的状态为i，当前在j点的最大地雷个数。状态转移直接扫描j点的所有出边就好了，DP方程$f[i|(1<<k-1)][k]=\min(f[i|(1<<k-1)][k],f[i][j]+a[k])$（j到k有边）。我用的是邻接矩阵存图。 注意：直接开$2^{20}*20$会MLE，要改成short。 代码： ``` cpp #include<bits/stdc++.h> using namespace std; #define N 21 #define int short//懒人专用 inline int read(){int x=0;char c=getchar();while(c<'0' || c>'9')c=getchar();while(c>='0' && c<='9')x=(x<<3)+(x<<1)+(c^'0'),c=getchar();return x;}//快读 short n,ans2[N],cnt,a[N],f[1<<20][N],ans; pair<short,short>pre[1<<20][N],s;//pre记录前驱 bool e[N][N];//邻接矩阵存图 signed main() { n=read(); for(register int i=1;i<=n;i++)a[i]=read(); for(register int i=1;i<n;i++)for(register int j=i+1;j<=n;j++)e[i][j]=read(); for(register int i=0;i<(1<<n)-1;i++) { if(i==0) { for(register int j=1;j<=n;j++)f[1<<j-1][j]=a[j]; } else { for(register int j=1;j<=n;j++) { if(!(i&(1<<j-1)))continue; for(register int k=1;k<=n;k++) { if(!e[j][k] || i&(1<<k-1))continue; if(f[i|(1<<k-1)][k]<f[i][j]+a[k])//状态转移 { f[i|(1<<k-1)][k]=f[i][j]+a[k]; pre[i|(1<<k-1)][k]=make_pair(i,j); } } } } } for(register int i=1;i<(1<<n);i++)//记录答案 { for(register int j=1;j<=n;j++) { if(!(i&(1<<j-1)))continue; if(f[i][j]>ans) { ans=f[i][j]; s=make_pair(i,j); } } } for(pair<short,short>i=s;i.first;i=pre[i.first][i.second])ans2[++cnt]=i.second;//记录路径 for(register int i=cnt;i;i--)printf("%hd ",ans2[i]);//输出 putchar('\n'); printf("%hd",ans); } ```