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

[POI2014]RAJ-Rally

程序员文章站 2022-07-13 12:35:02
...

Description

Luogu3573

Solution

神仙题。

删掉一个点后,最长路一共就三种情况:两个端点的拓扑序都比它大/小/一大一小。然后按拓扑序枚举删哪个点。用堆或线段树维护一下三种情况的最长路就好了。为了方便,先预处理出来以每个点为开头或结尾的最长路。

Code

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>

const int N = 500010 * 4;

int n, m, f[N], g[N], ind[N], outd[N];
std::vector<int> G[N], F[N];
int q[N][2], qhd, qtl, vis[N];

struct SegmentTree {
    int val[N], sz[N];
    void Add(int o, int l, int r, int v) {
        sz[o]++;
        if (l == r) return;
        int mid = (l + r) >> 1;
        if (v <= mid)
            Add(o << 1, l, mid, v);
        else
            Add(o << 1 | 1, mid + 1, r, v);
    }
    void Del(int o, int l, int r, int v) {
        if (sz[o] == 0) puts("Error");
        sz[o]--;
        if (l == r) return;
        int mid = (l + r) >> 1;
        if (v <= mid)
            Del(o << 1, l, mid, v);
        else
            Del(o << 1 | 1, mid + 1, r, v);
    }
    int Max(int o, int l, int r) {
        if (l == r) return l;
        if (sz[o << 1 | 1])
            return Max(o << 1 | 1, ((l + r) >> 1) + 1, r);
        else
            return Max(o << 1, l, (l + r) >> 1);
    }
    void Add(int x) { Add(1, 1, n, x); }
    void Del(int x) { Del(1, 1, n, x); }
    int Max() { return Max(1, 1, n); }
} Tr;

int main() {
    n = read(), m = read();
    for (int i = 1, x, y; i <= m; ++i) {
        x = read(), y = read();
        G[x].push_back(y);
        F[y].push_back(x);
        ind[y]++;
        outd[x]++;
    }
    //---正向拓排---//
    qhd = qtl = 0;
    int fl1 = 0;
    for (int i = 1; i <= n; ++i)
        if (ind[i] == 0) q[qtl++][0] = i;
    if (qtl == 1) fl1 = 1;
    while (qhd < qtl) {
        int x = q[qhd++][0];
        for (int i : G[x]) {
            g[i] = std::max(g[i], g[x] + 1);
            if (--ind[i] == 0) q[qtl++][0] = i;
        }
    }
    //---反向拓排---//
    qhd = qtl = 0;
    for (int i = 1; i <= n; ++i)
        if (outd[i] == 0) q[qtl++][1] = i;
    while (qhd < qtl) {
        int x = q[qhd++][1];
        for (int i : F[x]) {
            f[i] = std::max(f[i], f[x] + 1);
            if (--outd[i] == 0) q[qtl++][1] = i;
        }
    }
    //---初始化---//
    int ans = 0x3f3f3f3f, ans2 = -1;
    for (int i = 1; i <= n; ++i) Tr.Add(f[i]);
    //---开始枚举删哪个点---//
    for (int i = 0; i < n; ++i) {
            int &x = q[i][0];
            Tr.Del(f[x]);
            for (int j : F[x])
                if (vis[j]) {
                    Tr.Del(g[j] + f[x] + 1);
                }
            int tmp = Tr.Max();
            Tr.Add(g[x]);
            if (tmp < ans) ans = tmp, ans2 = x;
            for (int j : G[x])
                if (!vis[j]) {
                    Tr.Add(g[x] + f[j] + 1);
                }
            vis[x] = 1; // mark:一开始这里忘了写……
        }
    printf("%d %d\n", ans2, ans);
    return 0;
}

转载于:https://www.cnblogs.com/wyxwyx/p/poi2014raj.html