BZOJ3832: [Poi2014]Rally(拓撲排序 堆)

題意

題目鏈接

Sol

最直觀的思路是求出刪除每個點後的最長路，我們考慮這玩意兒怎麼求

設\(f[i]\)表示以\(i\)結尾的最長路長度，\(g[i]\)表示以\(i\)開始的最長路長度

根據DAG的性質，顯然我們刪除一個點後，整個集合會被分成兩部分：拓撲序小於/大於當前點

那麼此時的最長路一定可以通過計算連接著兩個集合的邊\((u, v)\)的\(f(u) + f(v) +1\)得到

這樣的話我們可以直接維護邊集，在統計每個點的答案的時候首先刪掉入邊的貢獻統計答案，統計完後再加入出邊的貢獻

顯然線段樹可以維護，其實堆也可以維護，具體見代碼(抄襲自yyb大佬)

#include<bits/stdc++.h>
#define chmax(x, y) (x = (x > y ? x : y))
#define chmin(x, y) (x = (x < y ? x : y))
using namespace std;
const int MAXN = 1e6 + 10, INF = 1e9 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M, a1 = INF, a2;
class MyPriorityQueue {
    public: 
        priority_queue<int> q1, q2;
        void push(int x) {
            q1.push(x);
        }
        int pop(int x) {
            q2.push(x);
        }
        bool empty() {
            while(!q2.empty() && (q1.top() == q2.top())) q1.pop(), q2.pop();
            return q1.size() == 0;
        }
        int top() {
            return empty() ? INF : q1.top();
        }   
};
MyPriorityQueue Q;
struct Graph {
    vector<int> v[MAXN];
    int f[MAXN], inder[MAXN], id[MAXN], tot;
    Graph() {
        tot = 0;
    }
    void AddEdge(int x, int y) {
        v[x].push_back(y); inder[y]++;
    }
    void Topsort() {
        queue<int> q;
        for(int i = 1; i <= N; i++) if(!inder[i]) q.push(i);
        while(!q.empty()) {
            int p = q.front(); q.pop(); id[++tot] = p;
            for(int i = 0; i < v[p].size(); i++) {
                int to = v[p][i]; chmax(f[to], f[p] + 1);
                if(!(--inder[to])) q.push(to);
            }
        }
    }
};
Graph Gs, Gt;
int main() {
    N = read(); M = read();
    for(int i = 1; i <= M; i++) {
        int x = read(), y = read();
        Gs.AddEdge(x, y); Gt.AddEdge(y, x);
    }
    Gs.Topsort(); Gt.Topsort();
    for(int i = 1; i <= N; i++) Q.push(Gt.f[i]);
    for(int t = 1; t <= N; t++) {
        int x = Gs.id[t]; Q.pop(Gt.f[x]);
        for(int i = 0; i < Gt.v[x].size(); i++) {
            int to = Gt.v[x][i];
            Q.pop(Gs.f[to] + Gt.f[x] + 1);
        }
        int now = Q.top(); Q.push(Gs.f[x]);
        if(now < a1) a1 = now, a2 = x;
        for(int i = 0; i < Gs.v[x].size(); i++) {
            int to = Gs.v[x][i];
            Q.push(Gs.f[x] + Gt.f[to] + 1);
        }
    }
    printf("%d %d\n", a2, a1);
    return 0;
}