题解 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!非常的小，带上一大串常数都没问题 因此我们考虑深搜 如何爆搜？ 第一反应是枚举全排列然后去更新答案。 但是有问题啊，知道点开拓的顺序并没有什么用，我们还要知道它是由哪个点开拓而来的。 因此我们再枚举去开拓的点： 代码如下 ```cpp #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。 那让我们结合详细的注释来看看如何剪枝。 ```cpp #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