AT2657 Mole and Abandoned Mine 题解

状压DP

考虑删完边之后的图，一定是从1到n的一条链，链旁边挂上若干个联通块，要求这张图的边权和最大。

f(S, i)表示链的尾部是i，目前加入了S集合里的点，最大的边权和。预处理block表示集合s内部边权之和，g(i, j)表示(i, j)边的边权。

有两种转移, 一种是新处理一个点, 一种是将一个联通块与当前终点相连，每个连通块最多只与保留下来的那条路径上的一个点有边相连

代码长这样

#include<bits/stdc++.h>
using namespace std;

#define go(i,a,b) for(int i=a;i<=b;++i)
#define com(i,a,b) for(int i=a;i>=b;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#define fo(i,a) for(int i=0;i<a;++i)
#define il inline

const int inf=0x3f3f3f3f,N=4e4;

int n,m,block[N],dp[N][20],g[20][20];

il void read(int &x){
    x=0;char c=getchar(),f=1;
    while(!isdigit(c)){ if(c=='-') f=-1; c=getchar(); }
    while(isdigit(c)){ x=x*10+c-'0'; c=getchar(); }
    x*=f;
}
il void gmax(int &x,const int &y){
    x=x>y?x:y;
}

int main(){
    //freopen("input.txt","r",stdin);
    read(n),read(m);
    int x,y,w;
    go(i,1,m){
        read(x),read(y),read(w);
        --x,--y;
        g[x][y]=g[y][x]=w;
    }
    int all=(1<<n)-1;
    go(i,1,all)
        fo(j,n){
            if(i>>j&1){
                block[i]=block[i^1<<j];
                fo(k,n) if(i>>k&1) block[i]+=g[j][k];
                break;
            }
        }
    mem(dp,-1);
    dp[1][0]=0;
    go(i,1,all)
        fo(j,n)
            if(i>>j&1&&dp[i][j]!=-1){
                fo(k,n)
                    if(!(i>>k&1)&&g[j][k])
                        gmax(dp[i|1<<k][k],dp[i][j]+g[j][k]);
                int tmp=(all^i)|1<<j;
                for(int k=tmp;k;k=(k-1)&tmp){
                    if(k>>j&1)
                        gmax(dp[i|k][j],dp[i][j]+block[k]);
                }
            }
    cout<<block[all]-dp[all][n-1];
    return 0;
}

AT2657 Mole and Abandoned Mine 题解

原文：https://www.cnblogs.com/White-star/p/11752622.html