洛谷 P4286 [SHOI2008] 安全的航线

题目描述

在一个无向连通图中，给定两个不同的顶点s和t，要求找到一条从s到t的路径，使得路径上的每一条边都不是桥（即该路径是安全的航线）。如果不存在这样的路径，则输出-1；如果存在多条，则输出路径的最短长度。

输入格式

第一行包含两个整数n和m，分别表示图的顶点数和边数。 接下来m行，每行包含两个整数u和v，表示一条无向边。 最后一行包含两个整数s和t。

输出格式

如果存在安全的航线，输出最短路径的长度；否则输出-1。

思路分析

本题可采用递归分治（树的分治）思想解决：

1. 首先，通过Tarjan算法找出图中所有桥边，将图分解为双连通分量。
2. 安全航线必须位于双连通分量内部，因此需在每个双连通分量中寻找s到t的路径。
3. 递归分治的核心步骤：
   • 选择一个分治中心（如某个顶点），计算经过该中心的安全路径。
   • 递归处理分治中心的各个子树，避免重复计算。
   • 合并子问题结果，得到最终答案。

代码实现

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN = 10005;
const int INF = 1e9;

vector<int> adj[MAXN];
int n, m, s, t;
bool is_bridge[MAXN*2];
int disc[MAXN], low[MAXN], timeStamp;
vector<int> comp_nodes[MAXN];
int comp_cnt;
int ans;

// Tarjan算法找桥
void tarjan(int u, int parent) {
    disc[u] = low[u] = ++timeStamp;
    for (int i = 0; i < adj[u].size(); ++i) {
        int v = adj[u][i];
        if (v == parent) continue;
        if (!disc[v]) {
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] > disc[u]) {
                is_bridge[i] = true;
                is_bridge[find(adj[v].begin(), adj[v].end(), u) - adj[v].begin()] = true;
            }
        } else {
            low[u] = min(low[u], disc[v]);
        }
    }
}

// BFS寻找最短路径
int bfs(const vector<int>& nodes, int start, int end) {
    vector<int> dist(n+1, INF);
    queue<int> q;
    dist[start] = 0;
    q.push(start);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (u == end) return dist[u];
        for (int i = 0; i < adj[u].size(); ++i) {
            int v = adj[u][i];
            if (dist[v] == INF && !is_bridge[i]) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return -1;
}

// 分治函数
void solve(const vector<int>& nodes) {
    if (nodes.empty()) return;
    int center = nodes[0]; // 选择第一个节点作为分治中心
    vector<int> sub_nodes;
    for (int u : nodes) {
        if (u != center) sub_nodes.push_back(u);
    }
    // 计算经过center的安全路径
    for (int u : sub_nodes) {
        int d = bfs(nodes, u, center);
        if (d != -1) ans = min(ans, d);
    }
    // 递归处理子树
    for (int u : sub_nodes) {
        solve(sub_nodes);
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    cin >> s >> t;
    
    // 找桥
    memset(disc, 0, sizeof(disc));
    memset(low, 0, sizeof(low));
    timeStamp = 0;
    tarjan(s, -1);
    
    // 分治求解
    ans = INF;
    vector<int> all_nodes;
    for (int i = 1; i <= n; ++i) all_nodes.push_back(i);
    solve(all_nodes);
    
    if (ans == INF) cout << -1 << endl;
    else cout << ans << endl;
    
    return 0;
}

【题解】洛谷 P4286 [SHOI2008] 安全的航线 [递归分治]-CSDN博客