欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[POI2014] RAJ-Rally

程序员文章站 2022-07-13 12:27:54
...

题目描述

给定一个N个点M条边的有向无环图,每条边长度都是1。

请找到一个点,使得删掉这个点后剩余的图中的最长路径最短。

输入输出格式

输入格式:

 

第一行包含两个正整数N,M(2<=N<=500 000,1<=M<=1 000 000),表示点数、边数。

接下来M行每行包含两个正整数A[i],Bi,表示A[i]到B[i]有一条边。

 

输出格式:

 

包含一行两个整数x,y,用一个空格隔开,x为要删去的点,y为删除x后图中的最长路径的长度,如果有多组解请输出任意一组。

 

输入输出样例

输入样例#1: 
6 5
1 3
1 4
3 6
3 4
4 5
输出样例#1: 
1 2


考虑怎么利用有向无环图这个性质。
假设我们从 x -> y ,其中x的拓扑序为a,y的拓扑序为b,显然a<b。
那么显然a<拓扑序<b的点都不再会被经过了。

所以我们就可以用x -> y这条边所在的最长路径来更新删除 a<拓扑序<b 的点 的答案了。
当然删除一个点i还不会影响路径上拓扑序都>或< top(i)的点。

对于前者我们可以在下标是拓扑序的线段树上直接区间修改;后者直接预处理出前缀后缀就可以了。

(最近好像常数不是很大的样子)


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=500005;
#define lc (o<<1)
#define mid (l+r>>1)
#define rc ((o<<1)|1)

inline int read(){
	int x=0; char ch=getchar();
	for(;!isdigit(ch);ch=getchar());
	for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
	return x;
}

int hd[maxn],ne[maxn*2],to[maxn*2],num;
int dfn[maxn],dy[maxn],F[maxn],B[maxn],dc;
int n,m,le,ri,w,mx[maxn*4],d[maxn],p,ans=1<<30;
int qz[maxn],hz[maxn];

inline void add(int x,int y){ to[++num]=y,ne[num]=hd[x],hd[x]=num,d[y]++;}

void update(int o,int l,int r){
	if(l>=le&&r<=ri){ mx[o]=max(mx[o],w); return;}
	if(le<=mid) update(lc,l,mid);
	if(ri>mid) update(rc,mid+1,r);
}

void dfs(int o,int l,int r,int M){
	if(l==r){
		M=max(max(M,mx[o]),max(qz[l-1],hz[l+1]));
	    if(M<ans) ans=M,p=dy[l]; 
		return;
	}
	dfs(lc,l,mid,max(M,mx[o]));
	dfs(rc,mid+1,r,max(M,mx[o]));
}

inline void tpsort(){
	queue<int> q; int x;
	for(int i=1;i<=n;i++) if(!d[i]) q.push(i);
	
	while(!q.empty()){
		x=q.front(),q.pop();
		
		dfn[x]=++dc,dy[dc]=x;
		
		for(int i=hd[x];i;i=ne[i]){
			F[to[i]]=max(F[to[i]],F[x]+1);
			if(!(--d[to[i]])) q.push(to[i]);
		}
	}
	
	for(int i=dc,now;i;i--){
		now=dy[i];
		for(int j=hd[now];j;j=ne[j]) B[now]=max(B[now],B[to[j]]+1);
	}
}

inline void getnew(){
	for(int i=1;i<=n;i++)
	    for(int j=hd[i];j;j=ne[j]){
	    	le=dfn[i]+1,ri=dfn[to[j]]-1;
	    	if(le<=ri) w=F[i]+B[to[j]]+1,update(1,1,n);
		}
	
	for(int i=1;i<=n;i++) qz[i]=max(qz[i-1],F[dy[i]]);
	for(int i=n;i;i--) hz[i]=max(hz[i+1],B[dy[i]]);
}

inline void solve(){
	tpsort();
	
	getnew();
	
	dfs(1,1,n,0);
}

int main(){
	n=read(),m=read();
	int uu,vv;
	for(int i=1;i<=m;i++) uu=read(),vv=read(),add(uu,vv);
	
	solve();
	
	printf("%d %d\n",p,ans);
	return 0;
}