BZOJ 3832: [Poi2014]Rally

Sol

线段树+拓扑序.

先把图的拓扑序搞出来,然后统计从起点到该点最长链,从该点到终点的最长链,然后建个起点终点,这里跟网络流很像,把它统一到一个有起点的图中,这里也要注意下细节处理.S,T的一个边割掉后最长链就是答案.

然后一开始所有点都在T的集合中,一个个将点加入S集合,用线段树维护每个节点 (从起点到该点最长链+从终点到该点的最长链)的长度,其实就是一个权值线段树,然后就是加加减减的...

Code

/**************************************************************

    Problem: 3832

    User: BeiYu

    Language: C++

    Result: Accepted

    Time:13472 ms

    Memory:65804 kb

****************************************************************/

#include<cstdio>

#include<vector>

#include<queue>

#include<iostream>

using namespace std;

const int N = 500050;

#define debug(a) cout<<#a<<"="<<a<<endl

inline int in(int x=0,char ch=getchar()){ while(ch>'9'||ch<'0') ch=getchar();

    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x; }

int n,m,l,r,s,t;int du[N],q[N],f[N][2];

vector<int> g[N],h[N];

int ans1,ans2;

#define mid ((l+r)>>1)

#define lc (o<<1)

#define rc (o<<1|1)

int d[N<<2],ma[N<<2];

void Add(int x,int v,int o=1,int l=0,int r=n+2){

    if(l==r){ d[o]+=v;return; }

    if(x<=mid) Add(x,v,lc,l,mid);

    else Add(x,v,rc,mid+1,r);

    d[o]=d[lc]+d[rc];

}

int Query(int o=1,int l=0,int r=n+2){

    if(l==r) return l;

    if(d[rc]>0) return Query(rc,mid+1,r);

    else return Query(lc,l,mid);

}

#undef mid

#undef lc

#undef rc

int main(){

//  freopen("in.in","r",stdin);

    n=in(),m=in();

    for(int i=1,u,v;i<=m;i++){

        u=in(),v=in(),du[v]++;

        g[u].push_back(v),h[v].push_back(u);

    }

    for(int i=1;i<=n;i++) if(!du[i]) q[r++]=i;

    int cnt=r;

    for(int x;l<r;){

        x=q[l++];

        for(int i=0,lim=g[x].size();i<lim;i++) if(!--du[g[x][i]]) q[r++]=g[x][i];

    }for(int i=0;i<n;i++){

        for(int j=0,u=q[i],lim=h[u].size();j<lim;j++)

            f[u][0]=max(f[u][0],f[h[u][j]][0]+1);

        for(int j=0,u=q[r-i-1],lim=g[u].size();j<lim;j++)

            f[u][1]=max(f[u][1],f[g[u][j]][1]+1);

    }

//  for(int i=0;i<cnt;i++) Add(f[q[i]][1],1);

//  debug(cnt);

//  debug(Query());

    s=n+1,t=s+1;

    for(int i=1;i<=n;i++){

        g[s].push_back(i),h[i].push_back(s);

        g[i].push_back(t),h[t].push_back(i);

        Add(f[i][1],1);

    }

    f[s][0]=-1,f[t][1]=-1;

    ans2=n+2;

//  for(int i=1;i<=t;i++) printf("%d %d\n",f[i][0],f[i][1]);

    for(int i=0;i<n;i++){

        int u=q[i];

        for(int j=0,lim=h[u].size();j<lim;j++)

            Add(f[h[u][j]][0]+f[u][1]+1,-1);

        int tmp=Query();

        if(tmp<ans2) ans2=tmp,ans1=u;

        for(int j=0,lim=g[u].size();j<lim;j++)

            Add(f[g[u][j]][1]+f[u][0]+1,1);

    }return printf("%d %d\n",ans1,ans2);

}