写在前面
搜索好啊!没有什么比搜索还要好的算法了
记录
本题的记录
$Acwing$
$Luogu$
$Idea$
本题采用搜索,不用状压$DP$
首先,小明只会开凿可以使各个宝藏点联通的最少条路径,所以最后这个图将会是一棵树,而$DFS$图形化后也是一棵树,所以顺理成章的想到$DFS$(雾。
以此为依据,我们可以用深搜一步一步构建树,每个不同形态的树必有一个总代价,枚举树的构成形态即可枚举不同的总代价,各个总代价的最小值就是答案。
如何去一步步构建树呢?
我们可以按层来讨论
每层都对所有点讨论,讨论是否把这个点放在该层
分析题目后我们会发现,每增加一个点;
这棵树的分数是: 前面已经得到的分数+该点连接上一层的点的边的权值 $\times$该层层数,所以分数会随着点的加入而线性增长,且增加的分数不与前面层的点的结构有关
这样,我们就可以用贪心的思想,我们总希望边新加的分数最小,这样总分数才会小,所以对于要讨论的一个点,我们找到他与上层的最小距离,即他与上层点(无论哪个)的最小边(如果有),即是他加入这棵树后,与上层连接的点;
而对于这棵树,我们只用在乎他的得分多少,并不会在乎每层的详细结构。因为影响树的分数的因素只有:在一步一步构建树的过程中,新加入的点与上一层的点相连的边的边权,我们可以直接理解成这个点与上一层的距离
所以,在构建一棵树的时候,我们只需要记录他不断增加的得分,对于其结构,只需要知道每一层有哪些点,顺序如何,而不需要记录具体的点边相连状况
以此得出大致搜索思路
枚举每一层,每一层都枚举每个点是否放入该层
当所有点都构建进了树中,树的可能形态其一就构建完成
枚举每一种可能的树的形态,然后讨论得分最小值
总的来说 搜的是树的每种可能状态 由于每点加分满足不被前态影响 所以我们用枚举每个点的方式一步步构建出树,并在这过程中得出这种可能树的得分 最后所有树的形态都列出过,所有可能的总得分也都求过了 求个最小值OK
$Code$
const int INF=1000000;
int map[15][15];
int n,m;
int lay[15][15];//每层第i个是哪个点
int nlay[15];//每层多少个点
bool used[15];//每个点是否被用过
int ans=INF;
inline void dfs(int ceng,int k,int cnt,int sum){//现在是在第ceng层,在讨论编号是k的点,总共用了cnt个点,现在这棵树价值sum
if(sum>=ans)return ;//最优性剪枝 !!!最重要!!!只要现阶段的得分已经不是最小的了就没有继续的必要了
if(nlay[ceng-1]==0)return ;//上一层没有选入点(上层为空),树不可能继续构建,该可能不合法,直接跳过
if(cnt==n){
ans=sum<ans?sum:ans;//所有点都已经被构建进树中,比对答案
return ;//结束这种可能
}
if(k>n){
dfs(ceng+1,1,cnt,sum);//该层所有点都讨论过一遍,继续下一层
return ;
}
if(used[k]==1){
dfs(ceng,k+1,cnt,sum);//该点已用,直接讨论下一个点
return ;
}
if(used[k]==0){//该点没用过,讨论一下
used[k]=1;
int mini=INF;//找到该点与上层的最小联系
for(int i=1;i<=nlay[ceng-1];i++)//若没有联系(即与上层所有点不连通),则mini是INF,会被最优性剪枝减去
if(map[k][lay[ceng-1][i]]<mini)
mini=map[k][lay[ceng-1][i]];
nlay[ceng]++;//这层又多一个点啦
lay[ceng][nlay[ceng]]=k;//这点是哪个?存在 lay[哪层][第几个] 中
dfs(ceng,k+1,cnt+1,sum+mini*ceng);//选用此点(可能1)
nlay[ceng]--;
used[k]=0;
dfs(ceng,k+1,cnt,sum);//不用此点(可能2)
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)map[i][j]=INF;//数组初始化
for(int i=1;i<=m;i++){
int a,b,c;
cin>>a>>b>>c;
if(c<map[a][b])map[a][b]=map[b][a]=c;//无向图双向赋值
}
for(int i=1;i<=n;i++){//每个点都当一次根
used[i]=1;//点已用
lay[0][1]=i;//根看做第0层
nlay[0]=1;//0层有一个根节点
dfs(1,1,1,0);//从第一层开始搜索
used[i]=0;//以该点为根的数搜索完毕
}
cout<<ans;
return 0;
}
$$ The \quad End $$
$$ \text{任他转眼高楼起又随浮云散,山鸟过青烟此处安见南山。-《京津有味》音频怪物} $$
图片挂了hhhh