题意
\(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\)点及其相关的边后,在途中的一个割中找最大值。由于图是拓扑序的,所以,我们只要把某割点的入边拿掉后、拓扑秩在自己前或相同的点出边都加入到一个堆里,那么堆中就可以形成一个割!这个比较显然。
#includeusing 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 (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;}