P1029 · OFFICIAL SOLUTION

P1029 沧溟探秘藏官方题解

Gioush OJ · P1029 沧溟探秘藏

沧溟探秘藏

【题意简述】

给定 $n$ 个点、 $m$ 条边的带权无向图。可以任选起点，之后每次从已探索点扩展一个未探索点。若从深度为 $k$ 的点经长度为 $w$ 的边扩展，则代价为 $w(k+1)$ 。求探索所有点的最小总代价。

【Hint】

$n$ 很小，可以用集合状态表示已经探索的点。由于代价与层数有关，转移时还需要枚举当前扩展发生在哪一层。

【提示】

设 $Dp_{i,S}$ 表示已经探索集合为 $S$ ，当前准备扩展到第 $i$ 层时的最小代价。

【解法】

先用 $Val_{u,v}$ 记录两点之间最短的直接边权。令 $\operatorname{Cost}_{S,T}$ 表示从已探索集合 $S$ 向新增集合 $T$ 扩展一层时的最小边权和，其中每个 $v\in T$ 都选择一条来自 $S$ 的最小边。

设 $Dp_{k,S}$ 表示完成若干层扩展后，已探索集合为 $S$ ，当前最大层数为 $k$ 的最小代价。转移时枚举下一层新增集合 $T$ ：

Dp_{k+1,S\cup T}\leftarrow \min(Dp_{k+1,S\cup T},Dp_{k,S}+(k+1)\operatorname{Cost}_{S,T}).

起点任意，因此所有单点集合初值为 $0$ 。答案为全集状态的最小值。

【转移含义】

固定一棵探索树后，同一深度的结点可以任意交换探索顺序，费用只取决于它们从此前已探索集合连出的最小边。因此用新增集合 $T$ 统一表示下一层， $\operatorname{Cost}_{S,T}$ 取每个 $v\in T$ 到 $S$ 的最小直接边权之和。

枚举 $T\subseteq\overline S$ 后， $S\cup T$ 正是完成一层扩展后的集合；乘上 $k+1$ 正是这层边的深度系数。每一棵合法探索树按层划分都会产生一条转移序列，反过来每条转移序列也能取最小边连接为一棵合法探索树。

【复杂度】

状态数量为 $\mathcal{O}(n2^n)$ ，枚举子集后复杂度约为 $\mathcal{O}(3^n n)$ ，适合 $n\le12$ 的范围。

【参考代码】

1/*2Author:Ehundategh3Date:2026/7/214Name:treasure.cpp5You steal,I kill.6*/7#include <vector>8#include <cstdio>9#include <cstring>10#include <algorithm>11using namespace std;12int n,m;13int Val[13][13],In1,In2,In3,Pow[13]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096},B[4097];14long long Dp[13][4097],Cost[13][4097],Ans=0x3f3f3f3f3f3f3f3f;15int Lowbit(int x){return x&-x;}16vector <int> Valid[4097];17vector <long long> Pri[4097];18int main(){19    freopen("treasure.in","r",stdin);20    freopen("treasure.out","w",stdout);21    memset(Val,0x3f,sizeof(Val));22    memset(Cost,0x3f,sizeof(Cost));23    memset(Dp,0x3f,sizeof(Dp));24    scanf("%d%d",&n,&m);25    int Temp=1;26    for(int i=1;i<=n;i++){27        B[Temp]=i;28        Temp<<=1;29    }30    for(int i=1;i<=m;i++){31        scanf("%d%d%d",&In1,&In2,&In3);32        Val[In1][In2]=min(Val[In1][In2],In3);33        Val[In2][In1]=min(Val[In2][In1],In3);34    }35    for(int i=0;i<(1<<n);i++){36        for(int j=1;j<=n;j++){37            if((i&(1<<(j-1)))==0) continue;38            for(int k=1;k<=n;k++){39                Cost[k][i]=min(Cost[k][i],1ll*Val[k][j]);40            }41        }42    }43    for(int i=0;i<(1<<n);i++){44        for(int j=(i-1)&i;;j=(j-1)&i){45            int Diff=i-j; bool Tag=1;46            long long Sum=0;47            while(Diff){48                if(Cost[B[Lowbit(Diff)]][j]>1e6){Tag=0; break;}49                Sum+=Cost[B[Lowbit(Diff)]][j];50                Diff-=Lowbit(Diff);51            }52            if(Tag){Valid[i].push_back(j); Pri[i].push_back(Sum);}53            if(j==0) break;54        }55    }56    for (int i=1;i<=n;i++) {57        Dp[1][1<<(i-1)]=0;58    }59    for(int i=1;i<=n;i++){60        for(int j=0;j<=(1<<n)-1;j++){61            for(int k=0;k<Valid[j].size();k++){62                Dp[i][j]=min(Dp[i][j],Dp[i-1][Valid[j][k]]+(i-1)*Pri[j][k]);63            }64        }65        Ans=min(Ans,Dp[i][(1<<n)-1]);66    }67    printf("%lld\n",Ans);68    return 0;69}