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;
}