自动搬运

查看原文

来自洛谷，原作者为

	xcxcli AFOed.

搬运于2025-08-24 21:50:18，当前版本为作者最后更新于2019-09-28 14:31:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本题的要点是有向无环图，所以我们可以先拓扑排序，并$O(n)$求出以$u$为起点的最长路$ds_u$和以$u$为终点的最长路$dt_u$。

于是我们可以得到经过边$(u\to v)$的最长路为$dt_u+1+ds_v$。

把拓扑序小于$i$的节点的集合记为$A$，把拓扑序大于$i$的集合记为$B$。在删去$i$之后，可能是最长路的路径有：

$A\to A,B\to B,A\to B$

所以我们要维护$dt_u(u\in A),ds_v(v\in B),dt_u+1+ds_v(u\to v)$的最大值。

那么我们怎么得到上面的路径？我们可以从删除$i+1$的状态转移过来。下面是转移的过程：

一开始数据结构中有：$dt_{1,2,3},ds_{4,5,6,7},dt_2+1+ds_4,dt_3+1+ds_5$

删除$ds_4,dt_2+1+ds_4$，这时数据结构中数字的最大值就是图的最长路。

将$dt_4,dt_4+1+ds_6,dt_4+1+ds_5$加入数据结构，成功转移到下一个状态。

所以我们可以将初始状态设为所有节点都在$B$，然后按拓扑序一个个加入到$A$中。

我们的数据结构要支持插入、删除、求最大值。所以我们可以用multiset，权值线段树。但我们还可以写堆。

我们可以用$a,b$两个堆，分别表示插入和删除的操作。当我们要取出堆顶元素时，可以比较两者的堆顶。若两者相同，则弹出两者。否则$a$的堆顶元素就是真正的堆顶元素。

struct Queue{
	priority_queue<int>a,b;int sz;
	void push(int x){a.push(x),++sz;}
	void pop(int x){b.push(x),--sz;}
	int top(){
		while(!b.empty()&&a.top()==b.top())a.pop(),b.pop();
		return sz>0?a.top():-INF;
	}
}Q;//可删堆

下面我们来分析一下复杂度：初始化+拓扑排序$O(n+m)$，每个点和边都加入和删除过一次，总复杂度$O((n+m)\log(n+m))$。

比用multiset和权值线段树都跑得慢，果然是人弱自带大常数。

代码如下：

#include<stdio.h>
#include<queue>
using namespace std;
int rd(){
	int k=0,f=1;char c=getchar();
	while(c>'9'||c<'0'){if(c=='-')f=0;c=getchar();}
	while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
	return f?k:-k;
}
const int N=500001;
int Max(int x,int y){return x>y?x:y;}
int Min(int x,int y){return x<y?x:y;}
struct E{int v,nxt;}e[N<<1]; 
struct Queue{
	priority_queue<int>a,b;
	void push(int x){a.push(x);}
	void pop(int x){b.push(x);}
	int top(){while(!b.empty()&&a.top()==b.top())a.pop(),b.pop();return a.top();}
}Q;//可删堆
int n,m,h[N],H[N],cnt,u,v,ds[N],dt[N],I[N],a[N],T,w,ans;queue<int>q;
void add(int u,int v,int*head){e[++cnt].v=v,e[cnt].nxt=head[u],head[u]=cnt;}
int main(){
	freopen("data.in","r",stdin);
	freopen("data.out","w",stdout);
	n=rd(),m=rd();
	for(int i=1;i<=m;++i)u=rd(),v=rd(),add(u,v,h),add(v,u,H),++I[v];
	for(int i=1;i<=n;++i)if(!I[i])q.push(i);
	while(!q.empty()){
		u=q.front(),q.pop(),a[++T]=u;
		for(int i=h[u];i;i=e[i].nxt)if(--I[v=e[i].v]==0)q.push(v); 
	}//拓扑排序
	for(int i=1;i<=n;++i){
		u=a[i];
		for(int i=h[u];i;i=e[i].nxt)v=e[i].v,dt[v]=Max(dt[v],dt[u]+1);
	}
	for(int i=n;i;--i){
		u=a[i];
		for(int i=H[u];i;i=e[i].nxt)v=e[i].v,ds[v]=Max(ds[v],ds[u]+1);
	}//求dt,ds
	for(int i=1;i<=n;++i)Q.push(ds[i]);
	ans=Q.top();
	for(int j=1;j<=n;++j){
		u=a[j],Q.pop(ds[u]);
		for(int i=H[u];i;i=e[i].nxt)Q.pop(dt[e[i].v]+ds[u]+1);//删除点和边
		T=Q.top();
		if(T<=ans)ans=T,w=u;//更新答案
		for(int i=h[u];i;i=e[i].nxt)Q.push(dt[u]+ds[e[i].v]+1);
		Q.push(dt[u]);//插入点和边
	}
	printf("%d %d\n",w,ans);
	return 0;
}