[POI2014]RAJ-Rally

· · 题解

本题的要点是有向无环图，所以我们可以先拓扑排序，并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;
}