P3573 [POI2014]RAJ-Rally 题解

非常好题目，爱来自 xc。

• 看到有向无环图，想到拓扑序。通过拓扑序，可以轻松求出以每个点为起点的最长路 \(disS\)与每个点为终点的最长路 \(disF\)。

• 如何求总共的最长路？在 \(disS,disF,disS_u + 1 + disF_v((u,v)\in E)\) 中取最大值即可。注意最后一项，表示将连边的二点值相加。

• 如何处理删点？删掉一个点后，有一些点的 \(disS\) 不会变，有一些点的 \(disT\) 不会变。我们不妨把这两类点进行分组，得到组 \(A\) 和组 \(B\)。

• 为什么要进行分组？因为第三类取值 \(disS_u + 1 + disF_v\) 只会在两组间连边产生，且 \(u\in A,v\in B\)。因为只有此时 \(disS_u\) 和 \(disF_v\) 才不会受删点影响。

• 发现 \(A\) 与 \(B\) 的单次加减是简单的，于是我们考虑递推每一个答案。

• 若当前求的点为 \(u\)，不妨认为在这之后我们会将 \(u\) 从 \(B\) 中加入 \(A\) 中。那么我们要删除 \(disF_u\) 以及所有包含 \(disF_u\) 的第三类值，同时加入 \(disS_u\) 与所有包含 \(disS_u\) 的第三类值。此时最大值就是答案。

• 注意到上述过程需要满足当加入 \(u\) 时，所有 \(u\) 连向的点还在 \(B\) 内。因此递推的顺序是翻转的拓扑序。

• 删除加入求最大值可以用优先队列解决，由于一次就写过了不知道有什么需要注意的点。

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;

template<typename T> bool chkmax(T &a, T b) { return a < b ? (a = b, 1) : 0; }
template<typename T> bool chkmin(T &a, T b) { return a > b ? (a = b, 1) : 0; }

int n, m;
namespace Graph {
    template<const int M> 
    struct graph {
        int st[M], nx[M << 1], to[M << 1], cnt;
        void add(int u, int v) { to[++cnt] = v;nx[cnt] = st[u];st[u] = cnt; }
    };
    #define go(g, u, v) for (int i = g.st[u], v = g.to[i]; i; i = g.nx[i], v = g.to[i])
    graph<N << 1> g, ig;

    int in[N], out[N], hisI[N], hisO[N];
    bool vis[N];
    void add(int u, int v) {
        g.add(u, v);
        ig.add(v, u);
        vis[u] = vis[v] = true;
        ++hisI[v];++hisO[u];
        ++in[v];++in[u];
    }
    void init() {
        for (int i = 1; i <= n; ++i) in[i] = hisI[i], out[i] = hisO[i];
    }

    vector<int> A, B;
    int disS[N], disF[N];
    void findS() {
        init();
        queue<int> q;
        for (int i = 1; i <= n; ++i) if (out[i] == 0 && vis[i] == true) q.push(i);
        while (!q.empty()) {
            int u = q.front();q.pop();
            A.push_back(u);
            go (ig, u, v) {
                if (--out[v] == 0) q.push(v);
                chkmax(disS[v], disS[u] + 1);
            }
        } 
        for (int i = A.size() - 1; i >= 0; --i) B.push_back(A[i]);
    }
    void findF() {
        init();
        queue<int> q;
        for (int i = 1; i <= n; ++i) if (in[i] == 0) q.push(i);
        while (!q.empty()) {
            int u = q.front();q.pop();
            go (g, u, v) {
                if (--in[v] == 0) q.push(v);
                chkmax(disF[v], disF[u] + 1);
            }
        }
    }

    struct Pqueue {
        priority_queue<int> q, del;
        void push(int x) { q.push(x); }
        void pop(int x) { del.push(x); }
        int top() { 
            while (!del.empty() && q.top() == del.top()) q.pop(), del.pop();
            return q.top();
        }
        int size() {
            while (!del.empty() && q.top() == del.top()) q.pop(), del.pop();
            return q.size();
        } 
    }Q;

    pair<int, int> work() {
        int ans = 2147483647, id = 0;
        for (int i = 1; i <= n; ++i) Q.push(disS[i]);
        for (auto u : B) {
            Q.pop(disS[u]);
            go (ig, u, v) Q.pop(disF[v] + 1 + disS[u]);
            if (chkmin(ans, Q.top())) id = u;
            go (g, u, v) Q.push(disF[u] + 1 + disS[v]);
            Q.push(disF[u]);
        }
        return make_pair(id, ans);
    }
}
int main() {
    freopen("text.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    cin >> n >> m;
    for (int i = 1, u, v; i <= m; ++i) {
        cin >> u >> v;
        Graph::add(u, v);
    }

    Graph::findS();
    Graph::findF();

    pair<int, int> ans = Graph::work();
    cout << ans.first << ' ' << ans.second << endl;

    return 0;
}