题解 P3959 【宝藏】
本题大致有以下几种思路：
1.超纲的模拟退火
2.错误但可以A题的状压DP
3.正确但跑得太慢的状压DP
但是，这些真的正确或者适合吗？
想当初在NOIP考场上打爆搜结果编译不过的尴尬；
不过感谢上苍我还有5分。
但现在，
我们从起点开始走起；
20分做法：
容易想到利用树这一条件
用dfs/bfs求出距离即可
40分做法：
类比与20分做法
用Floyd求出最短路即可（实际上没必要使用SPFA）
我们容易发现这题的n非常非常小
大多数的人的第一印象恐怕就是复杂度常常是(2 ^ n)的状压吧
但是啊，NOIP还有一种神奇的算法，虽然使用它算不上高大大气上档次，复杂度高到无法接受，但是，它毕竟是你曾近学过的算法。
它是谁？复杂度O(n!/玄学)的dfs！！！
70分做法：
我们发现 8!非常的小，带上一大串常数都没问题
因此我们考虑深搜
如何爆搜？
第一反应是枚举全排列然后去更新答案。
但是有问题啊，知道点开拓的顺序并没有什么用，我们还要知道它是由哪个点开拓而来的。
因此我们再枚举去开拓的点：
代码如下
#include <cstdio>
using namespace std;
int a[55], l[55];
int cost[55][55];
int ans = 2147483645, tmp, n, m;
#define getchar() (S==T&&(T=(S=BB)+fread(BB,1,1<<15,stdin),S==T)?EOF:*S++)
char BB[1 << 16], *S = BB, *T = BB;
inline int read () {
int X = 0; char ch = 0;
while(ch < 0 || ch > 9) ch = getchar();
while(ch >= 0 && ch <= 9) X = X * 10 + ch - '0', ch = getchar();
return X;
}
inline int min(int a, int b) {
int c = (a - b) >> 31;
return a ^ c | b ^ ~c;
}
inline void dfs(int e, int num) {
if(num == n) {
ans = min(tmp, ans);
return;
}
if(tmp >= ans) return;
for(int i = 1; i <= n; i ++) {//确定下一步扩展谁
if(l[i]) continue;
for(int j = 1; j <= n; j ++) {//由谁扩展
if(cost[j][i] == 2147483645 || !l[j] || i == j) continue;
tmp += l[j] * cost[j][i]; l[i] = l[j] + 1;
dfs(i, num + 1);
tmp -= l[j] * cost[j][i]; l[i] = 0;
}
}
}
int main() {
int u, v;
n = read(); m = read();
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
cost[i][j] = 2147483645;
for(int i = 1; i <= m; i ++)
u = read(), v = read(),
cost[u][v] = cost[v][u] = min(cost[u][v], read());
for(int i = 1; i <= n; i ++) {
l[i] = 1; dfs(i, 1); l[i] = 0;
}
printf("%lld\n", ...);
return 0;
}（请不要尝试着复制本代码）
为什么这个爆搜正确呢？
因为题目中一句及其重要的话：
另外，小明不想开发无用道路，即两个已经被挖掘过的宝藏 屋之间的道路无需再开发。
因此，我们其实可以很轻易地拿到70分。
大家在考场上都拿了几分呢？
100分不超纲极快解法:
既然都写了爆搜，我们想想有没有更快的速度？
有，我们还有剪枝呢！！
dfs + 剪枝可以跑多快？ 玄学啊。
什么？ 你想知道玄学有多快？
说了不要吃惊。 0ms。
那让我们结合详细的注释来看看如何剪枝。
#include <cstdio>
//基础的头文件
#include <algorithm>
//给sort开的头文件
#define INF 1917483645
using namespace std;
int vis[20], lev[20], d[20];
//vis : 已经访问过的点
//lev : 点距离初始点的距离
//d : 通过此点可以达到的点数
int c[20][20], tar[20][20];
//c : 费用
//tar ：存下每个点能到的点
/*为什么要特意存下每个点到的点？
答案其实并不困难，加快访问速度*/
int ans = INF, tmp, tot, cnt, n, m, p;
//ans : 最终的答案
//tmp : 最优解剪枝用
//tot : dfs储存中间答案的用具
//cnt ：现在已经访问过的点数
//n : 点数
//m : 边数
//p : sort用品
inline bool cmp(int a, int b) {
return c[p][a] < c[p][b];
//按照费用给每个点能到的点排序
}
inline void dfs(int num, int node) {
for(int i = num; i <= cnt; i ++) {
//由第几个被访问的点来扩展
if(tot + tmp * lev[vis[i]] >= ans) return;
//最优性剪枝，如果当前解加上理论最小的费用都比中途的答案高
//那么这次搜索一定不是最优解
for(int j = node; j <= d[vis[i]]; j ++)
//下一步扩展谁
if(!lev[tar[vis[i]][j]]) { //用lev同时充当标记，有lev代表已访问
cnt ++; //多添加一个点
vis[cnt] = tar[vis[i]][j]; //记录这个点
tmp -= c[vis[cnt]][tar[vis[cnt]][1]]; //理论最小的更新
tot += c[vis[i]][vis[cnt]] * lev[vis[i]]; //加上当前的影响
lev[vis[cnt]] = lev[vis[i]] + 1; //因为从vis[i]拓展，故lev一定为其 + 1
dfs(i, j + 1); //继续从i枚举, 注意到tar[i][1 ~ j]已全部访问，下一次从j + 1尝试访问
tot -= c[vis[i]][vis[cnt]] * lev[vis[i]]; //回溯
lev[vis[cnt]] = 0; //回溯
tmp += c[vis[cnt]][tar[vis[cnt]][1]]; //回溯
cnt --; //回溯
}
node = 1; //剪枝别剪错了，i枚举玩下次还要从1枚举
}
if(cnt == n) { //已经访问了n个点，更新答案
if(tot < ans) ans = tot;
return;
}
}
int main() {
int u, v, w;
scanf("%d%d", &n, &m); //读入n, m
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
c[i][j] = INF; //初始赋无限大，方便后面的操作
for(int i = 1; i <= m; i ++) {
scanf("%d%d%d", &u, &v, &w); //这个w先暂时存起来
//因为发现m = 1000 远> n * n，所以要剪掉一些边
if(c[u][v] < w) continue; //w不能更新c[u][v]
if(c[u][v] == INF) //第一次更新c[u][v]，统计u,v的出度
tar[u][++ d[u]] = v, tar[v][++ d[v]] = u;
c[u][v] = c[v][u] = w;
}
for(int i = 1; i <= n; i ++) {
p = i; //sort排序cmp
sort(tar[i] + 1, tar[i] + 1 + d[i], cmp);
tmp += c[i][tar[i][1]]; //因为每个点总要扩展一条边，
//因此我们把最小的边找出来,作为最优性剪枝
//不仅如此，因为边越小作为最终解的可能性越大
//实际上在一定程度上优化了程序
}
for(int i = 1; i <= n; i ++) {
tot = 0; cnt = 1; //赋初值
vis[1] = i; //第一个就选i
tmp -= c[i][tar[i][1]]; //i的最优性剪枝的影响要去掉
//因为剪枝的时候是以还未访问和还未将被访问的点为基础的
//不去掉剪枝就是错误的
lev[i] = 1; //赋值
dfs(1, 1); //只有一个点，也肯定是从1枚举
lev[i] = 0; //回溯
tmp += c[i][tar[i][1]];
}
printf("%d", ans);
return 0;
}希望大家学习高级算法后不要忘了那些低级算法的重要！！
By Xiyue reverymoon