刷题记录:牛客NC20568[SCOI2012]滑雪与时间胶囊
时间 记录 刷题 牛客
2023-09-14 09:12:55 时间
传送门:牛客
题目描述:
a180285非常喜欢滑雪。他来到一座雪山,这里分布着M条供滑行的轨道和N个轨道之间的
交点(同时也是景点),而且每个景点都有一编号i(1 ≤ i ≤ N)和一高度Hi。a180285 能
从景点i 滑到景点j 当且仅当存在一条i 和j 之间的边,且i 的高度不小于j。
与其他滑雪爱好者不同,a180285喜欢用最短的滑行路径去访问尽量多的景点。如果仅仅
访问一条路径上的景点,他会觉得数量太少。于是a180285拿出了他随身携带的时间胶
囊。
这是一种很神奇的药物,吃下之后可以立即回到上个经过的景点(不用移动也不被认为是
a180285 滑行的距离)。
请注意,这种神奇的药物是可以连续食用的,即能够回到较长时间 之前到过的景点(比如
上上个经过的景点和上上上个经过的景点)。
现在,a180285站在1号景点望着山下的目标,心潮澎湃。他十分想知道在不考虑时间 胶
囊消耗的情况下,以最短滑行距离滑到尽量多的景点的方案(即满足经过景点数最大的前
提下使得滑行总距离最小)。你能帮他求出最短距离和景点数吗?
输入:
3 3
3 2 1
1 2 1
2 3 1
1 3 10
输出:
3 2
一道最小生成树的题目
主要思路:
- 首先我们看一下题目,我们会发现我们的出发点可以使任意之前所走过的点,这就意味着对于每一点来说,我们到达这一点的花费等同于将这个点加入我们的联通量的花费,而这个步骤恰好是一个最小生成树的过程,对于这个过程,我们使用 p r i m prim prim算法进行实现,对于 p r i m prim prim,如果不太熟悉可以看这篇博客
- 但是和最小生成树不同的是,这道题中我们有一个高度的限制,我们会发现高度高的肯定是无法被高度低的所更新的.那么此时对于 p r i m prim prim算法来说,我们进行排序的第一关键字就是我们的高度,第二关键字是我们的将其加入我们联通量的花费.因为对于 p r i m prim prim算法来说,我们的算法思想是尽量用最小的花费将点加入我们的联通量中,而对于优先队列中高度最高的点来说,这个点无法被之后的点所更新了,那么此时需要的花费就是最小的花费了.所以贪心正确性是可以得到保证的.而小的点可以被大的点所更新,所以应该放在后面.这样我们就巧妙的解决了高度的问题
注意使用long long
下面是具体的代码部分:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
ll x=0,w=1;char ch=getchar();
for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*w;
}
#define int long long
#define maxn 1000000
const double eps=1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
struct Node{
int v,w;
};
vector<Node>edge[maxn];
struct heapnode{
int u,d;
};
int h[maxn];
bool operator < (const heapnode a,const heapnode b) {
if(h[a.u]==h[b.u]) return a.d>b.d;
else return h[a.u]<h[b.u];
}
int n,m;
int cnt=0,ans=0;int vis[maxn],dis[maxn];
void prim(int S) {
for(int i=1;i<=n;i++) dis[i]=int_INF;
dis[S]=0;
priority_queue<heapnode>q;
q.push({S,0});
while(!q.empty()&&cnt<n) {
heapnode f=q.top();q.pop();
int u=f.u;
if(vis[u]) continue;
vis[u]=1;
cnt++;ans+=dis[u];
for(int i=0;i<edge[u].size();i++) {
int v=edge[u][i].v;
if(dis[v]>edge[u][i].w) {
dis[v]=edge[u][i].w;
q.push({v,dis[v]});
}
}
}
}
signed main() {
n=read();m=read();
for(int i=1;i<=n;i++) h[i]=read();
for(int i=1;i<=m;i++) {
int u=read(),v=read(),w=read();
if(h[u]>=h[v]) edge[u].push_back({v,w});
if(h[v]>=h[u]) edge[v].push_back({u,w});
}
prim(1);
cout<<cnt<<" "<<ans<<endl;
return 0;
}
相关文章
- PHP 指定时间/时间戳+某天/某月/某年
- 华为手机备忘录中怎么设置待办时间的重复提醒?
- 2023国考报名时间和考试时间安排 用手机待办清单记录
- 2022年五一法定节假日是几天?五一劳动节放假时间用便签记录
- 2021双十一晚会直播在哪看?可在便签上记录播出时间和平台
- 怎么样才能在手机上设置时间规划进行自律?
- C# 获取某个时间的0点0分和23点59分59秒
- linux时间
- C# txt格式记录时间,时间对比,决定是否更新代码记录Demo
- Linux获取进程执行时间
- thinkphp中在页面怎么格式输出小数和时间
- 解决vsftpd日志时间问题
- Futter基础第18篇: 实现调用原生时间选择器、日期选择器、时间戳、Future异步
- Android Calendar方法根据出生的时间戳获取当前年龄
- dateparser解析常见的时间字符串
- c++ 怎样获取系统时间
- linux时间格式
- (12)yolov5+deepsort 应用实例之跟踪目标起始时间并记录结果图像
- 时间API在更新,传奇已经谢幕,但技术永远不死