[POI2014]RAJ-Rally

题目链接：传送门

找到一个点使删除这个点后图中的最长路最短
DAG——->拓扑
好吧第一步就挂掉了
标签线段树主席树？
好像线段树确实也能做
设$f[i]$表示到达$i$的最长路
$ff[i]$表示从$i$出发的最长路
一条最长路（起点$fr$,终点$ca$）一定等于 $f[fr]+ff[ca]+1$
所以做法就出来了
枚举每个点用一个堆来维护每个节点的贡献
可以删去和插入和询问最大值
记着最后把那个+1减掉

/**
 * @Date:   2019-04-01T16:39:57+08:00
 * @Last modified time: 2019-04-01T16:39:58+08:00
 */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define A 1000010
#define B 2010

using namespace std;
typedef long long ll;
struct node {
    int next, to;
}e[A];
int heads[A], num, headt[A];
void add(int fr, int to, int head[]) {
    e[++num].next = head[fr];
    e[num].to = to;
    head[fr] = num;
}
struct heap {
    priority_queue<int> ins, del;
    void insert(int x) {ins.push(x);}
    void deletee(int x) {del.push(x);}
    int top() {
        while (!del.empty() and !ins.empty() and del.top() == ins.top()) {del.pop(); ins.pop();}
        return ins.top();
    }
}hp;
int n, m, a, b, in[A], tail, Q[A], f[A], ff[A], ans = 0x3f3f3f3f, pos;
void topo() {
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (!in[i]) q.push(i), Q[++tail] = i;
    while (!q.empty()) {
        int fr = q.front(); q.pop();
        for (int i = heads[fr]; i; i = e[i].next) {
            int ca = e[i].to;
            if (!--in[ca]) q.push(ca), Q[++tail] = ca;
        }
    }
}

int main(int argc, char const *argv[]) {
	cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> a >> b;
        add(a, b, heads); add(b, a, headt);
        in[b]++;
    }
    topo();
    fill(f + 1, f + n + 1, 1); //到达i的最长路径
    fill(ff + 1, ff + n + 1, 1); //从i出发的最长路径
    for (int j = 1; j <= n; j++) {
        int fr = Q[j];
        for (int i = heads[fr]; i; i = e[i].next) {
            int ca = e[i].to;
            f[ca] = max(f[ca], f[fr] + 1);
        }
    }
    for (int j = n; j >= 1; j--) {
        int fr = Q[j];
        for (int i = headt[fr]; i; i = e[i].next) {
            int ca = e[i].to;
            ff[ca] = max(ff[ca], ff[fr] + 1);
        }
    }
    for (int i = 1; i <= n; i++) hp.insert(ff[i]);
    for (int j = 1; j <= n; j++) {
        int fr = Q[j];
        for (int i = headt[fr]; i; i = e[i].next) {
            int ca = e[i].to;
            hp.deletee(f[ca] + ff[fr]);
        }
        hp.deletee(ff[fr]);
        if (ans > hp.top() - 1) {
            ans = hp.top() - 1;
            pos = fr;
        }
        for (int i = heads[fr]; i; i = e[i].next) {
            int ca = e[i].to;
            hp.insert(f[fr] + ff[ca]);
        }
        hp.insert(f[fr]);
    }
    cout << pos << " " << ans << endl;
}