【状压DP】【NOIP2017】宝藏_综合

分析：

很简单的状压DP水题。。。一年前我居然不会。。。太菜了。。。

$DP[i][j]$ 表示前i层，被选中的状态为 $j$ 的最小代价。
每次枚举一个集合 $k$ ，把k中每个点向 $j$ 中最短的边取和。再乘上 $(i+1)$

这里并不需要区分哪些是上一层的，因为优越性已经可以保证方案的正确性了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define SF scanf
#define PF printf
#define MAXN 20
#define MAXM 4100
using namespace std;
typedef long long ll;
ll dist[MAXN][MAXN];
ll len[MAXM][MAXM];
int bits[MAXM];
ll dp[MAXN][MAXM];
ll min1(ll x,ll y){if(x==-1)return y;if(y==-1)return x;return min(x,y);    
}
int main(){int n,m,u,v,val;memset(dist,-1,sizeof dist);SF("%d%d",&n,&m);for(int i=1;i<=m;i++){SF("%d%d%d",&u,&v,&val);u--;v--;    dist[u][v]=min1(dist[u][v],val);dist[v][u]=dist[u][v];}for(int i=0,j=1;i<n;i++,j<<=1)bits[j]=i;for(int i=1;i<(1<<n);i++){int pre=((1<<n)-1)^i;for(int j=pre;j;j=(j-1)&pre){int x=bits[i&(-i)];ll mindist=-1;for(int s=j;s;s^=(s&(-s))){int y=bits[s&(-s)];mindist=min1(mindist,dist[x][y]);}if(mindist!=-1&&len[i^(1<<x)][j]!=-1)len[i][j]=len[i^(1<<x)][j]+mindist;elselen[i][j]=-1;}}memset(dp,-1,sizeof dp);for(int i=0;i<n;i++)dp[0][1<<i]=0;ll ans=-1;for(int i=0;i<n;i++)for(int j=0;j<(1<<n);j++){if(dp[i][j]==-1||(ans!=-1&&dp[i][j]>ans))continue;int x=((1<<n)-1)^j;for(int k=x;k!=0;k=(k-1)&x)if(len[k][j]!=-1)dp[i+1][k|j]=min1(dp[i+1][k|j],dp[i][j]+(i+1)*len[k][j]);if(j==(1<<n)-1)ans=min1(ans,dp[i][j]);}PF("%lld",ans);
}