洛谷 P2542 [AHOI2005]航线规划 题解【树链剖分】【线段树】【tarjan】

作者: wjyyy 分类: tarjan,图论,,树链剖分,线段树,解题报告 发布时间: 2018-07-14 17:37

点击量:22

 

   一道特别特别特别考基本功的题。

 

题目描述

对Samuel星球的探险已经取得了非常巨大的成就,于是科学家们将目光投向了Samuel星球所在的星系——一个巨大的由千百万星球构成的Samuel星系。

 

星际空间站的Samuel II巨型计算机经过长期探测,已经锁定了Samuel星系中许多星球的空间坐标,并对这些星球从1开始编号1、2、3……。

 

一些先遣飞船已经出发,在星球之间开辟探险航线。

 

探险航线是双向的,例如从1号星球到3号星球开辟探险航线,那么从3号星球到1号星球也可以使用这条航线。

 

例如下图所示:

在5个星球之间,有5条探险航线。

 

A、B两星球之间,如果某条航线不存在,就无法从A星球抵达B星球,我们则称这条航线为关键航线。

 

显然上图中,1号与5号星球之间的关键航线有1条:即为4-5航线。

 

然而,在宇宙中一些未知的磁暴和行星的冲撞,使得已有的某些航线被破坏,随着越来越多的航线被破坏,探险飞船又不能及时回复这些航线,可见两个星球之间的关键航线会越来越多。

 

假设在上图中,航线4-2(从4号星球到2号星球)被破坏。此时,1号与5号星球之间的关键航线就有3条:1-3,3-4,4-5。

 

小联的任务是,不断关注航线被破坏的情况,并随时给出两个星球之间的关键航线数目。现在请你帮助完成。

 

输入输出格式

输入格式:

第一行有两个整数N,M。表示有N个星球(1< N < 30000),初始时已经有M条航线(1 < M < 100000)。随后有M行,每行有两个不相同的整数A、B表示在星球A与B之间存在一条航线。接下来每行有三个整数C、A、B。C为1表示询问当前星球A和星球B之间有多少条关键航线;C为0表示在星球A和星球B之间的航线被破坏,当后面再遇到C为1的情况时,表示询问航线被破坏后,关键路径的情况,且航线破坏后不可恢复; C为-1表示输入文件结束,这时该行没有A,B的值。被破坏的航线数目与询问的次数总和不超过40000。   输出格式:

对每个C为1的询问,输出一行一个整数表示关键航线数目。

 

输入输出样例

输入样例#1:
5 5
1 2
1 3
3 4
4 5
4 2
1 1 5
0 4 2
1 5 1
-1
输出样例#1:
1
3

说明

我们保证无论航线如何被破坏,任意时刻任意两个星球都能够相互到达。在整个数据中,任意两个星球之间最多只可能存在一条直接的航线。

 

题解:

   关键路径让人联想到割边,不过这里求的是两点之间的关键路径,可以缩环为点,缩图为树,求树上两点间距离。而有的环还会被拆开,根据航线被破坏后不能再被修复,我们考虑倒着做。

 

   最终状态的环是可以缩掉的,因为环内各点一定不存在关键路径。这时图变成了一棵树,我们如果再给树上两点连上一条边,就会成环,这样又要做一遍tarjan缩环。不过我们可以用树剖把路径上的点边权改为0,因为上面建模时把缩点后两点间距离定为了1。只要把最短路径上的边全部改为0,这一段就相当于一个环,后面以此类推也可以做。缩环后的处理一定要特别注意,一定要映射为缩点后的点编号。

 

   不过树剖维护的是点权,这里要维护边权,那么就让每个点去维护自己的入边边权。不过要注意的是,树剖两点间LCA的值是不能改的,因为它维护的边权不在最短路径上。这样一来就要特判LCA的位置,如果恰好在同一环上,那就不操作;到树剖最后一步相同链时,区间是[dfn[x]+1,dfn[y]],因为dfn[x]维护的边不在路径上。注意建树时1点维护的边权为0。

 

Tip:namespace完美解决了我多个dfn/s数组和cnt的麻烦。

 

Code:

