题目太长了啦,来个概要
题目描述:
输入描述:
输入的第一行是两个整数N,M。
接下来1行有N个整数Hi,分别表示每个景点的高度。
输出描述:
输出一行,表示滑雪者最多能到达多少个景点,以及此时最短的滑行距离总和。
题目概要
题目描述: 有一座雪山,这里有N个山头和M条轨道。滑雪者从a山头滑到b山头要求,a山比b山高或相等。
滑雪者想要从1号山头开始滑尽量多的山头。滑雪者有回溯的能力(返回上一个节点),并且可以连续回溯。
得到以最短滑行距离滑到尽量多的景点的方案。
求出最短距离和最多可以景点数。
输入的第一行是两个整数N,M。
接下来1行有N个整数Hi,分别表示每个景点的高度。
接下来M行,表示各个景点之间轨道分布的情况。每行3个整数,Ui,Vi,Ki。表示编号为Ui的景点和编号为Vi的景点之间有一条长度为Ki的轨道。
输出一行,表示滑雪者最多能到达多少个景点,以及此时最短的滑行距离总和。
解析
这道题,在我们看到题干的时候就发现,又是熟悉的配方。但是多了一点不熟悉的操作。
- 毫无疑问,这道题我们可以用前向星用于保存。然后我们这里要用到新的操作:kruskal(求最小生成树,看专栏)。
那我们就来讲一下代码怎么写吧:
- 首先我们还是用前向星(可看专栏)保存我们的点与边:但是有一点点不一样的是,这是一个有向图。
- 方向在哪呢?题目告诉了我们只能从高山滑到低山。所以我们先根据山的高低来建立前向星正反方向。
- 当我们建立好了树的结构之后就要开始操作了。首先我们要判断情况:我们很可能不会走完所有的节点(比如这不是一张连通图)。
- 所以我们先用一遍bfs+visited数组(探测数组探测走过的位置),标记出我们所有能走的位置,并计数(计数是因为答案要我们输出)。
- 然后再用kruskal建立最小生成树,并在构建新边的过程中累加路径和。(不懂就看专栏)
- 详情看代码~
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号点。以此类推。
几句话概括好了原理之后,我们就要讲怎么用代码实现了:
- 首先我们要干的就是如何去添加边?这个简单咯,排个序就好了。
- 然后我们怎么才能知道那些已经是我们的生成树成员了呢?这里就要用到查并集的知识了。
- 简单来说就是给每个节点找个父亲,然后以最开始的那个元素为根,只要根相同,就是同一个生成树成员。(可以认为是数组化的树找根)
- 于是每次将最小边加入生成树,我们最后就能得到最小生成树啦。
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; } //发现了可走,而且是新路的地方,联通并计算长度 } } //函数区