[luoguP2573/SCOI2012]滑雪

题意

给定一个有 \(n\) 个景点和 \(m\) 条边的无向图，景点有高度 \(h_i\)。从景点 \(i\) 到 \(j\) 的移动仅当 \(h_i \geq h_j\) 且有边 \((i, j)\)。从景点 \(1\) 出发，使用最短距离访问最多景点，且可使用回溯道具回到上一个点。求最多景点数和最短距离。

sol

如果本题无高度限制，那么这道题就是一道很水的最小生成树题目。但幸运的是，即便加入了高度限制，也可以很简单的建出图并计算出可以到达的最多景点数，去掉无法到达的边和点后，可以得到一个新图，包含所有可能遍历到的边和点。因此对这个图计算最小生成树即可。
在使用 Kruskal 时，需要注意：为使其可以遍历到所有点，需要将终点高度作为第一关键字（从大到小），边权作为第二关键字(从小到大)进行排序，原因如下：
记所有位于当前生成树中的点集为 \(S\)，\(S\) 可一步到达的点中，其中高度最高的点必定要选，因为若选择了高度更小的点 ，则会出现高度更高的点无法被选的情况。

代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100005, M = 2000005;

int h[N], e[M], w[M], ne[M], idx;
bool st[N];
int ht[N];
int n, m;
int edge_cnt;
int cnt;
int fa[N];

struct Edge {
    int a, b, c;

    bool operator< (const Edge &W) const{
        if (ht[b] != ht[W.b]) return ht[b] > ht[W.b];
        return c < W.c;
    }
}edges[M];

void add(int a, int b, int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u){
    if (st[u]) return ;
    cnt ++ ;
    st[u] = true;

    for (int i = h[u]; ~i; i = ne[i]){
        int j = e[i];
        edges[ ++ edge_cnt] = {u, j, w[i]};
        dfs(j);
    }
}

int find(int x){
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

int main(){
    memset(h, -1, sizeof h);

    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &ht[i]);
    while (m -- ){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        int ha = ht[a], hb = ht[b];
        if (ha == hb) add(a, b, c), add(b, a, c);
        else if (ha > hb) add(a, b, c);
        else add(b, a, c);
    }

    dfs(1);
    printf("%d ", cnt);

    sort(edges + 1, edges + edge_cnt + 1);
    for (int i = 1; i <= n; i ++ ) fa[i] = i;

    long long cost = 0;
    for (int i = 1; i <= edge_cnt; i ++ ){
        int faa = find(fa[edges[i].a]), fab = find(fa[edges[i].b]);
        if (faa == fab) continue;
        cost += edges[i].c;
        fa[faa] = fab;
    }

    printf("%lld\n", cost);

    return 0;
}