【每日一题】[SCOI2012]滑雪与时间胶囊

[SCOI2012]滑雪与时间胶囊

https://ac.nowcoder.com/acm/problem/20568

题目太长了啦,来个概要


题目概要

题目描述:
有一座雪山,这里有N个山头和M条轨道。滑雪者从a山头滑到b山头要求,a山比b山高或相等。
滑雪者想要从1号山头开始滑尽量多的山头。滑雪者有回溯的能力(返回上一个节点),并且可以连续回溯。
得到以最短滑行距离滑到尽量多的景点的方案。
求出最短距离和最多可以景点数。

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

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


解析

这道题,在我们看到题干的时候就发现,又是熟悉的配方。但是多了一点不熟悉的操作。
  • 毫无疑问,这道题我们可以用前向星用于保存。然后我们这里要用到新的操作:kruskal(求最小生成树,看专栏)。

那我们就来讲一下代码怎么写吧:
  1. 首先我们还是用前向星(可看专栏)保存我们的点与边:但是有一点点不一样的是,这是一个有向图
  2. 方向在哪呢?题目告诉了我们只能从高山滑到低山。所以我们先根据山的高低来建立前向星正反方向
  3. 当我们建立好了树的结构之后就要开始操作了。首先我们要判断情况:我们很可能不会走完所有的节点(比如这不是一张连通图)。
  4. 所以我们先用一遍bfs+visited数组(探测数组探测走过的位置),标记出我们所有能走的位置,并计数(计数是因为答案要我们输出)。
  5. 然后再用kruskal建立最小生成树,并在构建新边的过程中累加路径和。(不懂就看专栏)
  6. 详情看代码~


kruskal算法 + prim算法(构建最小生成树)

kruskal算法是图论中用于构建最小生成树的算法。相对应的还有prim算法。
那么kruskal算法是怎么操作的呢?我先简单描述一下:
  • 我们在边集里面任选一条最小边,如果该边的两个端点不在同一棵树里面,我们就将他们相连
  • 举个栗子就是:我们先认为所有的点都是一棵单独的树(以上图为标准)。
  • 最开始所有边里面最小的是3~6点之间的1,两边是不同的生成树,我们将他们相连。然后是3~4之间的2,两边依旧不同,我们将其相连。
  • 接下来最小的就是3了,但是我们可以看出来4和6已经在同一棵树里面了。所以不连找下一个。
  • 接下来所有边里面最小的是4~5点之间的4,两边是不同的生成树,我们将他们相连。然后是5~1之间的5,两边依旧不同,我们将其相连。
  • 依次类推。但是我们这里所有边权都不同,有相同边权怎么办呢?随便选一条就行了(所以最小生成树可能不唯一)。

与此同时,我们再来简单介绍一下prim算法
  • 我们以某一个点为起点,每次选择我们已经生成的树可以相连的最小边,加入我们的生成树。
  • 就拿这张图举例子:最开始是1号点,因为树能相邻的边最小为5,所以连上了5号点。然后所有相邻边里面最小是4,就连上了4号点。以此类推。

几句话概括好了原理之后,我们就要讲怎么用代码实现了:
  1. 首先我们要干的就是如何去添加边?这个简单咯,排个序就好了
  2. 然后我们怎么才能知道那些已经是我们的生成树成员了呢?这里就要用到查并集的知识了。
  3. 简单来说就是给每个节点找个父亲,然后以最开始的那个元素为根,只要根相同,就是同一个生成树成员。(可以认为是数组化的树找根)
  4. 于是每次将最小边加入生成树,我们最后就能得到最小生成树啦


AC代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef long long ll;
//代码预处理区

const int MAX = 1e6 + 7;
int N, M, H[MAX];//点数,边数,点高度
int head[MAX], tot = 0;//前向星变量
struct Node {
    int u, v, w, next;
    bool operator < (const Node& b)const {
        if (H[v] == H[b.v]) return w < b.w;//边长升序
        return H[v] > H[b.v];//高度降序
    }
} edge[MAX << 1];
int visited[MAX], fa[MAX];//标记可走的所有地方, 查并集数组
ll cnt = 0, sum = 0;//连通图节点个数(可抵达山峰数量),连通图权和
//全局变量区

template<class T>inline void read(T& res);//整型快读函数
void add_edge(int u, int v, int w);//前向星添加边
void bfs(int start);//广搜判连通块(可以抵达的所有地方)
int find(int x);//查并集找父亲
void kruskal();//构建最小生成树并求出权和
//函数预定义区

