题解 P2196 【挖地雷】

2019-10-27 20:06:58


由于我太智障。。。

并不会爆搜和正常的dp

就写了一个状压DP

方程和最长哈密顿路径的方程相同

放代码

#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;
}