题目链接：传送门
找到一个点使删除这个点后图中的最长路最短
DAG——->拓扑
好吧第一步就挂掉了
标签线段树主席树？
好像线段树确实也能做
设$f[i]$表示到达$i$的最长路
$ff[i]$表示从$i$出发的最长路
一条最长路（起点$fr$,终点$ca$）一定等于 $f[fr]+ff[ca]+1$
所以做法就出来了
枚举每个点用一个堆来维护每个节点的贡献
可以删去和插入和询问最大值
记着最后把那个+1减掉1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97/**
* @Date: 2019-04-01T16:39:57+08:00
* @Last modified time: 2019-04-01T16:39:58+08:00
*/
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;
}