首页 > [SCOI2012]滑雪与时间胶囊
开通博客写题解
头像 Kur1su
发表于 2020-04-30 16:57:13
Solution 这题在洛谷上是紫题, 但是好像没有想象中那么难很容易看出这题是要求从点 开始扩展的最小生成树因为有一个高度的限制, 不能直接求如果用 的话好像不知道怎么下手这个时候想到了用堆优化的 在优先队列里我们多加一个条件即先往高度大的地方走, 不行再往当前连通块的最近点走即可注意题目没给 展开全文
去ta的博客 赞 (7) 回复(1) 收起
头像 _LRJ_
发表于 2020-05-07 22:32:29
Kruskal+Greedy 这个题目还是一个比较有意思的题目啦。我们想解决这个问题还是需要一点前置知识的。首先我们来讲一下最小生成树的一些概念。已经有所了解的小伙伴可以直接跳到分割线后 最小生成树 首先我通俗讲一讲现在比较主流的一些最小生成树的做法。①prim算法。这个是一个基于加入点的做法了， 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 rk_no
发表于 2020-04-30 18:20:32
题目： a180285非常喜欢滑雪。他来到一座雪山，这里分布着M条供滑行的轨道和N个轨道之间的交点（同时也是景点），而且每个景点都有一编号i（1 ≤ i ≤ N）和一高度Hi。a180285 能从景点i 滑到景点j 当且仅当存在一条i 和j 之间的边，且i 的高度不小于j。与其他滑雪爱好者不同，a1 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 与人无语
发表于 2020-05-03 14:12:54
这题我一看就感觉是最小生成树的板子题然后开心的复制板子改一下输出 过了样例 提交然后就是ac0% why？在仔细看题 貌似点的高度没用 好像只能从高点滑到低点 。。。我最小生成树只会kruscal算法貌似不能解决 开始学习prim算法最后掏出了这个优先队列优化的prim算法（最小生成树板子并且 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 平凡的小白
发表于 2020-05-06 20:54:57
题意 题目描述：有一座雪山，这里有N个山头和M条轨道。滑雪者从a山头滑到b山头要求，a山比b山高或相等。滑雪者想要从1号山头开始滑尽量多的山头。滑雪者有回溯的能力（返回上一个节点），并且可以连续回溯。得到以最短滑行距离滑到尽量多的景点的方案。求出最短距离和最多可以景点数。 输入描述：输入的第一行是 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 19_hanhan
发表于 2020-05-01 02:22:08
题目太长了啦，来个概要 题目概要 题目描述： 有一座雪山，这里有N个山头和M条轨道。滑雪者从a山头滑到b山头要求，a山比b山高或相等。 滑雪者想要从1号山头开始滑尽量多的山头。滑雪者有回溯的能力（返回上一个节点），并且可以连续回溯。 得到以最短滑行距离滑到尽量多的景点的 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 回归梦想
发表于 2020-05-04 18:05:26
链接： 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld 题目描述 a180285非常喜欢滑雪。他来到一座雪山，这里分布着M条供滑行的轨道和N个轨道之间的交点（同时也是景点），而且每个景点都有一编号 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 人丑心更黑
发表于 2021-03-17 09:26:44
prim和Kruskal太久不打，都忘光啦。 题目大意：给n个点和m条边，每个点有一个高度h[i]，给定的m条边都有三个参数u,v,k表示u和v点有一天长度为k的边。其中这条边只能从高度高的地方连向高度低的地方。（两个点高度相同时就是无向边，否则是有向边）现在你可以从点1开始，问最多可以访问到的点的 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 sunsetcolors
发表于 2020-04-30 15:01:24
NC20568 [SCOI2012]滑雪与时间胶囊 题目地址： https://ac.nowcoder.com/acm/problem/20568 基本思路： 先吐槽一下这题题面里是不是没给数据范围啊QwQ这题我们首先会发现这个高度很重要，因为有高度的限制那么这个这个无向图实际上就能构造成一 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 sunrise__sunrise
发表于 2020-05-03 09:45:16
时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld 题目描述 a180285非常喜欢滑雪。他来到一座雪山，这里分布着M条供滑行的轨道和N个轨道之间的交点（同时也是景点），而且每个景点都有 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”