每日一题：滑雪与时间胶囊（最小生成树）

题意

给定一个 $n$ 个点 $m$ 条边图，只能从点权高的点走到低的，且可以不计路程的瞬移至之前走过的某个点，求经过最多点的最短路径。

solution

求经过最多点显然直接bfs，建图的时候建高到低的单向边即可，（值得注意的是，若点权相同，则为相互可达的，需要建双向边）。然后根据bfs遍历可以走到的点，将走过的边加入边集，建一个新图出来。为了使路径最短，考虑最小生成树，但需要满足题目的条件，因此我们对新的图进行排序，以高度为第一关键字从大到小排，再以路径长度为第二关键字从小到大排，这样可以保证点最多的同时路径最短。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 5;
int n, m, tot, cnt, hi[N], h[N], pre[N], vis[N];

struct Node {
  int from, to, v, next;
} g[N], E[N];

void add1(int x, int y, int z) {
  g[tot].from = x, g[tot].to = y, g[tot].v = z, g[tot].next = h[x],
  h[x] = tot++;
}

void add2(int x, int y, int z) {
  cnt++, E[cnt].from = x, E[cnt].to = y, E[cnt].v = z;
}

bool cmp(Node x, Node y) {
  if (hi[x.to] == hi[y.to]) return x.v < y.v;
  return hi[x.to] > hi[y.to];
}

int xfind(int x) {
  int i = x, j = x, temp;
  while (i != pre[i]) i = pre[i];
  while (i != j) {
    temp = pre[j];
    pre[j] = i;
    j = temp;
  }
  return i;
}

void bfs() {
  int res1 = 1;
  queue<int> q;
  vis[1] = true;
  q.push(1);
  while (q.size()) {
    int u = q.front();
    q.pop();
    for (int i = h[u]; ~i; i = g[i].next) {
      int v = g[i].to;
      add2(u, v, g[i].v);
      if (!vis[v]) {
        vis[v] = true;
        res1++;
        q.push(v);
      }
    }
  }
  printf("%d ", res1);
}

void Kruscal() {
  long long res2 = 0;
  int num = 0;
  for (int i = 1; i <= cnt; i++) {
    int x = E[i].from, y = E[i].to;
    int fx = xfind(x), fy = xfind(y);
    if (fx != fy) {
      pre[fx] = fy;
      res2 += E[i].v;
      num++;
    }
    if (num == n - 1) break;
  }
  printf("%lld\n", res2);
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &hi[i]);
    pre[i] = i;
  }
  memset(h, -1, sizeof(h));
  for (int i = 1; i <= m; i++) {
    int x, y, z;
    scanf("%d%d%d", &x, &y, &z);
    if (hi[x] >= hi[y]) add1(x, y, z);
    if (hi[x] <= hi[y]) add1(y, x, z);
  }
  bfs();
  sort(E + 1, E + cnt + 1, cmp);
  Kruscal();
  return 0;
}