题目太长了啦,来个概要


题目概要

题目描述:
有一座雪山,这里有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;
            }
            //发现了可走,而且是新路的地方,联通并计算长度
    }
}
//函数区