题解 P3573 【[POI2014]RAJ-Rally】

· · 题解

来Dew的博客观看？

好神仙的一道题目！

一般来说一些删边删点的东西在统计统计信息什么的在图上都比较麻烦，我们应该找一找这个题的特殊性

很容易发现，重点在这个图是DAG。

有了DAG，我们可以O(n)求出单源点最长路什么的

然而这个图的最长路咋求呢？其实这个不难，统计通过每条边的最长路，取最大值就行了

设diss_i表示以i为开头的最长路，dist_i表示以i为结尾的最长路，为起点的反向跑一遍就可以得到

通过某条边E=(u,v)的最长路等价于dist_u+diss_v+1

topo图还有一个性质，按照topo序取出一部分连续的点作为S集，剩下的作为T集，则两个集合的相互连边只有一些S到T的

为了方便，节点编号就是topo序，红边为S连向T的边

这启发我们按照拓扑序进行删点，我们先假设所有的点在T集，这样最长路就是max diss_i

我们按topo序拿走点，删掉有关贡献的边，统计答案，加入有关贡献的边，然后加入S集

这样说起来一点也不清楚，我们结合图形说明

现在正在删点4，看看有那些边可以作为答案。

首先S集合里面的边的最长长度，但不可以跨越两个集合即 max_{i \in S} dist_i，当然4的不算

然后跨越S,T集合的边即 max_{E(u,v),u \in S,v \in T} dist_u+diss_v+1

最后是集合T的，其实也差不多，不赘述了

我们首先在T集合的只有最后一种的答案，发现第一种的答案可以在把点扔进S的时候更新，而多余的T的答案可以在每次删点时删掉

第二种边其实也好统计，在点进去的时候出边都放进答案，当这个出边对的点进入S的时候把边的答案去掉

这么说可能还是有点抽象，还是拿4举个例子

第一步，删去diss_4

第二步，删去diss_4+dist_{1/2/3}+1这三个

第三步，统计最大值

第四步，加入dist_4+diss_{6/7}+1这两个

第五步，加入dist_4

关于这些操作，因为边权很小，所以我们可以拿权值线段树维护，也可以拿堆维护

其实思想上我说得也不算清楚，只是大概把过程讲清楚了

Code:

#include <cstdio>
#include <vector>
const int N=1e6+10;
int head[N],to[N<<1],Next[N<<1],cnt;
void add(int u,int v)
{
    to[++cnt]=v,Next[cnt]=head[u],head[u]=cnt;
}
std::vector <int > To[N];
int q[N],n,m,in[N],topo[N],tot;
void toposort()
{
    int l=1,r=0;
    for(int i=1;i<=n;i++)
        if(!in[i]) topo[++tot]=i,q[++r]=i;
    while(l<=r)
    {
        int u=q[l++];
        for(int i=head[u];i;i=Next[i])
        {
            int v=to[i];
            --in[v];
            if(!in[v]) q[++r]=v,topo[++tot]=v;
        }
    }
}
int diss[N],dist[N];
#define ls ch[now][0]
#define rs ch[now][1]
int max(int x,int y){return x>y?x:y;}
void DP()
{
    for(int k=1;k<=n;k++)
    {
        int u=topo[k];
        for(int i=head[u];i;i=Next[i])
        {
            int v=to[i];
            dist[v]=max(dist[v],dist[u]+1);
        }
    }
    for(int k=n;k;k--)
    {
        int u=topo[k];
        for(int i=0;i<To[u].size();i++)
        {
            int v=To[u][i];
            diss[v]=max(diss[v],diss[u]+1);
        }
    }
}
void init()
{
    scanf("%d%d",&n,&m);
    for(int u,v,i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        add(u,v),++in[v],To[v].push_back(u);
    }
    toposort();
    DP();
}
int ch[N<<2][2],sum[N<<2],root;
void change(int &now,int l,int r,int pos,int delta)
{
    if(!now) now=++tot;
    if(l==r) {sum[now]+=delta;return;}
    int mid=l+r>>1;
    if(pos<=mid) change(ls,l,mid,pos,delta);
    else change(rs,mid+1,r,pos,delta);
    sum[now]=sum[ls]+sum[rs];
}
int query(int now,int l,int r)
{
    if(l==r) return l;
    int mid=l+r>>1;
    if(sum[rs]) return query(rs,mid+1,r);
    else return query(ls,l,mid);
}
void work()
{
    tot=0;int mx,id,ans=0x7fffffff;
    for(int i=1;i<=n;i++)
        change(root,0,n,diss[i],1);
    for(int i=1;i<=n;i++)
    {
        int now=topo[i];
        change(root,0,n,diss[now],-1);
        for(int j=0;j<To[now].size();j++)
        {
            int v=To[now][j];
            change(root,0,n,diss[now]+dist[v]+1,-1);
        }
        if((mx=query(root,0,n))<ans) ans=mx,id=now;
        for(int j=head[now];j;j=Next[j])
        {
            int v=to[j];
            change(root,0,n,dist[now]+diss[v]+1,1);
        }
        change(root,0,n,dist[now],1);
    }
    printf("%d %d\n",id,ans);
}
int main()
{
    init(),work();
    return 0;
}