这道题考试的时候就骗了部分分。其实一眼看过去，n范围12，就知道是状压，但是不知道怎么状压，想了5分钟想不出来就枪毙了状压，与AC再见了。
现在写的是状压搜索，其实算是哈希搜索，感觉状压DP理解不了啊。思路来自于Gt，几乎照搬地写了自己的代码。
思路很简单，搜索。搜索里加了个启发，有点，不，是很像最优性剪枝。
dfs里，hsh是每个点的深度哈希起来（初始化要对于每一个点定一个专门的哈希值，用这个值来哈希自己的深度），k是已经连上了多少个点，val是代价。
估价函数里，对于每一个没有加入答案集合的点，找到他连上任意一个集合（可以是答案集合，也可以是以任意一个同样未连上答案集合的点为根的集合，这样的话当前点的深度就为2了）的最小代价。所有代价加起来后就是把剩下所有点加入答案集合的最低要求（不一定是这个值，但一定大于等于这个值），用这个优化dfs。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=,Mod=,inf=0x3f3f3f3f,base=;
int n,m,ans,hash[MAXN],f[Mod],G[MAXN][MAXN],d[MAXN];
inline void read(int &x)
{
int data=,w=;
char ch=;
while(ch!='-'&&(ch<''||ch>''))ch=getchar();
if(ch=='-')w=-,ch=getchar();
while(ch>=''&&ch<='')data=(data<<)+(data<<)+(ch^''),ch=getchar();
x=data*w;
}
inline void init()
{
for(register int i=;i<=n;++i)
for(register int j=;j<=n;++j)G[i][j]=inf;
hash[]=;
for(register int i=;i<=n;++i)hash[i]=(ll)hash[i-]*base%Mod;
for(register int i=;i<Mod;++i)f[i]=2e9;
ans=2e9;
}
inline int fr()
{
int res=;
for(register int i=;i<=n;++i)
if(!d[i])
{
int tmp=inf;
for(register int j=;j<=n;++j)
if(G[i][j]!=inf)
{
if(d[j])tmp=min(tmp,d[j]*G[i][j]);
else tmp=min(tmp,*G[i][j]);
}
res+=tmp;
}
return res;
}
inline void dfs(int k,int val,int hsh)
{
if(val+fr()>=ans||val>=f[hsh])return ;
f[hsh]=val;
if(k==n)
{
ans=min(ans,val);
return ;
}
for(register int i=;i<=n;++i)
if(!d[i])
for(register int j=;j<=n;++j)
if(d[j]&&G[i][j]!=inf)
{
d[i]=d[j]+;
dfs(k+,val+d[j]*G[i][j],(hsh+d[i]*hash[i])%Mod);
d[i]=;
}
}
int main()
{
freopen("treasure.in","r",stdin);
freopen("treasure.out","w",stdout);
read(n);read(m);
init();
for(register int i=;i<=m;++i)
{
int u,v,k;
read(u);read(v);read(k);
if(u==v)continue;
G[u][v]=min(G[u][v],k);
G[v][u]=min(G[v][u],k);
}
for(register int i=;i<=n;++i)
{
d[i]=;
dfs(,,hash[i]);
d[i]=;
}
printf("%d\n",ans);
return ;
}
NOIP2017 宝藏