AT2657 Mole and Abandoned Mine

传送门

好神的状压dp啊

首先考虑一个性质，删掉之后的图一定是个联通图

并且每个点最多只与保留下来的那条路径上的一个点有边相连

然后设状态：\(f[s][t]\)代表当前联通块的点的状态为\(s\)和路径结尾的点\(t\)

然后考虑转移，要么拓展一个点作为路径，要么挂一个联通块到当前路径结尾的点上

代码：

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<vector>

using namespace std;

void read(int &x){

    char ch;bool ok;

    for(ok=0,ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')ok=1;

    for(x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar());if(ok)x=-x;

}

#define rg register

const int maxn=1<<16;

int n,m,v[20][20];

long long ans,in[maxn],f[maxn][20];

vector<int>d[20];

int main(){

    read(n),read(m);

    for(rg int i=1,x,y,z;i<=m;i++){

        read(x),read(y),read(z),v[x][y]=v[y][x]=z;

        ans+=z;

        d[x].push_back(y),d[y].push_back(x);

    }

    int tot=1<<n;

    for(rg int i=0;i<tot;i++){

        for(rg int j=1;j<=n;j++)

            if(!(i&(1<<(j-1)))&&!in[i|(1<<(j-1))]){

                int w=d[j].size(),sum=in[i];

                for(rg int k=0;k<w;k++)

                    if(i&(1<<(d[j][k]-1)))sum+=v[j][d[j][k]];

                in[i|(1<<(j-1))]=sum;

        }

    }

    memset(f,-1,sizeof f);

    f[1][1]=0;

    for(rg int i=0;i<tot;i++)

        for(rg int k=1;k<=n;k++){

            if(f[i][k]==-1)continue;

            if(i&(1<<(k-1))){

                for(rg int j=1;j<=n;j++)

                    if(!(i&(1<<(j-1)))&&v[k][j])

                        f[i|(1<<(j-1))][j]=max(f[i][k]+v[k][j],f[i|(1<<(j-1))][j]);

                int now=((tot-1)^i)|(1<<(k-1));

                for(rg int j=now;j;j=(j-1)&now)

                    if(j&(1<<(k-1)))f[i|j][k]=max(f[i][k]+in[j],f[i|j][k]);

            }

        }

    printf("%lld\n",ans-f[tot-1][n]);

}

巴特西

AT2657 Mole and Abandoned Mine

传送门

最新文章

热门文章