P3573 [POI2014]RAJ-Rally

小灰灰 2021-03-28 15:42 281阅读 0赞

很妙的思路  
首先这是一个DAG，于是我们先在原图和反图上各做一遍，分别求出\\(diss\_i\\)和\\(dist\_i\\)表示从\\(i\\)点出发的最短路和以\\(i\\)为终点的最短路  
我们考虑把点分为两个集合\\(S\\)和\\(T\\)，一开始所有的点都在\\(T\\)中，按照拓扑序依次将点从\\(T\\)中取出放入\\(S\\)  
考虑对于点\\(u\\)，它从\\(T\\)中被取出，我们把它看做删除了这个点。那么这时图中的最长路径必定属于以下三种中的一种  
1.\\(S\\)中最大的\\(dist\_i\\)  
2.\\(T\\)中最大的\\(diss\_i\\)  
3.\\(dist\_i+diss\_j+1\\)，其中\\(i\\)在\\(S\\)中，\\(j\\)在\\(T\\)中  
于是我们只要能够维护好这些东西就可以了。将\\(u\\)从\\(T\\)中取出时，把它的\\(diss\_u\\)删去，并把所有的\\(dist\_v+diss\_u+1\\)也删去（\\(v\\)表示所有有边指向\\(u\\)的点），这时的最大值即为删掉点\\(u\\)时图中的最长路。把它新加入\\(S\\)中时，加入它的\\(dist\_u\\)，以及所有的\\(diss\_u+dist\_v+1\\)（\\(v\\)表示\\(u\\)指向的所有点）  
以上操作可以用线段树来维护

//minamoto
    #include<bits/stdc++.h>
    using namespace std;
    #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
    char buf[1<<21],*p1=buf,*p2=buf;
    template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
    int read(){
        int res,f=1;char ch;
        while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
        for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
        return res*f;
    }
    const int N=1e6+5;
    int head[N],Next[N],ver[N],du[N],tot;
    int hc[N],nc[N],vc[N],tc;
    inline void add(int u,int v){ver[++tot]=v,Next[tot]=head[u],head[u]=tot;}
    inline void addc(int u,int v){vc[++tc]=v,nc[tc]=hc[u],hc[u]=tc;}
    int diss[N],dist[N],q[N],n,m,ans=0x3f3f3f3f,id,mx;
    void topo(){
        int h=1,t=0;
        for(int i=1;i<=n;++i)if(!du[i])q[++t]=i;
        while(h<=t){
            int u=q[h++];
            for(int i=head[u];i;i=Next[i]){
                cmax(dist[ver[i]],dist[u]+1);
                if(--du[ver[i]]==0)q[++t]=ver[i];
            }
        }
        for(int j=n;j;--j){
            int u=q[j];
            for(int i=head[u];i;i=Next[i])cmax(diss[u],diss[ver[i]]+1);
        }
    }
    #define ls (p<<1)
    #define rs (p<<1|1)
    int sum[N<<2];
    void upd(int p,int l,int r,int x,int v){
        if(l==r)return (void)(sum[p]+=v);
        int mid=(l+r)>>1;
        x<=mid?upd(ls,l,mid,x,v):upd(rs,mid+1,r,x,v);
        sum[p]=sum[ls]+sum[rs];
    }
    int query(int p,int l,int r){
        if(l==r)return l;int mid=(l+r)>>1;
        return sum[rs]?query(rs,mid+1,r):query(ls,l,mid);
    }
    int main(){
    //  freopen("testdata.in","r",stdin);
        n=read(),m=read();
        for(int i=1,u,v;i<=m;++i)u=read(),v=read(),add(u,v),addc(v,u),++du[v];
        topo();for(int i=1;i<=n;++i)upd(1,0,n,diss[i],1);
        for(int j=1;j<=n;++j){
            int u=q[j];upd(1,0,n,diss[u],-1);
            for(int i=hc[u];i;i=nc[i])upd(1,0,n,diss[u]+dist[vc[i]]+1,-1);
            if((mx=query(1,0,n))<ans)ans=mx,id=u;
            for(int i=head[u];i;i=Next[i])upd(1,0,n,dist[u]+diss[ver[i]]+1,1);
            upd(1,0,n,dist[u],1);
        }
        printf("%d %d\n",id,ans);return 0;
    }