解题报告

吃我一记万年神坑。去年考场上做这题的时候一直在想二进制状压，现在回头看看那时候的自己真是蠢爆了。

很明显可以三进制状压 $f_{i,s}$ 表示深度为 $i$ 时，每个点的状态 $0/1/2$ 表示没选/上一层/这一层，转移很显然。

但是这样复杂度上天了，三进制状压让我们意识到一件事情：子集枚举。每次对于一个二进制状态，我们枚举他的子集表示之前选的状态，那么多出来的就是这一层的点。

不过仔细想想就会发现很奇怪，如何保证这一层的点连向上一层的点而不是之前层的点？其实最小值已经保证了这个性质，如果某个点没有连向上一层，那么说明他不是这层的点，但统计答案的时候一视同仁导致该点多统计了，这不会出现在最优解中。

直接做是 $O(3^nn^3)$ 的，预处理一下就可以做到 $O(3^nn)$ 。

示例程序

注意刷最优解时候的边界……否则可能会被 $n=1$ 卡……

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=12,maxs=1<<maxn;

int n,m,INF,dis[maxn+5][maxn+5],f[maxn+5][maxs],MIN[maxn+5][maxs],g[maxs][maxs];

int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&m);memset(dis,63,sizeof(dis));INF=dis[0][0];
    for (int i=1,x,y,z;i<=m;i++) scanf("%d%d%d",&x,&y,&z),x--,y--,dis[x][y]=dis[y][x]=min(dis[x][y],z);
    memset(f,63,sizeof(f));for (int i=0;i<n;i++) f[0][1<<i]=0;memset(MIN,63,sizeof(MIN));
    for (int s=1;s<(1<<n);s++)
        for (int i=0;i<n;i++)
            for (int j=0;j<n;j++)
                if (s>>j&1) MIN[i][s]=min(MIN[i][s],dis[i][j]);
    for (int S=1;S<(1<<n);S++)
        for (int s=S-1&S;s;s=s-1&S)
            for (int j=0;j<n;j++)
                if ((S>>j&1)&&!(s>>j&1))
                    if (MIN[j][s]<INF) g[S][s]+=MIN[j][s]; else {g[S][s]=INF;break;}
    for (int i=1;i<=n;i++)
        for (int S=1;S<(1<<n);S++)
            for (int s=S-1&S;s;s=s-1&S)
                if (f[i-1][s]<INF&&g[S][s]<INF) f[i][S]=min(f[i][S],f[i-1][s]+g[S][s]*i);
    int ans=INF;for (int i=0;i<=n;i++) ans=min(ans,f[i][(1<<n)-1]);printf("%d\n",ans);return 0;
}