题解 P3959 【宝藏】(状压)

2018-11-05 16:58:00


n出的那么小,显然就是让我们来状压的。

f[i]表示选的点状态为i时的最小代价,dis[i]表示到i这个这条路已经选了多少个点了。转移类似于spfa,如果走过来的代价要小的话:$f[u|(1<<(j-1))]=f[u]+dis[i]*val(i\to j)$

然后,实现起来就用大法师就行了。打其实很好打,就看想不想的到了

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
int g[20][20],f[20000],dis[20];
int dfs(int u)
{
    for(int i=1;i<=n;i++)
        if((1<<(i-1))&u)//枚举从那个点继续往下打
        {
            for(int j=1;j<=n;j++)
                if(!((1<<(j-1))&u) && g[i][j]!=-1)//枚举要到的点
                {
                    if(f[u|(1<<(j-1))]>f[u]+dis[i]*g[i][j])
                    {
                        int tmp=dis[j];
                        dis[j]=dis[i]+1;
                        f[u|(1<<(j-1))]=f[u]+dis[i]*g[i][j];
                        dfs(u|(1<<(j-1)));
                        dis[j]=tmp;//注意要还原
                    }
                }
        }
}
int main()
{
    memset(g,-1,sizeof(g));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        if(g[x][y]==-1) g[x][y]=z,g[y][x]=z;
        g[x][y]=min(g[x][y],z);
        g[y][x]=min(g[y][x],z);
    }
    int ans=0x7ffffff;
    for(int i=1;i<=n;i++)//枚举第一个打通的起点
    {
        memset(f,0x7f,sizeof(f));
        memset(dis,0x7f,sizeof(dis));
        dis[i]=1,f[1<<(i-1)]=0;
        dfs(1<<(i-1));
        ans=min(ans,f[(1<<n)-1]);
    }
    printf("%d",ans);
    return 0;
}