[SCOI2012] 滑雪

GitHub跳转原题关系图返回列表

先求从 1 号景点出发能到达的全部景点；在这些点上按边的较低端高度降序、边长升序做 Kruskal，可以在保证可达景点数最大的前提下，把总滑行距离压到最小。

OJ: luogu

题目 ID: P2573

难度:省选/NOI-

标签:图论最小生成树思维推导

日期: 2026-06-20 01:32

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结
  6. 一图流解析

题意

有 n 个景点和 m 条轨道，每个景点有高度。

如果景点 u 和 v 之间有轨道，并且 h[u] >= h[v]，那么就能从 u 滑到 v。

你从 1 号景点出发。每次滑到一个新景点后，可以免费吃时间胶囊，瞬间回到任意一个之前经过的景点。

要求：

  1. 先让经过的景点数尽量多
  2. 在这个前提下，让总滑行距离最小

输出“最多能经过多少个景点”和“此时最短的总距离”。

思路

先看一个小数据暴力：

cpp
// brute.cpp：小数据集合 DP，直接按“已访问景点集合”转移。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 12;
const long long INF = (1LL << 60);

int n, m;
int h[MAXN];
vector<pair<int, int>> g[MAXN];
long long dp[1 << MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
        g[i].clear();
    }

    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        if (h[u] >= h[v]) {
            g[u].push_back({v, w});
        }
        if (h[v] >= h[u]) {
            g[v].push_back({u, w});
        }
    }

    int max_mask = 1 << n;
    for (int i = 0; i < max_mask; i++) {
        dp[i] = INF;
    }
    dp[1 << 0] = 0;

    int best_cnt = 1;
    long long best_sum = 0;

    for (int mask = 0; mask < max_mask; mask++) {
        if (dp[mask] == INF) {
            continue;
        }

        int cnt = __builtin_popcount((unsigned)mask);
        if (cnt > best_cnt || (cnt == best_cnt && dp[mask] < best_sum)) {
            best_cnt = cnt;
            best_sum = dp[mask];
        }

        for (int u = 1; u <= n; u++) {
            if (((mask >> (u - 1)) & 1) == 0) {
                continue;
            }
            for (pair<int, int> e : g[u]) {
                int v = e.first;
                int w = e.second;
                if ((mask >> (v - 1)) & 1) {
                    continue;
                }
                int next_mask = mask | (1 << (v - 1));
                dp[next_mask] = min(dp[next_mask], dp[mask] + w);
            }
        }
    }

    cout << best_cnt << ' ' << best_sum << '\n';

    return 0;
}

暴力把“已经访问了哪些景点”做成集合 DP：

  • 从集合里的任意一个景点出发
  • 沿一条允许方向的边去访问一个新景点
  • 代价加上这条边长

这个模型完全贴题，但 n=10^5 时当然不可能做集合状态。

关键观察分两步。

第一步：最多能经过多少个景点，其实就是从 1 号点在有向图里能到达的点数。

因为有时间胶囊存在，一旦某个点被到达，它以后就一直可以作为新的出发点。 所以只要一个点在有向可达范围里，就总能在某个时刻被访问到。

第二步：在这些可达点里，如何让总代价最小？

假设已经知道哪些点可达。把所有这些点单独拿出来看。

如果一条边连接 u,v，那么真正有用的信息是它能把“较高处的一部分点”和“较低处的一部分点”连接起来。 设这条边两端高度较小者为 low = min(h[u], h[v])。

要想访问所有高度不小于 low 的可达点，这条边是否应当被选，只取决于：

  1. 它能不能把当前两个连通块接起来
  2. 在同样能接起来的边里，它是不是更短

于是可以把所有可达点之间的边按下面顺序排序：

  1. min(h[u],h[v]) 从大到小
  2. 边长 从小到大

然后做一遍 Kruskal。

直观理解：

  • 我们先处理“较高层”的连通需求
  • 再逐层往更低处放开
  • 在同一层里，优先选更短的边

这样选出来的树，既不会减少可达景点数量，又能把总代价压到最小。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int MAXM = 1000005;

struct Edge {
    int u, v, w;
} edges[MAXM];

struct SortEdge {
    int u, v, w, low_h;

    bool operator<(const SortEdge &other) const {
        if (low_h != other.low_h) {
            return low_h > other.low_h;
        }
        return w < other.w;
    }
};

int n, m;
int h[MAXN];
vector<pair<int, int>> g[MAXN];
bool reachable[MAXN];
int fa[MAXN];

void dfs(int start) {
    stack<int> st;
    st.push(start);
    reachable[start] = true;

    while (!st.empty()) {
        int u = st.top();
        st.pop();

        for (pair<int, int> e : g[u]) {
            int v = e.first;
            if (reachable[v]) {
                continue;
            }
            reachable[v] = true;
            st.push(v);
        }
    }
}

void init_dsu() {
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
}

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

bool unite(int x, int y) {
    x = find_root(x);
    y = find_root(y);
    if (x == y) {
        return false;
    }
    fa[x] = y;
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
    }

    vector<SortEdge> cand;
    for (int i = 1; i <= m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;

        int u = edges[i].u;
        int v = edges[i].v;
        int w = edges[i].w;

        if (h[u] >= h[v]) {
            g[u].push_back({v, w});
        }
        if (h[v] >= h[u]) {
            g[v].push_back({u, w});
        }
    }

    dfs(1);

    int reachable_cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (reachable[i]) {
            reachable_cnt++;
        }
    }

    for (int i = 1; i <= m; i++) {
        int u = edges[i].u;
        int v = edges[i].v;
        int w = edges[i].w;
        if (!reachable[u] || !reachable[v]) {
            continue;
        }
        cand.push_back({u, v, w, min(h[u], h[v])});
    }

    sort(cand.begin(), cand.end());

    init_dsu();
    long long answer = 0;
    int used = 0;

    for (SortEdge e : cand) {
        if (!unite(e.u, e.v)) {
            continue;
        }
        answer += e.w;
        used++;
        if (used == reachable_cnt - 1) {
            break;
        }
    }

    cout << reachable_cnt << ' ' << answer << '\n';

    return 0;
}

复杂度

设点数为 n，边数为 m。

  • 先做一次从 1 出发的可达性搜索：O(n+m)O(n+m)
  • 再把可达边排序并做 Kruskal：O(mlogm)O(m log m)

总时间复杂度 O(mlogm)O(m log m)，空间复杂度 O(n+m)O(n+m)。

总结

这题表面像“带回溯的搜索”，但时间胶囊其实把问题变成了“访问集合不断扩张”。先求出从 1 可达的最大景点集合，再在这个集合上做一棵特殊顺序的最小生成树，就是整题的核心。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

一图流解析