[Luogu3959] [NOIP2017] 宝藏 Treasure [状态压缩+子集+dp搜索+剪枝模拟退火]

[$\mathfrak{L}\mathfrak{i}\mathfrak{n}\mathfrak{k}$] 注意：洛谷题解里面有很大一部分题解是错误的 具体可以用讨论中的hack数据自行验证。

---

点数很特殊。 最开始的想法是类似最小生成树那样的东西，不过这个“最小”定义实在有点模糊。

注意到数据范围。n的范围十分特殊，考虑一下。 按理来说不是搜索就是状态压缩了，而且状压的可能性更大一点。 不过还是先考虑搜索吧。

---

搜索

首先枚举起点，然后逐个跑最小生成树？ 要注意的是，边权不是固定的，和之前的方案有关。所以最小生成树是跑不了了。 不过还是可以骗一点分：尝试枚举全排列，同时每一步还要枚举新的点是哪个点拓展出来的。

#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std; int n,m,dis[15][15]={},dep[15]={}; int pt[15][15]={}; int mn[15]={}; long long ans=0x3f3f3f3f; bool vis[15]={}; int stk[15]={}; inline void dfs(register int step,register long long sum) { if(sum>=ans) return; if(step==n) { ans=min(ans,sum); return;} for(register int i,ti=1;ti<=stk[0];++ti) { i=stk[ti]; for(register int v,j=1;j<=pt[i][0];++j) { v=pt[i][j]; if(vis[v])continue; vis[v]=1, dep[v]=dep[i]+1; stk[++stk[0]]=v; dfs(step+1,sum+1ll*dis[i][v]*dep[v]); vis[v]=0; --stk[0]; } } } int main() { memset(mn,0x3f,sizeof(mn)); memset(dis,0x3f,sizeof(dis)); scanf("%d%d",&n,&m); for(register int i=1;i<=n;++i)dis[i][i]=0; for(register int u,v,w,i=1;i<=m;++i) { scanf("%d%d%d",&u,&v,&w); if(dis[u][v]==0x3f3f3f3f) { pt[u][++pt[u][0]]=v; pt[v][++pt[v][0]]=u; } if(w<dis[u][v]) { dis[u][v]=dis[v][u]=w; mn[u]=min(mn[u],w); mn[v]=min(mn[v],w); } } stk[0]=1; for(register int i=1;i<=n;++i) { vis[i]=1; dep[i]=0; stk[1]=i; dfs(1,0); vis[i]=0;} printf("%d",ans); return 0; }

没有特意剪枝，剪枝AC的代码可以参考洛谷题解。

---

模拟退火

最小生成树跑不了，所以在Prim贪心的基础上随机接受非最短边。 具体见洛谷题解

---

状态压缩

状压的根本在于按（被压缩的）层转移。 初步考虑$\mathfrak{f}(\mathfrak{S})$表示$\mathfrak{S}$里面的点都被选入，此时的最小代价。 转移的影响因素有两个，一个是转移边的权值，一个是转移点的层数 第二个是动态变化的。于是状态变为$\mathfrak{f}(\mathfrak{i},\mathfrak{S})$。 所以枚举$\mathfrak{i}$和$\mathfrak{S}$，然后枚举${\mathfrak{S}}^{\prime }$表示要放在$\mathfrak{i}+1$层的点集。 复杂度是$\Theta (\mathfrak{n}\cdot 4^{\mathfrak{n}})$。实际上里面的剪枝剪掉了很多重复的状态，仔细考虑一下？

实际上因为${\mathfrak{S}}^{\prime }$是$\mathfrak{S}$补集的子集也就是全集的子集的子集， 枚举$\mathfrak{S}$的一层复杂度可以无视掉，复杂度实际上就是枚举全集的子集的子集的复杂度。

考虑一个元素数量为$\mathfrak{n}$的集合，它的元素个数为$\mathfrak{x}$的子集数量为${\mathfrak{C}}_{\mathfrak{n}}^{\mathfrak{x}}$， 且元素个数为$\mathfrak{x}$的集合的所有子集数量为$2^{\mathfrak{x}}$。 综上所述，元素个数为$\mathfrak{n}$的集合的子集的子集数量为$\sum _{\mathfrak{x}=1}^{\mathfrak{n}}{\mathfrak{C}}_{\mathfrak{n}}^{\mathfrak{x}}{2}^{\mathfrak{x}}$。 这个形式应该挺熟悉的，就是二项式定理那个$\sum _{\mathfrak{r}=1}^{\mathfrak{n}}{\mathfrak{C}}_{\mathfrak{n}}^{\mathfrak{r}}{\mathfrak{a}}^{\mathfrak{n}-\mathfrak{r}}{\mathfrak{b}}^{\mathfrak{r}}$取$\mathfrak{a}=2,\mathfrak{b}=1$。 所以数量就是$(2+1{)}^{\mathfrak{n}}=3^n$

综上所述复杂度为$\Theta (\mathfrak{n}\cdot 3^{\mathfrak{n}})$。

#include<cstdio> #include<iostream> #include<algorithm> #include<cmath> #include<ctime> #include<cstring> using namespace std; int n,m,Ans=0x3f3f3f3f; int F[15][5000]={}; int dis[15][15]={}; int cost[15][5000]={}; int to[5000][5000]={}; void out(int x) { while(x) { if(x&1)putchar('1'); else putchar('0'); x>>=1; }cout<<" "; } int main() { memset(dis,0x3f,sizeof(dis)); memset(cost,0x3f,sizeof(cost)); scanf("%d%d",&n,&m); for(register int u,v,w,i=1;i<=m;++i) { scanf("%d%d%d",&u,&v,&w); if(w<dis[u][v])dis[u][v]=dis[v][u]=w; } for(int i=1;i<=n;++i) { for(int j=0;j<(1<<n);++j) { if(j&(1<<i-1))continue; for(int k=1;k<=n;++k) { if(j&(1<<k-1))cost[i][j]=min(cost[i][j],dis[i][k]); } } } for(int i=0;i<(1<<n);++i) { for(int j=0;j<(1<<n);++j) { if(i&j)continue; for(int k=1;k<=n;++k) { if(i&(1<<k-1))to[i][j]=min(to[i][j]+cost[k][j],0x3f3f3f3f); } } } memset(F,0x3f,sizeof(F)); for(int i=1;i<=n;++i)F[1][1<<i-1]=0; for(register int f=1;f<n;++f) { for(register int j=0;j<(1<<n);++j) { if(F[f][j]==0x3f3f3f3f)continue; for(register int k=0;k<(1<<n);++k) { if(j&k)continue; if(to[k][j]==0x3f3f3f3f)continue; F[f+1][j|k]=min(F[f+1][j|k],F[f][j]+f*to[k][j]); } } } for(register int i=1;i<=n;++i)Ans=min(Ans,F[i][(1<<n)-1]); if(Ans==0x3f3f3f3f)printf("-1"); else printf("%d",Ans); return 0; }

其他做法： ${\mathfrak{n}}^3{3}^{\mathfrak{n}}$、$2^{\mathfrak{n}}\mathfrak{n}\mathfrak{m}$、$3^{\mathfrak{n}}\mathfrak{n}$