题解 P3959 【宝藏】

Dalao的题解多数是什么模拟退火、DFS剪枝、O(3^nn^2)的状压DP之类。蒟蒻尝试着把状压改进了一下使复杂度降到O(3^nn)。

考虑到每条边的贡献跟它所在的层有关，所以如果我们能够将一层的边一起加进去，计算就会方便许多。于是想办法把这个转移过程状压一下。

设f_{i,j}为当前已选点集为i，下一层加入的点集为j时，新加入的所有点与原有点之间最小的边权之和。计算的具体实现，我们O(2^n)枚举i，再枚举i的补集的子集j，把j的lowbit挑出来，f_{i,j}等于f_{i,j-lowbit(j)}加上\log lowbit(j)与i之间的最小边权。

这一部分的复杂度是O(3^nn)（n元素集合的所有子集的子集大小之和是3^n可以证）

接着就可以开始转移了。设g_{l,i}为总层数为l，已选点集为i的最小答案。参考f的定义我们可以很快的写出转移方程（式中的i-j为集合意义，代码中写i^j）

也是一遍枚举子集，复杂度还是O(3^nn)。最后\max\limits_{l=0}^ng_{l,2^n-1}就是答案。

当然，为了实际复杂度和理论一致，我们枚举子集不能这样暴枚

    for(i=0;i<=S;++i)
        if(i&S)//do something

而应该这样

    for(i=S;i;i=(i-1)&S)
        //do something

跟队爷Anson学的，具体原理蒟蒻也策不清楚啊qwq

代码十分简洁，注意INF的设置

#include<bits/stdc++.h>
#define R register int
using namespace std;
const int N=13,M=4096,INF=0x01010101;
int a[N][N],f[M][M],g[N][M],ne[M],lg[M];
inline void chkmn(R&x,R y){
    if(x>y)x=y;
}
int main(){
    memset(a,1,sizeof(a));
    memset(g,63,sizeof(g));//貌似需要区别对待
    R n,m,S,s,i,j,l,x,y,v;
    cin>>n>>m;
    S=(1<<n)-1;
    for(i=0;i<n;++i)
        lg[1<<i]=i;//log预处理
    while(m--){
        cin>>x>>y>>v;
        if(a[--x][--y]>v)//邻接矩阵存边
            a[x][y]=a[y][x]=v;
    }
    for(i=1;i<=S;++i){
        v=0;
        for(j=s=S^i;j;j=(j-1)&s)
            ne[j]=v,v=j;//为了更新顺序需要反向枚举
        for(j=v;j;j=ne[j]){
            x=lg[j&-j];v=INF;
            for(y=0;y<n;++y)//找到可以连接的最小边权
                if(1<<y&i)chkmn(v,a[x][y]);
            f[i][j]=f[i][j^(j&-j)]+v;
        }
    }
    for(i=1;i<=S;i<<=1)
        g[0][i]=0;//状态预处理
    for(l=1;l<n;++l)
        for(i=1;i<=S;++i)
            for(j=i;j;j=(j-1)&i)
                chkmn(g[l][i],g[l-1][i^j]+f[i^j][j]*l);
    v=0x7fffffff;
    for(l=0;l<=n;++l)
        chkmn(v,g[l][S]);
    cout<<v<<endl;
    return 0;
}