【题解】洛谷P3959[NOIP2017]宝藏 状压DP
学习了大佬题解，大概看明白了思路。
#include<cstdio>
#include<climits>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
int n,m,g[15][15],d[15][1<<13];
ll f[15][1<<13],ans=LONG_LONG_MAX;
//f[i][s]表示第i层状态为s时的最小代价
int main()
{
//freopen("in.txt","r",stdin);
scanf("%d%d",&n,&m);int S=1<<n;
int u,v,w;
memset(g,0x3f,sizeof(g));
for(int i=1;i<=m;i++)
scanf("%d%d%d",&u,&v,&w),g[u][v]=g[v][u]=min(g[u][v],w);
for(int i=1;i<=n;i++)
for(int s=1;s<S;s++)//找到s状态下i连出去的最小边
{
d[i][s]=INF;
for(int k=1;k<=n;k++)
if((1<<(k-1))&s)d[i][s]=min(d[i][s],g[i][k]);
}
for(int s1=1;s1<S;s1++)
{
if(s1&(s1-1))
for(int i=0;i<=n;i++)
f[i][s1]=INF;
for(int s2=s1&(s1-1);s2;s2=s1&(s2-1))//枚举子集
{
ll dis=0;//每一次的道路权值和
int s=s1^s2;
for(int k=1;k<=n;k++)
if((1<<(k-1))&s2)
dis+=d[k][s];
for(int k=1;k<=n;k++)
f[k][s1]=min(f[k][s1],f[k-1][s]+dis*k);
}
}
for(int i=1;i<=n;i++)
ans=min(ans,f[i][S-1]);
printf("%lld\n",ans);
return 0;
}
总结
复习一波状压DP，包括子集的枚举等等操作。