【每日一题】[SCOI2012]滑雪与时间胶囊
[SCOI2012]滑雪与时间胶囊
https://ac.nowcoder.com/acm/problem/20568
题目太长了啦，来个概要
题目描述：
输入描述：
输入的第一行是两个整数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;
}
//发现了可走，而且是新路的地方，联通并计算长度
}
}
//函数区每日一题 文章被收录于专栏
憨憨的专栏
投递小天才等公司7个岗位