P10199 题解

· · 题解

等概率是骗人的，最晚到达时间必定为其某个入边的 R_i，而可以通行的条件则是出边的区间覆盖入边的区间。

先来考虑对于一个中转点，怎么处理他的入边与出边。首先找到每条可以经过的入边的 L_i,R_i，对于每条出边，我们要找到所有的 i 使得 O_i,C_i 使得该区间包含入边里的某个区间。容易想到对左端点做扫描线，维护入边中左端点 \ge l 的最小右端点 r，那么出边中左端点 =l 且右端点 \ge r 的都满足条件。之后更新这些出边对应的点的答案。

可以发现，这个做法可以动态插入入边。对每个左端点单独开一个堆，枚举时不断弹出右端点最大的来更新即可。

考虑用广搜不断对这张图进行“松弛”。若当前搜到点 u，其连向的点 v 新增了一条可行入边，我们就对 v 进行上述的插入操作，然后将所有它新增的可行出边加入 v 的“代办列表”。当搜到 v 时，再由 v 对其“代办列表”的点继续进行“松弛”。

该做法的正确性是显然的，因为一个点的答案和他上一个点的答案无关。而只有在一个点多了能更新的出边，才会继续进行更新，所以总更新次数为 O(m)，时间复杂度为 O((\max O,L)m+m\log m)。

AC 代码

#include <bits/stdc++.h>

// using fread
#define INPUT_OPTIMIZE

// using fwrite
// #define OUTPUT_OPTIMIZE

namespace IO {
//  by R_i.
}

using namespace IO;

using namespace std;

typedef long long ll;

const int MAXN = 5e5 + 10;

struct node {
    int v, a, b, c, d, id;
    bool operator < (const node &rhs) const { return b < rhs.b; }
}; vector<node> g[MAXN]; set<node> ts[MAXN];

int t[MAXN]; queue<int> q;

priority_queue<node> y[MAXN][21];

inline 
void upd(int u, int x) {
    if (!t[u]) t[u] = x;
    else t[u] = min(t[u], x);
}

inline 
void insert(int u, node p) {
    for (int i = p.c; i; i--) {
        for (; !y[u][i].empty() && y[u][i].top().b >= p.d;) {
            node tmp = y[u][i].top();
            q.push(tmp.v), ts[u].insert(tmp);
            upd(tmp.v, tmp.d), y[u][i].pop();
        }
    }
}

int n, m;

void solve(int S) {
    for (int i = 1; i <= n; i++) {
        for (node x : g[i]) y[i][x.a].push(x);
    }
    for (node x : g[S]) {
        upd(x.v, x.d);
        q.push(x.v), insert(x.v, x);
    }
    for (int u; !q.empty();) {
        u = q.front(), q.pop();
        if (!t[u]) continue;
        for (node p : ts[u]) insert(p.v, p);
        ts[u].clear();
    }
}

int S, ans;

int main() {
    read(n, m, S);
    for (int i = 1, u, v, a, b, c, d; i <= m; i++) {
        read(u, v, a, b, c, d);
        g[u].push_back({ v, a, b, c, d, i });
    }
    solve(S);
    for (int i = 1; i <= n; i++) ans = max(ans, t[i]);
    write(ans);
}

1e7 个 priority_queue 不会 MLE，1e6 个 deque 会 MLE，怎么回事呢？