#include
#include
#include
#include
#define ls (k<<1)
#define rs (k<<1|1)
#define mid (l+r>>1)
#define Mid (T[k].l+T[k].r>>1)
using std::map;
using std::min;
using std::max;
map >m;
struct edge
{
    int n,nxt;
    int able;
    edge(int n,int nxt)
    {
        this->n=n;
        this->nxt=nxt;
        able=1;
    }
    edge()
    {
        nxt=-1;
        able=1;
    }
}e[410000];
int head[31000],ecnt=-1;
void add(int from,int to)
{
    e[++ecnt]=edge(to,head[from]);
    head[from]=ecnt;
    e[++ecnt]=edge(from,head[to]);
    head[to]=ecnt;
}
int n;
struct query
{
    int u,v,op,ans;
}q[41000];
int del[31000];
namespace Tarjan
{
int dfn[31000],low[31000],cnt=0;
int in[31000],s[31000],top=0;
void tarjan(int x,int from)
{
    dfn[x]=++cnt;
    low[x]=dfn[x];
    in[x]=1;
    s[++top]=x;
    for(int i=head[x];~i;i=e[i].nxt)
    {
        if(e[i].n==from||!e[i].able)
            continue;
        if(dfn[e[i].n])
        {
            if(in[e[i].n])
                low[x]=min(dfn[e[i].n],low[x]);
            else
                continue;
        }
        else
        {
            tarjan(e[i].n,x);
            low[x]=min(low[x],low[e[i].n]);
        }
    }
    if(low[x]==dfn[x])
    {
        while(s[top]!=x)
        {
            in[s[top]]=0;
            del[s[top--]]=x;
        }
        in[x]=0;
        del[s[top--]]=x;
    }
    return;
}
}
namespace Cut
{
struct node
{
    int l,r,v,lazy;
    node(int l,int r,int v)
    {
        this->l=l;
        this->r=r;
        this->v=v;
        lazy=0;
    }
    node(){lazy=0;}
}T[150000];
void build(int k,int l,int r)
{
    T[k]=node(l,r,r-l+1);
    if(l==1)
        T[k].v--;
    if(l==r)
        return;
    build(ls,l,mid);
    build(rs,mid+1,r);
}
void pushdown(int k)
{
    if(T[k].lazy==0||T[k].l==T[k].r)
    {
        T[k].lazy=0;
        return;
    }
    T[ls].v=0;
    T[ls].lazy=1;
    T[rs].v=0;
    T[rs].lazy=1;
    T[k].lazy=0;
    return;
}
void change(int k,int l,int r)
{
    if(T[k].l==l&&T[k].r==r)
    {
        T[k].lazy=1;
        T[k].v=0;
        return;
    }
    pushdown(k);
    if(r<=Mid)
        change(ls,l,r);
    else if(l>Mid)
        change(rs,l,r);
    else
    {
        change(ls,l,Mid);
        change(rs,Mid+1,r);
    }
    T[k].v=T[ls].v+T[rs].v;
    return;
}
int ask(int k,int l,int r)
{
    if(l==T[k].l&&r==T[k].r)
        return T[k].v;
    pushdown(k);
    if(r<=Mid)
        return ask(ls,l,r);
    else if(l>Mid)
        return ask(rs,l,r);
    else
        return ask(ls,l,Mid)+ask(rs,Mid+1,r);
}
int dfn[31000],top[31000],fa[31000],sz[31000],s[31000],d[31000],cnt=0;
void dfs1(int x)
{
    sz[x]=1;
    for(int i=head[x];~i;i=e[i].nxt)
        if(!d[e[i].n]&&e[i].able)
        {
            if(e[i].n==1)
            {
                int o;
                o=1;
            }
            fa[e[i].n]=x;
            d[e[i].n]=d[x]+1;
            dfs1(e[i].n);
            sz[x]+=sz[e[i].n];
            if(sz[e[i].n]>sz[s[x]])
                s[x]=e[i].n;
        }
}
void dfs2(int x,int t)
{
    dfn[x]=++cnt;
    top[x]=t;
    if(s[x])
        dfs2(s[x],t);
    for(int i=head[x];~i;i=e[i].nxt)
        if(e[i].able&&e[i].n!=fa[x]&&e[i].n!=s[x])
            dfs2(e[i].n,e[i].n);
}
void cut()
{
    d[1]=1;
    dfs1(1);
    cnt=1;
    top[1]=1;
    for(int i=head[1];~i;i=e[i].nxt)
        if(e[i].able)
            dfs2(e[i].n,e[i].n);
}
int modify(int op,int x,int y)
{
    int ans=0;
    int tx=top[x],ty=top[y];
    while(tx!=ty)
    {
        if(d[tx]dfn[y])
    {
        int t=x;
        x=y;
        y=t;
    }
    if(op==0)
        change(1,dfn[x]+1,dfn[y]);
    else
        ans+=ask(1,dfn[x]+1,dfn[y]);
    return ans;
}
}
int main()
{
    memset(head,-1,sizeof(head));
    int M,u,v;
    scanf("%d%d",&n,&M);
    for(int i=1;i<=M;i++)
    {
        scanf("%d%d",&u,&v);
        add(u,v);
        m[u][v]=ecnt-1;
        m[v][u]=ecnt;
    }
    int T;
    for(T=1;;T++)
    {
        scanf("%d",&q[T].op);
        if(q[T].op==-1)
            break;
        scanf("%d%d",&q[T].u,&q[T].v);
        if(q[T].op==0)
        {
            int tmp=m[q[T].u][q[T].v];
            e[tmp].able=0;
            e[tmp^1].able=0;
        }
    }
    T--;
    Tarjan::tarjan(1,1);
    for(int i=1;i<=n;i++)
        for(int j=head[i];~j;j=e[j].nxt)
        {
            e[j].n=del[e[j].n];
            if(del[i]==e[j].n||e[j].able==0)
            {
                e[j].able=0;
                continue;
            }
            if(del[i]!=i)
            {
                e[j].able=0;
                e[++ecnt]=edge(e[j].n,head[del[i]]);
                head[del[i]]=ecnt;
            }
        }
    Cut::cut();
    Cut::build(1,1,Cut::cnt);
    for(int i=T;i;--i)
    {
        if(q[i].op==0)
            Cut::modify(0,del[q[i].u],del[q[i].v]);
        else
            q[i].ans=Cut::modify(1,del[q[i].u],del[q[i].v]);
    }
    for(int i=1;i<=T;i++)
        if(q[i].op==1)
            printf("%d\n",q[i].ans);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */