题解：AT_arc078_d [ARC078F] Mole and Abandoned Mine

· · 题解

Sol

刻画一下合法图的状态，不难想到可以视作 1\rightarrow n 的一条简单路径，每个节点外挂一个联通块，各个节点外挂的联通块互不相交。

图状压，f(S,i) 表示已经考虑了 S 中的点，路径最后一点为 i 的最大边权和，转移就枚举连通块即可，块是否连通以及块内边权和可以预处理得出。直接这么做可以做到 O(3^nn^2)，交上去 3.6 秒过了。

事实上对每个 S 预处理其补集子集的最大代价即可做到 O(3^nn+2^nn^2)，由于很简单且已经过了且我懒就没写了。下面的代码是 O(3^nn^2) 的。

Code

const int N=15;

int n,m;
int g[N][N];
int f[1<<N],e[1<<N],lg[1<<N],h[1<<N][N];

inline void Main(){
    cin>>n>>m;
    int sum=0;
    rep(i,1,m){
        int a,b,c;cin>>a>>b>>c;
        --a,--b;
        g[a][b]=g[b][a]=c;
        sum+=c;
    }
    repl(i,0,n)lg[1<<i]=i;
    repl(s,1,1<<n){
        int i=lg[s&-s];
        e[s]=e[s^1<<i];
        repl(j,0,n)if(s>>j&1)e[s]+=g[i][j];
    }
    repl(s,1,1<<n)for(int t=s-1&s;t;t=t-1&s)f[s]|=(e[s]==e[t]+e[s^t]);
    memset(h,-0x3f,sizeof h);
    repl(s,1,1<<n)if(!f[s]&&(s&1)&&(s>>n-1&1^1))h[s][0]=e[s];
    int S=(1<<n)-1;
    repl(s,1,1<<n)repl(i,0,n)if(s>>i&1)
        for(int t=S-s;t;t=t-1&S-s)if(!f[t])repl(j,0,n)if(g[i][j]&&(t>>j&1))chmax(h[s|t][j],h[s][i]+g[i][j]+e[t]);
    put(sum-h[S][n-1]);
}