题意
\(n(2 \le n \le 500000)\)个点\(m(1 \le m \le 1000000)\)条边的有向无环图，找到一个点，使得删掉这个点后剩余图中的最长路径最短。
分析
神题不会做。
题解
首先我们新建个源\(s\)和汇\(t\)，连边\(s->i, i->t\)，最远距离分别为\(d[i, 0]\)和\(d[i, 1]\)，则一个图中的最长链就是\(max(d[u, 0]+d[v, 1]-1, \exists edge(u, v))\)，再由于图中任意一个\(s-t\)割都会有最长链的边，那么问题就转化为去掉\(x\)点及其相关的边后，在途中的一个割中找最大值。由于图是拓扑序的，所以，我们只要把某割点的入边拿掉后、拓扑秩在自己前或相同的点出边都加入到一个堆里，那么堆中就可以形成一个割！这个比较显然。
#include <bits/stdc++.h>
using namespace std;
inline int getint() {
int x=0;
char c=getchar();
for(; c<'0'||c>'9'; c=getchar());
for(; c>='0'&&c<='9'; x=x*10+c-'0', c=getchar());
return x;
}
const int N=500005;
int q[N], in[N], d[N][2], n, cnt1, cnt2, ihead1[N], ihead2[N], sz[N<<2];
struct E {
int next, to;
}e1[N<<2], e2[N<<2];
void add(int x, int y) {
e1[++cnt1]=(E){ihead1[x], y}; ihead1[x]=cnt1;
e2[++cnt2]=(E){ihead2[y], x}; ihead2[y]=cnt2;
++in[y];
}
void ins(int p, int d, int l=0, int r=n, int x=1) {
sz[x]+=d;
if(l==r) {
return;
}
int mid=(l+r)>>1;
p<=mid?ins(p, d, l, mid, x<<1):ins(p, d, mid+1, r, x<<1|1);
}
int ask(int l=0, int r=n, int x=1) {
if(l==r) {
return l;
}
int mid=(l+r)>>1, ls=x<<1, rs=ls|1;
return sz[rs]?ask(mid+1, r, rs):ask(l, mid, ls);
}
int main() {
n=getint();
int m=getint(), fr=0, ta=0;
for(int i=1; i<=m; ++i) {
int x=getint(), y=getint();
add(x, y);
}
for(int i=1; i<=n; ++i) {
if(!in[i]) {
q[ta++]=i;
}
}
while(fr!=ta) {
int x=q[fr++];
for(int i=ihead1[x]; i; i=e1[i].next) {
if(!--in[e1[i].to]) {
q[ta++]=e1[i].to;
}
}
}
for(int j=0; j<n; ++j) {
for(int x=q[j], i=ihead2[x]; i; i=e2[i].next) {
d[x][0]=max(d[x][0], d[e2[i].to][0]+1);
}
for(int x=q[n-j-1], i=ihead1[x]; i; i=e1[i].next) {
d[x][1]=max(d[x][1], d[e1[i].to][1]+1);
}
}
for(int i=1, S=n+1, T=S+1; i<=n; ++i) {
add(S, i);
add(i, T);
ins(d[i][1], 1);
}
d[n+1][0]=-1;
d[n+2][1]=-1;
int ans1=-1, ans2=n+1;
for(int j=0; j<n; ++j) {
int x=q[j], t;
for(int i=ihead2[x]; i; i=e2[i].next) {
ins(d[e2[i].to][0]+d[x][1]+1, -1);
}
if(ans2>(t=ask())) {
ans1=x;
ans2=t;
}
for(int i=ihead1[x]; i; i=e1[i].next) {
ins(d[x][0]+d[e1[i].to][1]+1, 1);
}
}
printf("%d %d\n", ans1, ans2);
return 0;
}