int main() {
    read(N); read(M);
    memset(H, 0, sizeof H);
    for (int i = 1; i <= N; i++)
        read(H[i]);
    memset(head, 0, sizeof head); tot = 0;
    for (int i = 1; i <= M; i++) {
        int U, V, K; read(U); read(V); read(K);
        if (H[U] >= H[V]) add_edge(U, V, K);
        if (H[V] >= H[U]) add_edge(V, U, K);
    }
    //前向星表示图初始化
    bfs(1);
    sort(edge + 1, edge + 1 + tot);
    //按边权升序排序,保证每次取到最小边权的路径
    kruskal();
    printf("%lld %lld", cnt, sum);
    return 0;
}
template<class T>inline void read(T& res) {
    char c; T flag = 1;
    while ((c = getchar()) < '0' || c > '9')
        if (c == '-')
            flag = -1;
    res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        res = res * 10 + c - '0';
    res *= flag;
}
void add_edge(int u, int v, int w) {
    tot++;
    edge[tot].u = u;
    edge[tot].v = v;
    edge[tot].w = w;
    edge[tot].next = head[u];
    head[u] = tot;
}
void bfs(int start) {
    memset(visited, 0, sizeof visited);
    queue<int> que; que.push(start);
    visited[start] = 1; cnt++;
    while (!que.empty()) {
        int u = que.front(); que.pop();
        for (int i = head[u]; i; i = edge[i].next) {
            int v = edge[i].v;
            if (!visited[v]) {
                que.push(v);
                visited[v] = 1;
                cnt++;
            }
        }
    }
}
int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void kruskal() {
    sum = 0;
    for (int i = 1; i <= N; i++) fa[i] = i;
    for (int i = 1; i <= tot; i++) {
        int u = edge[i].u, v = edge[i].v, w = edge[i].w;
        if (visited[u] && visited[v])
            if (find(u) != find(v)) {
                fa[find(u)] = find(v);
                sum += w;
            }
            //发现了可走,而且是新路的地方,联通并计算长度
    }
}
//函数区
每日一题 文章被收录于专栏

憨憨的专栏

全部评论

相关推荐

榕城小榕树:1200单休,我去干点啥别的不好
点赞 评论 收藏
分享
点赞 评论 收藏
分享
避坑恶心到我了大家好,今天我想跟大家聊聊我在成都千子成智能科技有限公司(以下简称千子成)的求职经历,希望能给大家一些参考。千子成的母公司是“同创主悦”,主要经营各种产品,比如菜刀、POS机、电话卡等等。听起来是不是有点像地推销售公司?没错,就是那种类型的公司。我当时刚毕业,急需一份临时工作,所以在BOSS上看到了千子成的招聘信息。他们承诺无责底薪5000元,还包住宿,这吸引了我。面试的时候,HR也说了同样的话,感觉挺靠谱的。于是,我满怀期待地等待结果。结果出来后,我通过了面试,第二天就收到了试岗通知。试岗的内容就是地推销售,公司划定一个区域,然后你就得见人就问,问店铺、问路人,一直问到他们有意向为止。如果他们有兴趣,你就得摇同事帮忙推动,促进成交。说说一天的工作安排吧。工作时间是从早上8:30到晚上18:30。早上7点有人叫你起床,收拾后去公司,然后唱歌跳舞(销售公司都这样),7:55早课(类似宣誓),8:05同事间联系销售话术,8:15分享销售技巧,8:30经理训话。9:20左右从公司下市场,公交、地铁、自行车自费。到了市场大概10点左右,开始地推工作。中午吃饭时间大约是12:00,公司附近的路边盖饭面馆店自费AA,吃饭时间大约40分钟左右。吃完饭后继续地推工作,没有所谓的固定中午午休时间。下午6点下班后返回公司,不能直接下班,需要与同事交流话术,经理讲话洗脑。正常情况下9点下班。整个上班的一天中,早上到公司就是站着的,到晚上下班前都是站着。每天步数2万步以上。公司员工没有自己的工位,百来号人挤在一个20平方米的空间里听经理洗脑。白天就在市场上奔波,公司的投入成本几乎只有租金和工资,没有中央空调。早上2小时,晚上加班2小时,纯蒸桑拿。没有任何福利,节假日也没有3倍工资之类的。偶尔会有冲的酸梅汤和西瓜什么的。公司的晋升路径也很有意思:新人—组长—领队—主管—副经理—经理。要求是业绩和团队人数,类似传销模式,把人留下来。新人不能加微信、不能吐槽公司、不能有负面情绪、不能谈恋爱、不能说累。在公司没有任何坐的地方,不能依墙而坐。早上吃早饭在公司外面的安全通道,未到上班时间还会让你吃快些不能磨蹭。总之就是想榨干你。复试的时候,带你的师傅会给你营造一个钱多事少离家近的工作氛围,吹嘘工资有多高、还能吹自己毕业于好大学。然后让你早点来公司、无偿加班、抓住你可能不会走的心思进一步压榨你。总之,大家在找工作的时候一定要擦亮眼睛,避免踩坑!———来自网友
qq乃乃好喝到咩噗茶:不要做没有专业门槛的工作
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-04 15:36
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务