P3959 [NOIP2017 提高组] 宝藏 题解

news/2024/10/11 18:18:05

P3959 [NOIP2017 提高组] 宝藏 题解

搜索魅力时刻

怎么说，四种做法

  • 比较？？的模拟退火
  • 跑得快但是 正确性有问题的 状压DP
  • 跑得慢但是 一定正确的 状压 DP
  • 时间复杂度很玄学的DFS+剪枝

我就选择了搜索的做法

先打个暴搜，70pts

点击查看暴搜代码 
#include <bits/stdc++.h>
using namespace std;
const int inf = 998244353;
int n, m;
int dis[100][100];
struct node
{// int vis;int step;
};
node nds[114514];
int tmp;
int ans = inf;
void dfs(int num)
{if (tmp > ans){return;}if (num == n){ans = min(ans, tmp);}else{for (int yy = 1; yy <= n; yy++) //由谁拓展{if (nds[yy].step){for (int tt = 1; tt <= n; tt++) //拓展到谁{if (nds[tt].step == 0 && yy != tt && dis[yy][tt] != inf)//如果能去{tmp += nds[yy].step * dis[yy][tt];nds[tt].step = nds[yy].step + 1;dfs(num + 1);tmp -=nds[yy].step * dis[yy][tt];nds[tt].step=0;}}}}}
}
int main()
{ios::sync_with_stdio(false);cin >> n >> m;memset(dis, inf, sizeof(dis));int a, b, c;for (int yy = 1; yy <= m; yy++){cin >> a >> b >> c;if (dis[a][b] < c){continue;}if (dis[a][b] > c){dis[b][a] = c;dis[a][b] = c;}}for (int ww = 1; ww <= n; ww++) //枚举起点{nds[ww].step = 1;dfs(1);nds[ww].step = 0;}cout<<ans;return 0;
}

接下来就是想着怎么优化了

自然，我们可以想到这题可以加上一个最优化剪枝，然后在记录一下哪些点被拓展过。
就可以得到如下代码

点击查看优化代码-1 
#include <bits/stdc++.h>
using namespace std;
const int inf = 198244353;
int n, m;
int dis[100][100], sho[100];
int dd[55];
struct node
{// int vis;int step;
};
node nds[114514];
int tmp;
int ans = inf;
int short_;
void dfs(int num)
{// cout<<(3*ans)/2<<endl;if (num == n){ans = min(ans, tmp);}else{for (int ysy = 1; ysy <= num; ysy++) //由谁拓展{int yy = dd[ysy];//最优化剪枝if (tmp + short_ * nds[yy].step > ans)//如果当前代价加上后面的最小代价还是比之前的答案大，那么一定不优{return;}for (int tt = 1; tt <= n; tt++) //拓展到谁{if (nds[tt].step == 0 && yy != tt && dis[yy][tt] != inf){tmp += nds[yy].step * dis[yy][tt];nds[tt].step = nds[yy].step + 1;short_ -= sho[tt];//减去这个点的最小代价dd[num + 1] = tt;dfs(num + 1);dd[num + 1] = 0;short_ += sho[tt];tmp -= nds[yy].step * dis[yy][tt];nds[tt].step = 0;}}}}
}
int main()
{// freopen("P3959_1.in", "r", stdin);// freopen("", "w", stdout);ios::sync_with_stdio(false);cin >> n >> m;memset(dis, inf, sizeof(dis));int a, b, c;for (int yy = 1; yy <= m; yy++){cin >> a >> b >> c;// if (dis[a][b] < c)// {// continue;// }// if (dis[a][b] > c)dis[b][a] = min(dis[b][a], c);dis[a][b] = min(dis[a][b], c);}for (int yy = 1; yy <= n; yy++){int ww = inf;for (int ee = 1; ee <= n; ee++)//获取每个点的最小代价，也就是那个最短的出边{if (yy != ee){ww = min(ww, dis[yy][ee]);}}short_ += ww;sho[yy] = ww;}for (int ww = 1; ww <= n; ww++) //枚举起点{tmp = 0;nds[ww].step = 1;short_ -= sho[ww];dd[1] = ww;dfs(1);dd[1] = 0;short_ += sho[ww];nds[ww].step = 0;// cout << ans << "\n";}cout << ans;return 0;
}

官方数据都过了，但是 Hack 数据会有 \(10\) 各点左右 超时，那我们该怎么进一步优化呢？

首先我们可以发现，当我们拓展完一个节点后，又会回到之前拓展过的节点上，重新遍历他们的出度，但是事实上，这些点中的出度已经有很多被遍历过了，所以我们可以用当前弧优化的思想 对于每一个点记录一下这次搜索之中已经遍历到哪个出度了。

加上这个优化的代码 
#include <bits/stdc++.h>
using namespace std;
const int inf = 998244353;
int n, m;
int dis[100][100], sho[100];
int du[100];
int to_[100][100];
int dd[55];
struct node
{int vis=1;int step;
};
node nds[114];
int tmp;
int ans = inf;
int short_;
int cmm;
bool cmp(int a, int b)
{return dis[cmm][a] < dis[cmm][b];
}
void dfs(int num)
{// cout<<(3*ans)/2<<endl;if (num == n){ans = min(ans, tmp);}else{int tt, yy;for (int ysy = 1; ysy <= num; ysy++) //由谁拓展{yy = dd[ysy];if (tmp + short_ * nds[yy].step > ans){return;}// cout<<du[yy]<<"   |||   "<<endl;for (int att = nds[yy].vis; att <= du[yy]; att++) //拓展到谁{nds[yy].vis++;tt = to_[yy][att];// cout<<tt;if (nds[tt].step == 0&&dis[yy][tt]!=inf){tmp += nds[yy].step * dis[yy][tt];nds[tt].step = nds[yy].step + 1;short_ -= sho[tt];dd[num + 1] = tt;dfs(num + 1);dd[num + 1] = 0;short_ += sho[tt];tmp -= nds[yy].step * dis[yy][tt];nds[tt].step = 0;}}nds[yy].vis=1;//C}}
}
int main()
{// freopen("P3959_22.in", "r", stdin);// freopen("", "w", stdout);ios::sync_with_stdio(false);cin >> n >> m;for (int ww = 0; ww <= n + 1; ww++){for (int ee = 0; ee <= n + 1; ee++){dis[ww][ee] = inf;}du[ww]=0;}int a, b, c;for (int yy = 1; yy <= m; yy++){cin >> a >> b >> c;// if (dis[a][b] < c)// {// continue;// }// if (dis[a][b] > c)if (dis[a][b] == inf){du[a]++;du[b]++;to_[a][du[a]] = b;to_[b][du[b]] = a;}dis[b][a] = min(dis[b][a], c);dis[a][b] = min(dis[a][b], c);}for (int yy = 1; yy <= n; yy++){// cout<<du[yy]<<endl;;cmm = yy;sort(to_[yy] + 1, to_[yy] + 1 + du[yy], cmp);int ww = inf;for (int ee = 1; ee <= n; ee++){if (yy != ee){ww = min(ww, dis[yy][ee]);}}short_ += ww;sho[yy] = ww;}for (int ww = 1; ww <= n; ww++) //枚举起点{tmp = 0;nds[ww].step = 1;short_ -= sho[ww];dd[1] = ww;dfs(1);dd[1] = 0;short_ += sho[ww];nds[ww].step = 0;// cout << ans << "\n";}cout << ans;return 0;
}

加上这个优化之后，我们就可以过掉这个题了，但是，还是太慢了,需要足足 \(1.3s\) 才能跑完官方的数据。

事实上，我们还有 \(1\) 个很可以优化的地方：对于最先开始遍历的那些点，我们在循环之中已经把他们都处理完了，下次搜索就不需要再考虑他们，于是，我们再次用上当前弧优化的思想，加上一个传参 来记录有多少个被拓展的点已经被处理完了，加上这个优化之后 ，真就是暴力碾标算，只用 \(130ms\) 就可以跑完官方的所有数据

最终版的代码 
#include <bits/stdc++.h>
using namespace std;
const int inf = 998244353;
int n, m;
int dis[100][100], sho[100];
int du[100];
int to_[100][100];
int dd[55];
/*
dis:邻接矩阵
sho:每个点最短的出边
du:每个点的出度(边已去重)
to_:每个点能到的点
dd:被拓展的点的顺序
*/
struct node
{int vis = 1;int step;
};
node nds[114];//每个洞穴
int tmp;//dfs用的,记录中间答案
int ans = inf;//最终答案
int short_;//每个点最短的出度之和,用于最优化剪枝
int cmm;//sort用
bool cmp(int a, int b)
{return dis[cmm][a] < dis[cmm][b];
}
void dfs(int now_,int num)
{// cout<<(3*ans)/2<<endl;if (num == n){ans = min(ans, tmp);}else{int tt, yy;for (int ysy = now_; ysy <= num; ysy++) //由谁拓展{yy = dd[ysy];if (tmp + short_ * nds[yy].step > ans){return;}for (int att = nds[yy].vis; att <= du[yy]; att++) //拓展到谁{nds[yy].vis++;tt = to_[yy][att];if (tt == 0){cout << "Warning!";cout << yy << "'s " << att << '\n';}if (nds[tt].step == 0){tmp += nds[yy].step * dis[yy][tt];nds[tt].step = nds[yy].step + 1;short_ -= sho[tt];dd[num + 1] = tt;dfs(ysy,num + 1);dd[num + 1] = 0;short_ += sho[tt];tmp -= nds[yy].step * dis[yy][tt];nds[tt].step = 0;}}nds[yy].vis = 1;//这个点处理完了,将其当前弧优化归零}}
}
int main()
{// freopen("P3959_22.in", "r", stdin);// freopen("", "w", stdout);ios::sync_with_stdio(false);cin >> n >> m;for (int ww = 0; ww <= n + 1; ww++){for (int ee = 0; ee <= n + 1; ee++){dis[ww][ee] = inf;}dis[ww][ww]=0;du[ww] = 0;}int a, b, c;for (int yy = 1; yy <= m; yy++){cin >> a >> b >> c;if (dis[a][b] == inf && c < inf){du[a]++;du[b]++;to_[a][du[a]] = b;to_[b][du[b]] = a;}dis[b][a] = min(dis[b][a], c);dis[a][b] = min(dis[a][b], c);}for (int yy = 1; yy <= n; yy++){cmm = yy;sort(to_[yy] + 1, to_[yy] + 1 + du[yy], cmp);//排序,降低复杂度,因为越短的边成为答案的概率越大int ww = inf;for (int ee = 1; ee <= n; ee++)//找到最小的出度(其实这里可以直接用上排序后的结果){if (yy != ee){ww = min(ww, dis[yy][ee]);}}short_ += ww;sho[yy] = ww;}for (int ww = 1; ww <= n; ww++) //枚举起点{tmp = 0;nds[ww].step = 1;short_ -= sho[ww];dd[1] = ww;dfs(1,1);dd[1] = 0;short_ += sho[ww];nds[ww].step = 0;// cout << ans << "\n";}cout << ans;return 0;
}

提交记录:

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.ryyt.cn/news/70315.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈，一经查实，立即删除！

相关文章

AMIS低代码平台，前端开发常见问题(样式篇 图片配置)

AMIS低代码平台，前端开发常见问题(样式篇 图片配置)

关于样式问题在上篇中已经总结过了。 这篇主要说下关于图片的引入。1.页面上的图片引入。 （1）将图片放入apps\bmc\page\bmc-page-config\image目录下。 （2）在静态资源中引入，如下图： （3）在图片控件地址栏中引入也可以直接在地址栏中写入图片路径 2.背景图片的处理 对于…
阅读更多...
coca after two months vs in two months

coca after two months vs in two months

This is the third time in two months.这是两个月内的第三次了。Its the second time in two months Compton Power Equipment at 5375 Urbana Road has been broken into this way.这是两个月内第二次有人闯入厄巴纳路5375号的康普顿电力设备公司。You know, in two months t…
阅读更多...
todolist案例--父子组件协调进行数据传递、方法调用、列表渲染

todolist案例--父子组件协调进行数据传递、方法调用、列表渲染

你想做的都能做成，只是时间问题。
阅读更多...
操作筛选器的 1 个应用实例：自动启用事务

操作筛选器的 1 个应用实例：自动启用事务

在 Asp.Net Core Web API 中，我们可以使用操作筛选器给所有的数据库操作 API 加上事务控制，省心又省力，效果还很好前言 在数据库操作过程中，有一个概念是绕不开的，那就是事务。 事务能够确保一系列数据库操作要么全部成功提交，要么全部失败回滚，保证数据的一致性和完整性…
阅读更多...
C# 线程---Thread1

C# 线程---Thread1

1. thread 不带参数 （Main和Thread都在同步处理）（注意using static 和System.Console的使用）using static System.Console;namespace Recipe1 {class Program{static void Main(string[] args){Thread t = new Thread(PrintNumber);t.Start();PrintNumber();Read();}static…
阅读更多...
解决 java.lang.VerifyError: Stack map does not match the one at exception

解决 java.lang.VerifyError: Stack map does not match the one at exception

项目上用的liteflow，动态编译代码，在项目执行过程中报错如下： 拿到异常信息网上搜索，网上的说法如下： VM加载class文件时会做字节码校验（bytecode verification）。如果你的class文件是由java源文件通过javac编译出来的，那么基本上不用担心bytecode verification。 如果…
阅读更多...
婚恋结构相亲管理系统的技术性分析

婚恋结构相亲管理系统的技术性分析

随着社会发展和人们对婚恋关系的重视，婚恋交友市场逐渐崛起。婚恋结构相亲管理系统作为该市场的重要解决方案，通过互联网平台将用户和服务提供者连接起来，帮助用户高效地寻找和管理自己的婚恋关系。本文将深入探讨婚恋结构相亲管理系统的技术架构、核心功能及其实现方式。一…
阅读更多...
笔记本电脑蓝屏固态硬盘数据恢复

笔记本电脑蓝屏固态硬盘数据恢复

当笔记本电脑出现蓝屏故障，并且需要恢复固态硬盘中的数据时，可以参考以下步骤和建议： 一、初步处理与评估 断开电源：在尝试任何数据恢复操作之前，首先要断开笔记本电脑的电源，以避免进一步的数据损坏或丢失。 评估蓝屏原因：蓝屏可能是由多种原因引起的，如驱动程序错误、…
阅读更多...
推荐文章
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站 尧图建网站 广利置业