欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[POI 2014]RAJ-Rally

程序员文章站 2022-07-13 12:30:32
...

Description

题库链接

给定一个 \(N\) 个点 \(M\) 条边的有向无环图,每条边长度都是 \(1\)。请找到一个点,使得删掉这个点后剩余的图中的最长路径最短。

\(1\leq N\leq 500 000,1\leq M\leq 1 000 000\)

Solution

比较神...

值得注意的是,对于一张 \(\text{DAG}\) 的拓扑序,任意从中截断那么前一部分以及后一部分的点都是连续的。

考虑按拓扑序来做,我们需要维护的就只是左边一部分内的最长路,以及右边一部分内的最长路。

除此之外还要维护经过被“割开”边的最长路。

对于删除一个点,我们需要做的就是将“割边”转移,维护上述需要维护的信息。

可以用可删除的堆来实现,不过考虑到空间的花销,用权值线段树可以实现同样的功能。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 500000+5, inf = ~0u>>1;

int n, m, u, v, c1[N], c2[N], q[N];
struct graph {
    struct tt {int to, next; }edge[N<<1];
    int path[N], top, in[N];
    void add(int u, int v) {edge[++top] = (tt){v, path[u]}, path[u] = top, ++in[v]; }
    void topsort(int* c, int flag) {
        queue<int>Q; int cnt = 0;
        for (int i = 1; i <= n; i++) if (!in[i]) Q.push(i);
        while (!Q.empty()) {
            int u = Q.front(); Q.pop(); if (flag) q[++cnt] = u;
            for (int i = path[u]; i; i = edge[i].next) {
                --in[edge[i].to]; c[edge[i].to] = max(c[edge[i].to], c[u]+1);
                if (in[edge[i].to] == 0) Q.push(edge[i].to);
            }
        }
    }
}g1, g2;
struct Segment_tree {
#define lr(o) (o<<1)
#define rr(o) (o<<1|1)
    int mx[N<<2], cnt[N<<2];
    Segment_tree() {memset(mx, -1, sizeof(mx)); }
    void modify(int o, int l, int r, int loc, int key) {
        if (l == r) {
            cnt[o] += key;
            if (cnt[o] == 1) mx[o] = l;
            else if (cnt[o] == 0) mx[o] = -1;
            return;
        }
        int mid = (l+r)>>1;
        if (loc <= mid) modify(lr(o), l, mid, loc, key);
        else modify(rr(o), mid+1, r, loc, key);
        mx[o] = max(mx[lr(o)], mx[rr(o)]);
    }
}T;

void work() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &u, &v); g1.add(u, v), g2.add(v, u);
    }
    g1.topsort(c1, 1), g2.topsort(c2, 0);
    int ans = inf, pos;
    for (int i = 1; i <= n; i++) T.modify(1, 0, n, c2[i], 1);
    for (int id = 1; id <= n; id++) {
        int u = q[id];
        for (int i = g2.path[u]; i; i = g2.edge[i].next)
            T.modify(1, 0, n, c2[u]+c1[g2.edge[i].to]+1, -1);
        T.modify(1, 0, n, c2[u], -1);
        if (T.mx[1] < ans) ans = T.mx[1], pos = u;
        for (int i = g1.path[u]; i; i = g1.edge[i].next)
            T.modify(1, 0, n, c1[u]+c2[g1.edge[i].to]+1, 1);
        T.modify(1, 0, n, c1[u], 1);
    }
    printf("%d %d\n", pos, ans);
}
int main() {work(); return 0; }