首页 > 其他分享 >NC20568 [SCOI2012]滑雪与时间胶囊

NC20568 [SCOI2012]滑雪与时间胶囊

时间:2023-01-05 18:15:32浏览次数:65  
标签:NC20568 le a180285 10 int fa 景点 滑雪 SCOI2012

题目链接

题目

题目描述

a180285非常喜欢滑雪。他来到一座雪山,这里分布着M条供滑行的轨道和N个轨道之间的交点(同时也是景点),而且每个景点都有一编号i(1 ≤ i ≤ N)和一高度Hi。a180285 能从景点i 滑到景点j 当且仅当存在一条i 和j 之间的边,且i 的高度不小于j。

与其他滑雪爱好者不同,a180285喜欢用最短的滑行路径去访问尽量多的景点。如果仅仅访问一条路径上的景点,他会觉得数量太少。于是a180285拿出了他随身携带的时间胶囊。

这是一种很神奇的药物,吃下之后可以立即回到上个经过的景点(不用移动也不被认为是 a180285 滑行的距离)。

请注意,这种神奇的药物是可以连续食用的,即能够回到较长时间 之前到过的景点(比如上上个经过的景点和上上上个经过的景点)。

现在,a180285站在1号景点望着山下的目标,心潮澎湃。他十分想知道在不考虑时间 胶囊消耗的情况下,以最短滑行距离滑到尽量多的景点的方案(即满足经过景点数最大的前 提下使得滑行总距离最小)。你能帮他求出最短距离和景点数吗?

输入描述

输入的第一行是两个整数N,M。
接下来1行有N个整数Hi,分别表示每个景点的高度。
接下来M行,表示各个景点之间轨道分布的情况。每行3个整数,Ui,Vi,Ki。表示编号为Ui的景点和编号为Vi的景点之间有一条长度为Ki的轨道。

输出描述

输出一行,表示a180285最多能到达多少个景点,以及此时最短的滑行距离总和。

示例1

输入

3 3 
3 2 1 
1 2 1 
2 3 1 
1 3 10

输出

3 2

备注

对于30% 的数据,\(1 \le n \le 2000\) ;
对于100% 的数据,\(1 \le n \le 10^5\) 。对于所有的数据,保证 \(1 \le m \le 10^6\) , \(1 \le h_i \le 10^9\) ,\(1 \le k_i \le 10^9\) 。

题解

知识点:DFS,最小生成树。

显然,起点连通的景点都是需要到达的,因此先DFS一遍求多少景点可以到达。

建图时,要保证边的方向是高到低的,且记录较低点的高度方便之后排序。

因为有胶囊可以随意传送,所以原题实际上就是最小生成树了,但生成的方式不太一样。由于,景点只能从高到底走,换句话说,如果高的景点走不到的话,那么其后低的景点也是不能走到的。如果单纯根据边权排序,可能会出现 高->低->高 的情况,实际上这是不合法的。

因此,先按照高度为第一关键字从高到底排序,再按照边权为第二关键字从小到大排序。选边时,边的两端应该要和起点连通,这在第一步DFS时可以记录起点是否能达到 \(vis\) ,其次和普通最小生成树一样两端点目前处在不同连通块内才需要选边。

