本文主要是介绍NOIP 2017 D2T2 洛谷P3959 宝藏，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
参与考古挖掘的小明得到了一份藏宝图，藏宝图上标出了 n 个深埋在地下的宝藏屋， 也给出了这 n 个宝藏屋之间可供开发的 m 条道路和它们的长度。
小明决心亲自前往挖掘所有宝藏屋中的宝藏。但是，每个宝藏屋距离地面都很远， 也就是说，从地面打通一条到某个宝藏屋的道路是很困难的，而开发宝藏屋之间的道路 则相对容易很多。
小明的决心感动了考古挖掘的赞助商，赞助商决定免费赞助他打通一条从地面到某 个宝藏屋的通道，通往哪个宝藏屋则由小明来决定。
在此基础上，小明还需要考虑如何开凿宝藏屋之间的道路。已经开凿出的道路可以 任意通行不消耗代价。每开凿出一条新道路，小明就会与考古队一起挖掘出由该条道路 所能到达的宝藏屋的宝藏。另外，小明不想开发无用道路，即两个已经被挖掘过的宝藏 屋之间的道路无需再开发。
新开发一条道路的代价是：
L×K
L代表这条道路的长度，K代表从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的 宝藏屋的数量（包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋） 。
请你编写程序为小明选定由赞助商打通的宝藏屋和之后开凿的道路，使得工程总代 价最小，并输出这个最小值。
输入输出格式
输入格式：
第一行两个用空格分离的正整数 n 和 m，代表宝藏屋的个数和道路数。
接下来 m 行，每行三个用空格分离的正整数，分别是由一条道路连接的两个宝藏 屋的编号（编号为 1~n），和这条道路的长度 v。
输出格式：
输出共一行，一个正整数，表示最小的总代价。
输入输出样例
输入样例#1：
4 5 1 2 1 1 3 3 1 4 1 2 3 4 3 4 1
输出样例#1：
4
输入样例#2：
4 5 1 2 1 1 3 3 1 4 1 2 3 4 3 4 2
输出样例#2：
5
说明
【样例解释1】
小明选定让赞助商打通了 1 号宝藏屋。小明开发了道路 1→2，挖掘了 2 号宝 藏。开发了道路 1→4，挖掘了 4 号宝藏。还开发了道路 4→3，挖掘了 3 号宝 藏。工程总代价为：1×1+1×1+1×2=4
【样例解释2】
小明选定让赞助商打通了 1 号宝藏屋。小明开发了道路 1→2，挖掘了 2 号宝 藏。开发了道路 1→3，挖掘了 3 号宝藏。还开发了道路 1→4，挖掘了 4 号宝 藏。工程总代价为：1×1+3×1+1×1=5
【数据规模与约定】
对于 20%的数据： 保证输入是一棵树，1≤n≤8，v≤5000 且所有的 v 都相等。
对于 40%的数据： 1≤n≤8，0≤m≤1000，v≤5000 且所有的 v 都相等。
对于 70%的数据： 1≤n≤8，0≤m≤1000，v≤5000
对于 100%的数据： 1≤n≤12，0≤m≤1000，v≤500000
题目链接
数据范围显然状压+搜索。
可能会说的比较晦涩难懂，但是我的代码里面包含了大量注释，可能比我说的更好理解一些。
大概就是首先枚举起点，然后直接搜索，每次从已经挖好的点中选取一个点出来枚举出边，如果这种情况没找过或者找到了更优的情况就继续往下搜索。
说详细点。
我们记dp[i]为状态i下的最小花费，显然i对应一个二进制状态，1表示这个点已经选好了,0表示还没选。设Depth[x]表示点x在当前情况下的深度。每次搜索在状态i对应的二进制中找到为1的点，枚举其出边。设v为出边的终点,w为边权。如果v还没有记录深度并且
这就意味着点v还没有被选过且当前选v后是更优的，那我们就把点v加进状态中继续搜索。搜索完后再把ans和(每一位全为1,表示所有点都已经选好了)取个min就好了。
果然说的神乎其神，还是看代码比较好吧！
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
inline int read()
{int sum=0,t=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') t=-1;ch=getchar();}while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}return sum*t;
}int n,m,tot=0,ans=192608170;
struct edge//邻接表存边
{int next,node,w;
}h[2005];
struct bian//预处理去重边，先存在这
{int s,t,w;
}now[2005];
int Head[20],Depth[20],dp[32768];//Head用于邻接表,Depth记录深度,dp[i]记录状态i的最小花费
inline void add(int u,int v,int w)//邻接表加边
{h[++tot].next=Head[u];h[tot].node=v;h[tot].w=w;Head[u]=tot;
}
bool cmp(const bian &a,const bian &b)//我们把重边排序放在一起，边权小的放在前面,方便主函数中处理。
{if(a.s==b.s){if(a.t==b.t)//这里关键是s和t相等，下面按照s和t排序可以随便return a.w<b.w;//小的在前return a.t<b.t;}return a.s<b.s;
}
void dfs(int x)
{for(register int i=1;i<=n;++i)//枚举状态x中的每个点。if((1<<(i-1))&x)//找到一个为1的也就是已经选好的点。for(register int j=Head[i];j;j=h[j].next)//枚举这个点的所有出边{int v=h[j].node,w=h[j].w;//记录下终点和边权if(Depth[v]==0&&dp[1<<(v-1)|x]>dp[x]+w*Depth[i]){//↑ v没有被选过 ↑状态dp[1<<(v-1)|x]原本的值 > 状态x+当前边的花费*深度(L*K)Depth[v]=Depth[i]+1;//更新深度dp[1<<(v-1)|x]=dp[x]+w*Depth[i];//更新最小花费dfs(1<<(v-1)|x);//由下一个状态继续搜索Depth[v]=0;//回溯}}
}
int main()
{n=read();m=read();for(register int i=1;i<=m;++i)//由于有许多的重边，所以我们先不进行加边，而是先去重{now[i].s=read();now[i].t=read();now[i].w=read();//暂时记录下边if(now[i].s>now[i].t)swap(now[i].s,now[i].t);}sort(now+1,now+m+1,cmp);//把s和t相同的边放一起且边权小的在前面for(register int i=1;i<=m;++i)//枚举每条边{if(now[i].s==now[i-1].s&&now[i].t==now[i-1].t)//如果起点和终点和上一条边相同,说明这是一条重边continue;//而我们把小的放在前面了，这条边权值肯定更大，所以直接跳过。add(now[i].s,now[i].t,now[i].w);add(now[i].t,now[i].s,now[i].w);//终于可以加边了}for(register int i=1;i<=n;++i)//枚举起点{memset(Depth,0,sizeof(Depth));memset(dp,63,sizeof(dp));//数组记得清零Depth[i]=1;//起点深度为1dp[1<<(i-1)]=0;起点不需要花费dfs(1<<(i-1));//搜索ans=min(ans,dp[(1<<n)-1]);//更新答案。(1<<n)-1的结果是n个数位上每一位都为1}cout<<ans<<endl;return 0;
}
这篇关于NOIP 2017 D2T2 洛谷P3959 宝藏的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
