[NOIP 2014 提高组] 寻找道路

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

先在反图上从终点标记可达点，再筛出所有安全点，最后只在安全子图中做 BFS 最短路。

OJ: luogu

题目 ID: P2296

难度:普及+/提高

标签:图论bfs最短路noip

日期: 2026-06-20 17:13

目录

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

题意

给一张有向图，所有边长度都是 1，要求从起点 s 走到终点 t。

但答案路径还必须满足一个额外限制：

  • 路径上的每个点，它的所有出边所指向的点，都必须直接或间接能到达终点 t。

在满足这个限制的前提下，求最短路径长度。无解输出 -1。

思路

先看一个可以直接验证想法的朴素解：

cpp
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int n, m;
int s, t;
vector<int> g[MAXN];
vector<int> rg[MAXN];

bool can_reach_t[MAXN];
bool safe_node[MAXN];
int dista[MAXN];

// 暴力做法仍然先按定义筛点，只是直接用 vector 存图，适合小数据阅读。
void mark_can_reach_t() {
    queue<int> q;
    q.push(t);
    can_reach_t[t] = true;

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int i = 0; i < (int)rg[u].size(); i++) {
            int v = rg[u][i];
            if (can_reach_t[v]) continue;
            can_reach_t[v] = true;
            q.push(v);
        }
    }
}

void mark_safe_node() {
    for (int u = 1; u <= n; u++) {
        safe_node[u] = true;
        for (int i = 0; i < (int)g[u].size(); i++) {
            int v = g[u][i];
            if (!can_reach_t[v]) {
                safe_node[u] = false;
                break;
            }
        }
    }
}

int bfs_shortest_path() {
    memset(dista, -1, sizeof(dista));
    if (!safe_node[s] || !safe_node[t]) return -1;

    queue<int> q;
    q.push(s);
    dista[s] = 0;

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        if (u == t) return dista[u];

        for (int i = 0; i < (int)g[u].size(); i++) {
            int v = g[u][i];
            if (!safe_node[v]) continue;
            if (dista[v] != -1) continue;
            dista[v] = dista[u] + 1;
            q.push(v);
        }
    }

    return -1;
}

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

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        rg[v].push_back(u);
    }
    cin >> s >> t;

    mark_can_reach_t();
    mark_safe_node();

    cout << bfs_shortest_path() << '\n';
    return 0;
}

这份代码已经体现了本题的核心结构：先判哪些点能到达 t，再删掉不合法的点，最后求最短路。

关键观察是：题目的额外限制，不是限制“当前走哪条边”，而是限制“路径上的这个点本身是否允许出现”。

所以我们先把点分类。

第一类是“能到达终点的点”。

这个最适合在反图上做：

  • 原图里 u -> v
  • 反图里 v -> u

于是从 t 在反图上 BFS 一遍，所有能被搜到的点，就是原图中能够到达 t 的点。

第二类是“安全点”。

如果一个点 u 存在某条出边 u -> v，而 v 根本到不了 t， 那么 u 就不满足题目要求，不能出现在任何合法路径上。

所以只要扫描每个点的所有出边，就能判断它是不是安全点。

最后只保留安全点，把从不安全点出发或指向不安全点的转移都忽略掉， 再从 s 做一次普通 BFS，第一次到达 t 的距离就是答案。

代码

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

const int MAXN = 10000 + 5;
const int MAXM = 200000 + 5;

int n, m;
int s, t;

int head[MAXN], to[MAXM], nxt[MAXM], edge_cnt;
int rhead[MAXN], rto[MAXM], rnxt[MAXM], redge_cnt;
int out_deg[MAXN];

bool can_reach_t[MAXN]; // 在原图中，这个点能否走到终点 t
bool safe_node[MAXN];   // 这个点的所有出边是否都指向 can_reach_t 的点
int dista[MAXN];

void add_edge(int u, int v) {
    edge_cnt++;
    to[edge_cnt] = v;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;

    redge_cnt++;
    rto[redge_cnt] = u;
    rnxt[redge_cnt] = rhead[v];
    rhead[v] = redge_cnt;

    out_deg[u]++;
}

// 在反图上从 t 开始 BFS，标记哪些点在原图中能够到达 t。
void mark_can_reach_t() {
    queue<int> q;
    q.push(t);
    can_reach_t[t] = true;

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int i = rhead[u]; i != 0; i = rnxt[i]) {
            int v = rto[i];
            if (can_reach_t[v]) continue;
            can_reach_t[v] = true;
            q.push(v);
        }
    }
}

// 题目要求路径上的每个点，其所有出边指向的点都要直接或间接与 t 连通。
// 所以只要某个点存在一条出边通向“坏点”，它自己就不能出现在合法路径上。
void mark_safe_node() {
    for (int u = 1; u <= n; u++) {
        safe_node[u] = true;
        for (int i = head[u]; i != 0; i = nxt[i]) {
            int v = to[i];
            if (!can_reach_t[v]) {
                safe_node[u] = false;
                break;
            }
        }
    }
}

int bfs_shortest_path() {
    memset(dista, -1, sizeof(dista));

    if (!safe_node[s] || !safe_node[t]) return -1;

    queue<int> q;
    q.push(s);
    dista[s] = 0;

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        if (u == t) return dista[u];

        for (int i = head[u]; i != 0; i = nxt[i]) {
            int v = to[i];
            if (!safe_node[v]) continue;
            if (dista[v] != -1) continue;
            dista[v] = dista[u] + 1;
            q.push(v);
        }
    }

    return -1;
}

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

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        add_edge(u, v);
    }
    cin >> s >> t;

    mark_can_reach_t();
    mark_safe_node();

    cout << bfs_shortest_path() << '\n';
    return 0;
}

复杂度

反图 BFS、扫描所有出边、在安全子图上 BFS 都是线性复杂度， 所以总时间复杂度为 O(n+m)O(n + m)，空间复杂度也为 O(n+m)O(n + m)。

总结

这题的重点是先把题面条件翻译成“哪些点允许出现在答案路径上”。

一旦意识到：

  • 先在反图里求“能到终点”
  • 再据此筛掉“不安全点”
  • 最后才做 BFS

整道题就会变成一题很干净的图上预处理加最短路。

一图流解析

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

一图流解析