时间复杂度 \(O(n+m(\log m+\log n)\)

空间复杂度 \(O(n+m)\)

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int h[100007];
vector<int> g[100007];
struct edge {
    int u, v, w, h;
}e[1000007];

int cnt = 0;
bool vis[100007];
void dfs(int u) {
    vis[u] = 1;
    cnt++;
    for (auto v : g[u]) {
        if (!vis[v]) dfs(v);
    }
}

int fa[100007];
int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y) {
    fa[find(x)] = find(y);
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1;i <= n;i++) cin >> h[i];
    for (int i = 1;i <= m;i++) {
        int u, v, w;
        cin >> u >> v >> w;
        e[i] = { u,v,w ,min(h[u],h[v]) };///短的那个是出点
        if (h[u] >= h[v]) {
            g[u].push_back(v);
        }
        if (h[u] <= h[v]) {
            g[v].push_back(u);
        }
    }
    dfs(1);
    for (int i = 1;i <= n;i++) fa[i] = i;
    sort(e + 1, e + 1 + m, [&](const edge &a, const edge &b) {
        return a.h > b.h ? 1 : a.h == b.h ? a.w < b.w : 0;
    });///因为是有向图,不确定滑道的较高点是否能走到。因此先把滑道出点较高的取了,保证滑道出点较矮的取的时候较高点一定走到了。
    ll sum = 0;
    for (int i = 1;i <= m;i++) {
        auto [u, v, w, h] = e[i];
        if (!vis[u] || !vis[v]) continue;
        if (find(u) == find(v)) continue;
        sum += w;
        merge(u, v);
    }
    cout << cnt << ' ' << sum << '\n';
    return 0;
}

标签:NC20568,le,a180285,10,int,fa,景点,滑雪,SCOI2012
From: https://www.cnblogs.com/BlankYang/p/17028497.html

相关文章

  • 上架亚马逊的自行车、滑雪和滑板头盔的标准是什么
    自行车头盔、滑雪头盔和滑板头盔上架亚马逊的有哪些规定标准?      头盔是作为个人防护类产品的最重要的一部分,肩负着保护运动人士生命安全的重任。越来越多的运动需......
  • P1434 [SHOI2002] 滑雪(记忆化搜索 DAG)
    P1434[SHOI2002]滑雪题意给你一个\(n\timesm\)的矩阵\(A\),\(A_{i,j}\)代表\((i,j)\)这个地方的高度,你可以从任意一个地方出发,然后走到一个和这个地方四联通......
  • POJ-1088 滑雪
    POJ-1088滑雪有一个平面区域,上面有一些点,每个点对应一定的权值,每次移动只能从当前位置向上下左右四个方向中,权值小于当前位置权值的点移动,一次性最多可以移动多远(相邻位......
  • 滑雪
    题目链接:https://www.acwing.com/problem/content/903/题目描述给定一个R行C列的矩阵,表示一个矩形网格滑雪场。矩阵中第i行第j列的点表示滑雪场的第i行第j......
  • 洛谷P1434滑雪分析
    [SHOI2002]滑雪题目描述Michael喜欢滑雪。这并不奇怪,因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来......
  • #yyds干货盘点# 动态规划专题:滑雪
    1.简述:描述NowCoder喜欢滑雪,因为滑雪的确很刺激。为了获得速度,必须从高处往低处滑。现在知道某片区域的海拔,如下所示1 2 3 4516171819615242520714......
  • 【SA+莫队】P2336 [SCOI2012]喵星球上的点名
    [SCOI2012]喵星球上的点名题目描述a180285幸运地被选做了地球到喵星球的留学生。他发现喵星人在上课前的点名现象非常有趣。假设课堂上有\(n\)个喵星人,每个喵星人的......
  • 【python 游戏】闲的无聊?那就和博主一起来滑雪吧~
    前言嗨喽~大家好呀,这里是魔王呐!  滑雪运动(特别是现代竞技滑雪)发展到当今,项目不断在增多,领域不断在扩展。世界比赛正规的大项目分为:高山滑雪、北欧滑雪(NordicSk......
  • 用火箭外壳技术制造滑雪头盔?
    用火箭外壳技术制造滑雪头盔?近日,2022年北京冬奥会开幕进入倒计时,为助力“科技冬奥”,大连理工大学科研团队自主研发的一款高性能滑雪头盔,引来不少网友点赞:堪称“黑科技、高颜......
  • 1036 [SCOI2012]滑雪与时间胶囊 最小生成树 可以用prim做的DAG prim+kruskal不能做DAG
    链接:https://ac.nowcoder.com/acm/contest/26077/1036来源:牛客网题目描述a180285非常喜欢滑雪。他来到一座雪山,这里分布着M条供滑行的轨道和......