题解 P2196 【挖地雷】
whyl
2019-10-27 20:06:58
由于我太智障。。。
并不会爆搜和正常的dp
就写了一个状压DP
方程和最长哈密顿路径的方程相同
放代码
```cpp
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1;
char p=getchar();
while(!isdigit(p)){
if(p=='-') f=-1;
p=getchar();
}
while(isdigit(p)) x=(x<<3)+(x<<1)+(p^48),p=getchar();
return x*f;
}
const int maxn=(1<<20);
int n,f[maxn][20],pre[maxn][20],w[maxn];
int head[25],nxt[505],ver[505],cnt,mx;
inline void add(int x,int y){
nxt[++cnt]=head[x];
head[x]=cnt;
ver[cnt]=y;
}
inline void print(int S,int x){
if(S==0) return;
print((S^(1<<(x-1))),pre[S][x]);
cout<<x<<" ";
}
inline void solve(){
int full=(1<<n)-1;
for(int S=1;S<=full;S++){
for(int x=1;x<=n;x++){
if(!(S&(1<<(x-1)))) continue;
for(int i=head[x];i;i=nxt[i]){
int y=ver[i];
if(!(S&(1<<(y-1)))) continue;
int T=S^(1<<(y-1));
if(f[T][x]+w[y]>f[S][y]){
f[S][y]=f[T][x]+w[y];
pre[S][y]=x;
mx=max(f[S][y],mx);
}
}
}
}
for(int S=1;S<=full;S++){
for(int x=1;x<=n;x++){
if(mx==f[S][x]){
print(S,x);
cout<<endl;
cout<<mx<<endl;
return;
}
}
}
}
int main(){
n=read();
for(int i=1;i<=n;i++) w[i]=read();
for(int i=1;i<n;i++){
for(int j=i+1;j<=n;j++){
int opt=read();
if(opt==1){
add(i,j);
}
}
}
memset(f,128,sizeof(f));
for(int i=1;i<=n;i++){
f[(1<<(i-1))][i]=w[i];
mx=max(mx,w[i]);
pre[(1<<(i-1))][i]=0;
}
solve();
return 0;
}
```