[ABC218F] Blocked Roads 题解

· · 题解

[ABC218F] Blocked Roads 题解

Intro

这里提供一种神秘做法，目前题解区里还没有出现。

Solution

先想暴力，枚举每条边，每次 bfs，总共 O(nm+m^2) 显然不行，我们考虑将每次求答案的 O(n+m) 复杂度优化成 O(n)。

我们在一开始的时候分别对原图的正反图以 1 和 n 为起点做 bfs，这样得到 dis 和 dis1 分别是正图上以 1 为起点和反图上以 n 为起点的单源最短路；同时，我们求一个 flag_{i,k} 和 flag1_{i,k} 表示从起点到 i 的最短路是否经过第 k 条边。得到这两个数组后我们枚举每条边 k，然后枚举每个点 i，若 [(\lnot{flag_{i,k}})\And(\lnot{flag1_{i,k}})] 则用 dis_i+dis1_i 更新答案，最后输出即可。

关于证明复杂度就简单讲一下。bfs 在松弛 id 号边 (u,v) 时 flag_{v,k}\gets flag_{u,k}，flag_{v,id}\gets 1，由于边权为 1 和 bfs 的性质每一个点只会被更新一次，每次更新 O(m)，bfs 的复杂度就是 O(nm)。而正确性的证明我们可以尝试感性理解。你可能考虑到如下图的情景：

我们在枚举边 (3,6) 时枚举到点 6，因为我们的 flag 取哪条边作为最短路是不确定的，所以若 [flag_{6,E(3,6)}]=1，那么点 6 就不会对答案造成贡献，但是点 5 是会造成贡献的，所以答案仍然正确。具体的理解我们可以想，如果一个点从起点开始有多条长度相同的最短路，并且我们枚举到的边正好就是我们 flag 标记的这条最短路，那在我们没有选择的那几条最短路中必定有点也能造成贡献。

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 410;
int n, m, d[N], d1[N];
bool flag[N][N * N], flag1[N][N * N];
pair<int, int> e[N * N];
struct node {
    int v, id;
};
vector<node> g[N], g1[N];
void bfs() {
    queue<int> q;
    q.push(1); memset(d, 0x3f, sizeof(d)); d[1] = 0;
    while(!q.empty()) {
        int u = q.front(); q.pop();
        for(auto it : g[u]) {
            int v = it.v, id = it.id;
            if(d[v] > d[u] + 1) {
                d[v] = d[u] + 1;
                for(int i = 1; i <= m; i++) flag[v][i] = flag[u][i];
                flag[v][id] = true;
                q.push(v);
            }
        }
    }
}
void bfs1() {
    queue<int> q;
    q.push(n); memset(d1, 0x3f, sizeof(d1)); d1[n] = 0;
    while(!q.empty()) {
        int u = q.front(); q.pop();
        for(auto it : g1[u]) {
            int v = it.v, id = it.id;
            if(d1[v] > d1[u] + 1) {
                d1[v] = d1[u] + 1;
                for(int i = 1; i <= m; i++) flag1[v][i] = flag1[u][i];
                flag1[v][id] = true;
                q.push(v);
            }
        }
    }
}
int main() {
    cin >> n >> m;
    for(int i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        g[u].push_back({v, i}); g1[v].push_back({u, i}); 
        e[i] = {u, v};
    }
    bfs(); bfs1();
    for(int i = 1; i <= m; i++) {
        int ans = 2e9;
        for(int j = 1; j <= n; j++) {
            if(!flag[j][i] && !flag1[j][i]) ans = min(ans, d[j] + d1[j]);
        }
        if(ans < 1e9) cout << ans << '\n';
        else cout << "-1\n";
    }
    return 0;
}