NOIP2017 Day2 T2 宝藏（状压DP）

　　$O(n*3^n)$好难想...还有好多没见过的操作

　　令$f[i][j]$表示最深深度为i，点的状态为j的最小代价，每次枚举状态$S$后，计算$S$的补集里的每个点与S里的点的最小连边代价，再$O(3^n)$枚举S补集的子集，$g[x]$表示补集里状态为x的点往S集合里的点连边的最小代价，然后转移的时候加上它就好。

　　但是$g[x]$怎么处理呢...处理不好就会变成$O(3^n*n^2)$了，当然也可以预处理，但是有更简单的方法。因为我们枚举补集的时候是按顺序的，当前状态去掉最低位的状态一定是算过了的，于是就可以用减去lowbit的$g[x-lowbit(x)]$加上最低位往S的某个点连边的最小代价来得到。

　　学习到的一些技巧是枚举状态之后每次减去lowbit得到所有的点效率可以提高一些，用于卡常，还有就是上方的$O(n^3)$就能预处理出$g[x]$的方法，都好喵喵啊~

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<cmath>

using namespace std;

const int maxn=, inf=6e6;

int n, m, x, y, z;

int mp[maxn][maxn], f[maxn][<<], g[<<], h[<<], Log[<<], a[maxn], mncost[maxn];

inline void read(int &k)

{

    int f=; k=; char c=getchar();

    while(c<'' || c>'') c=='-' && (f=-), c=getchar();

    while(c<='' && c>='') k=k*+c-'', c=getchar();

    k*=f;

}

inline int min(int a, int b){return a<b?a:b;}

int main()

{

    read(n); read(m); memset(mp, , sizeof(mp));

    for(int i=;i<=m;i++) read(x), read(y), read(z), mp[x][y]=mp[y][x]=min(mp[x][y], z);

    for(int i=;i<n;i++) Log[<<i]=i+;

    memset(f, , sizeof(f));

    for(int i=;i<=n;i++) f[][<<(i-)]=;

    int st=(<<n)-, ans=inf;

    for(int i=;i<=n;i++)

    {

        for(int j=;j<=st;j++)

        {

            int cnt=;

            for(int k=st-j;k;k-=k&-k)

            {

                int x=Log[k&-k]; a[++cnt]=x; mncost[x]=inf;

                for(int l=j;l;l-=l&-l) mncost[x]=min(mncost[x], min(1ll*inf, 1ll*mp[Log[l&-l]][x]*(i-)));

            }

            for(int k=;k<(<<cnt);k++)

            {

                g[k]=g[k-(k&-k)]+mncost[a[Log[k&-k]]];

                h[k]=k?h[k-(k&-k)]|(<<(a[Log[k&-k]]-)):;

                f[i][j|h[k]]=min(f[i][j|h[k]], f[i-][j]+g[k]);

            }

        }

        ans=min(ans, f[i][st]);

    }

    printf("%d\n", ans);

    return ;

}