P2542 [AHOI2005]航线规划 题解


以下题解仅供学习参考使用。

抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在洛谷是严格禁止的。

洛谷非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看洛谷社区规则

评论

  • BriMon
    写的太棒了!
  • siruiyang_sry
    hack
  • siruiyang_sry
    5 5 5 1 5 2 3 1 5 3 4 3 1 3 2 0 1 5 0 3 4 1 4 5 0 1 3 -1
  • Llf0703
    @siruiyang_sry 我们保证无论航线如何被破坏,任意时刻任意两个星球都能够相互到达。您这样断了4,3图就不连通了啊
作者: YoungNeal 更新时间: 2018-06-06 21:49  在Ta的博客查看 举报    9  

题解在博客食用效果更佳哦~

楼下dalao的lct我并不会

只会蒻蒻的树剖qwq

Hint

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

Solution

首先这题离线逆序处理不必多说了,这类删除点/边题固定套路

刚看到这题的想法是 $Tarjan$ 缩点然后怎么拓扑乱搞求一下距离

然而这是一个无向图并不存在拓扑序

然而我并不会求距离

我们注意到 $Hint$ 里面保证了这么一句话在整个数据中,任意两个星球之间最多只可能存在一条直接的航线。

题目保证不存在重边,而且互相连通,又是无向图...想到了什么?缩完点后的图是一棵树啊!

也就是说,我们需要动态的维护树上点之间的距离

树上把点连起来的是什么?边啊!

那么我们需要维护树上两点之间的边权不就行了!

想到了什么?树链剖分!

对,我们可以树剖维护树上的边权,这样就可以轻而易举的求出树上两点之间的距离了。

那...怎么动态缩点呢?

做这题时,我为这事纠结了半天...

然后才发现,既然能维护树上两点间距离,那还缩点干啥呢?

直接将一个环内的点之间的边权赋为0不就行了!

算法流程如下:

  1. 读入询问,逆序处理
  2. 先随便在原图中求出一棵生成树,我直接用 $dfs$ 序实现的
  3. 然后用那些没被删除的非树边先更新一遍当前的边权
  4. 树剖裸题。

因为是边权下放到点权,注意修改的时候不要改它们的 $lca$ !

Code

#include<map>
#include<cstdio>
#include<cctype>
#define N 30005
#define Q 40005
#define M 100005
#define max(A,B) ((A)>(B)?(A):(B))
#define min(A,B) ((A)<(B)?(A):(B))
#define swap(A,B) ((A)^=(B)^=(A)^=(B))

int n,m,d[N],ans[Q];
std::map<int,int> mp;
int cnt,tot,son[N],pos;
int val[N],head[N],fa[N];
int dfn[N],top[N],ques[Q][5];
int sze[N],sum[N<<2],lazy[N<<2];

struct Edge{
    int to,nxt,ok;
}edge[M<<1];

void add(int x,int y){
    edge[++cnt].to=y;
    edge[cnt].nxt=head[x];
    head[x]=cnt;
    mp[x*(n+1)+y]=cnt;;
}

int getint(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x*f;
}

void first_dfs(int now){
    sze[now]=1;
    for(int i=head[now];i;i=edge[i].nxt){
        int to=edge[i].to;
        if(sze[to] or edge[i].ok)
            continue;
        d[to]=d[now]+1;
        fa[to]=now;
        first_dfs(to);
        sze[now]+=sze[to];
        if(sze[to]>sze[son[now]])
            son[now]=to;
    }
}

void second_dfs(int now,int low){
    dfn[now]=++tot;
    top[now]=low;
    if(son[now])
        second_dfs(son[now],low);
    for(int i=head[now];i;i=edge[i].nxt){
        int to=edge[i].to;
        if(fa[to]!=now or to==son[now] or edge[i].ok)
            continue;
        second_dfs(to,to);
    }
}

void pushup(int cur){
    sum[cur]=sum[cur<<1]+sum[cur<<1|1];
}

void build(int cur,int l,int r){
    if(l==r){
        sum[cur]=1;
        return;
    }
    int mid=l+r>>1;
    build(cur<<1,l,mid);
    build(cur<<1|1,mid+1,r);
    pushup(cur);
}

void pushdown(int cur){
    if(!lazy[cur])
        return;
    sum[cur<<1]=sum[cur<<1|1]=0;
    lazy[cur<<1]=lazy[cur<<1|1]=1;
    lazy[cur]=0;
}

void modify(int cur,int l,int r,int ql,int qr){
    if(ql<=l and r<=qr){
        sum[cur]=0;
        lazy[cur]=1;
        return;
    }
    pushdown(cur);
    int mid=l+r>>1;
    if(ql<=mid)
        modify(cur<<1,l,mid,ql,qr);
    if(mid<qr)
        modify(cur<<1|1,mid+1,r,ql,qr);
    pushup(cur);
}

void change(int x,int y){
    while(top[x]!=top[y]){
        if(d[top[x]]<d[top[y]])
            swap(x,y);
        modify(1,1,n,dfn[top[x]],dfn[x]);
        x=fa[top[x]];
    }
    if(d[x]<d[y])
        swap(x,y);
    if(d[x]!=d[y])
        modify(1,1,n,dfn[y]+1,dfn[x]);
}

void third_dfs(int now){
    for(int i=head[now];i;i=edge[i].nxt){
        int to=edge[i].to;
        if(edge[i].ok)
            continue;
        if(fa[to]==now)
            third_dfs(to);
        if(fa[now]!=to and d[to]<d[now])
            change(to,now);
    }
}

int query(int cur,int l,int r,int ql,int qr){
    if(ql<=l and r<=qr)
        return sum[cur];
    pushdown(cur);
    int mid=l+r>>1,now=0;
    if(ql<=mid)
        now+=query(cur<<1,l,mid,ql,qr);
    if(mid<qr)
        now+=query(cur<<1|1,mid+1,r,ql,qr);
    return now;
}

int ask(int x,int y){
    int now=0;
    while(top[x]!=top[y]){
        if(d[top[x]]<d[top[y]])
            swap(x,y);
        now+=query(1,1,n,dfn[top[x]],dfn[x]);
        x=fa[top[x]];
    }
    if(d[x]<d[y])
        swap(x,y);
    now+=query(1,1,n,dfn[y],dfn[x]);
    now-=query(1,1,n,dfn[y],dfn[y]);
    return now;
}

signed main(){
    n=getint(),m=getint();
    for(int i=1;i<=m;i++){
        int x=getint(),y=getint();
        add(x,y); add(y,x);
    }
    while(1){
        int a=getint();
        if(a==-1) break;
        int b=getint(),c=getint();
        ques[++pos][1]=a;
        ques[pos][2]=b;
        ques[pos][3]=c;
        if(a==0)
            edge[mp[b*(n+1)+c]].ok=edge[mp[c*(n+1)+b]].ok=1;
    }
    d[1]=1;
    first_dfs(1);
    second_dfs(1,1);
    build(1,1,n);
    third_dfs(1);
    for(int i=pos;i;i--){
        if(ques[i][1])
            ans[i]=ask(ques[i][2],ques[i][3]);
        else
            change(ques[i][2],ques[i][3]);
    }
    for(int i=1;i<=pos;i++){
        if(ques[i][1]!=1) continue;
        printf("%d\n",ans[i]);
    }
    return 0;
}

评论

  • forever誓
    感谢您的讲解,但是我可以问一下为什么暴力修改的次数不会超过nlogn吗?
  • drophell
    sz是怎么实现维护关键路径的啊````````````````````````
  • FlashHu
    @forever誓 和并查集差不多吧,蒟蒻不会用文字证。。。
  • FlashHu
    @drophell 桥的数量等于双连通分量数量-1
  • GKxx
    short卡常可还行
  • siruiyang_sry
    hack
  • siruiyang_sry
    5 5 3 5 4 1 4 2 3 4 1 3 0 4 3 0 5 3 0 3 1 1 2 5 -1
  • siruiyang_sry
    @FlashHu
  • Balloons
    @siruiyang_sry 我们保证无论航线如何被破坏,任意时刻任意两个星球都能够相互到达。您这样断了4,3图就不连通了啊
作者: FlashHu 更新时间: 2018-03-26 20:00  在Ta的博客查看 举报    10  

太弱了不会树剖,觉得LCT好写一些,就上LCT乱搞,当LCT维护双连通分量的练手题好了

正序删边是不好来维护连通性的,于是就像水管局长那样离线处理,逆序完成操作

显然,每个点可以代表一个双连通分量,查询就是链的长度-1

连接一条边,如果在LCT中还没连通就link,如果连通了,显然这里会出现一个环,然后暴力缩点,可以把当前辅助树的根节点当做集合的标志节点,然后dfs整个辅助树,把链上的其它点的并查集祖先暴力改成这个标志节点,最后再断开标志节点与子树的连接。总的暴力修改次数不会超过$N\log N$次,复杂度是对的

但是点缩完了,那它们的子树不会指空吗?所以,access的时候,要更新$x$为$geth(f[x])$

至于常数,LCT也并不是很慢啊。反正有了O2还是可以做到很优秀的

代码细节很多,调试真心累TAT

#include<cstdio>
#include<algorithm>
using namespace std;
#define RG register
#define R RG short
#define I inline void
#define IB inline bool
#define IS inline short
#define G ch=getchar()
#define lc c[x][0]
#define rc c[x][1]
const int N=30009,M=100009;
short f[N],c[N][2],s[N],h[N],a[N],b[N],op[N],ans[M];
bool r[N],vis[M];
struct EDGE{//对边排序,方便查找该边是否被删除
    short x,y;
    IB operator<(const EDGE a)const{
        return x<a.x||(x==a.x&&y<a.y);
    }
}e[M];
template<typename T>
I in(RG T&z){
    RG char G;
    while(ch<'-')G;
    z=ch&15;G;
    while(ch>'-')z*=10,z+=ch&15,G;
}
IS geth(R x){
    if(x==h[x])return x;
    return h[x]=geth(h[x]);
}
IB nroot(R x){
    return c[f[x]][0]==x||c[f[x]][1]==x;
}
I pushup(R x){
    s[x]=s[lc]+s[rc]+1;
}
I pushdown(R x){
    if(r[x]){
        swap(lc,rc);
        r[lc]^=1;r[rc]^=1;r[x]=0;
    }
}
I pushall(R x){
    if(nroot(x))pushall(f[x]);
    pushdown(x);
}
I rotate(R x){
    R y=f[x],z=f[y],k=c[y][1]==x,w=c[x][!k];
    if(nroot(y))c[z][c[z][1]==y]=x;f[x]=z;
    c[x][!k]=y;f[y]=x;
    c[y][k]=w;f[w]=y;
    pushup(y);
}
I splay(R x){
    pushall(x);
    R y;
    while(nroot(x)){
        if(nroot(y=f[x]))
            rotate((c[f[y]][0]==y)^(c[y][0]==x)?x:y);
        rotate(x);
    }
    pushup(x);
}
I access(R x){
    for(R y=0;x;y=x,x=f[y]=geth(f[x]))//注意更新
        splay(x),rc=y,pushup(x);
}
I makeroot(R x){
    access(x);splay(x);
    r[x]^=1;
}
IS findroot(R x){
    access(x);splay(x);
    pushdown(x);
    while(lc)pushdown(x=lc);
    splay(x);
    return x;
}
I split(R x,R y){
    makeroot(y);
    access(x);splay(x);
}
I del(R x,R y){//函数递归缩点
    if(x)h[x]=y,del(lc,y),del(rc,y);
}
I merge(R x,R y){
    if(x==y)return;//在一个分量里什么都不用干
    makeroot(x);
    if(findroot(y)!=x){
        f[x]=y;return;//等于link
    }
    del(rc,x);
    rc=0;pushup(x);//缩点,删点
}
int main(){
    RG int n,m,i,j;
    R x,y;
    in(n);in(m);
    for(i=1;i<=n;++i)s[i]=1,h[i]=i;
    for(i=1;i<=m;++i){
        in(x);in(y);
        if(x>y)swap(x,y);//强制编号,方便以后查找
        e[i]=(EDGE){x,y};
    }
    sort(e+1,e+m+1);
    for(j=1;in(op[j]),op[j]!=131;++j){
        in(x);in(y);
        if(!op[j]){
            if(x>y)swap(x,y);
            vis[lower_bound(e+1,e+m+1,(EDGE){x,y})-e]=1;
        }//重载完小于号,直接二分找到,再打上删除记号
        a[j]=x;b[j]=y;
    }
    for(i=1;i<=m;++i)
        if(!vis[i])merge(geth(e[i].x),geth(e[i].y));
    for(i=0,--j;j;--j){
        x=geth(a[j]);y=geth(b[j]);
        if(op[j])split(x,y),ans[++i]=s[x]-1;
        else merge(x,y);
    }
    while(i)printf("%hd\n",ans[i--]);
    return 0;
}

评论

  • Imakf
    您的做法和我一样QAQ
作者: Mital 更新时间: 2019-03-21 19:34  在Ta的博客查看 举报    3  

一只蒟蒻介绍一种可能不太难想的解法。

(那些大佬好像都写了什么缩点双还是什么的,蒟蒻瑟瑟发抖啊$QAQ$)

不难想到要反向处理。

然后题目就变成了:先给一些边,然后不断加边,求$x-y$关键边数量。

因为只有加边操作,所以实际上只有关键边变非关键边,而不存在非关键边变成关键边。

不难发现,一条边如果为关键边,那么其联通了两个联通块,且没有其他边联通这两个联通块,所以对于一条关键边,从其联通的两个联通块中任意两个点到对方点的路径中其都为关键边,简单来讲,就是 一条关键边对于任意两个过其的点都是关键边

故我对每个边维护一下其是否为关键边,如果是其边权为$1$,否则其边权为$0$

由于前面加粗的字体所描述的优秀性质,所以我们询问$x-y$的路径上有多少关键路径,就是询问$x-y$的路径上边权和

有加边操作,所以考虑使用$LCT$,然后要把边拆为点。

现在考虑加边怎么做:

如果一条边连接了两个现在未联通的点,那么直接加边,且加入的这条边显然是一条关键边,假设当前边的编号为$Idnex$,那么$w[Idnex]=1$。

如果一条连接了两个已经联通的点呢?

看图理解$QWQ$

现在的图是这个样子的:

我们加入一条这样的边,那么这条边连接了两个已经联通的点,其显然是一个非关键边。

图中的红边是一条非关键边。

然后考虑其对答案的影响。

其会导致这些边变成非关键边:

(图中绿边)

那么我们如何把这些边改成非关键边?就是要将这些边的点权改为0

不难发现一条这样的红边对答案产生的影响就是:$x-y$的路径中的所有边。

这些边的边权都要被改为$0$

所以如果一条边连接的两个点在同一联通块内,就把这一条链拉出来,把边权全部覆盖为$0$,就操作如下:

先$slipt(x,y)$,然后给打上一个覆盖标记。

细节看代码$QWQ$

#include<bits/stdc++.h>
using namespace std;
int read() {
    char cc = getchar(); int cn = 0, flus = 1;
    while(cc < '0' || cc > '9') {  if( cc == '-' ) flus = -flus;  cc = getchar();  }
    while(cc >= '0' && cc <= '9')  cn = cn * 10 + cc - '0', cc = getchar();
    return cn * flus;
}
#define ls(x) t[x].son[0]
#define rs(x) t[x].son[1]
#define rep( i, s, t ) for( register int i = s; i <= t; ++ i )
#define drep( i, t, s ) for( register int i = t; i >= s; -- i )
const int N = 200000 + 5;
struct LCT {
    int son[2], val, fa, cover;
    bool mark;
}t[N];
struct E{
    int from, to, c;
}e[N];
map< int, int > mc1; 
int n, m, Opt[N], From[N], To[N], tot, w[N], Idnum, ans[N], Id[N];
void pushup( int x ) {
    t[x].val = t[ls(x)].val + t[rs(x)].val + w[x];
}
void push( int x ) { //cover表示覆盖标记,如果有覆盖标记,则此点的w值应改为0,且整棵子树都要被改为0 
    // 所以还要修改t[x].val = 0 
    w[x] = 0, t[x].cover = 1, t[x].val = 0;
}
void pushmark( int x ) {
    if( t[x].cover ) // 下传标记 
        t[x].cover = 0, push( ls(x) ), push( rs(x) ), t[x].val = 0;
    if( t[x].mark )
        t[x].mark = 0, t[ls(x)].mark ^= 1, t[rs(x)].mark ^= 1, swap( ls(x), rs(x) );
}
bool isroot( int x ) {
    return ( rs(t[x].fa) != x ) && ( ls(t[x].fa) != x );
}
void rotate( int x ) {
    int f = t[x].fa, ff = t[f].fa, qwq = ( rs(f) == x );
    t[x].fa = ff;
    if( !isroot(f) ) t[ff].son[rs(ff) == f] = x;
    t[t[x].son[qwq ^ 1]].fa = f, t[f].son[qwq] = t[x].son[qwq ^ 1];
    t[x].son[qwq ^ 1] = f, t[f].fa = x;
    pushup(f), pushup(x);
}
int st[N];
void Splay( int x ) {
    int top = 0, now = x; st[++top] = now;
    while( !isroot(now) ) st[++top] = ( now = t[now].fa );
    while( top ) pushmark( st[top--] );
    while( !isroot(x) ) {
        int f = t[x].fa, ff = t[f].fa;
        if( !isroot(f) ) ( ( rs(ff) == f ) ^ ( rs(f) == x ) ) ? rotate(x) : rotate(f);
        rotate(x);
    }
}
void access( int x ) {
    for( int y = 0; x; y = x, x = t[y].fa ) 
        Splay(x), t[x].son[1] = y, pushup(x);
}
void makeroot( int x ) {
    access( x ), Splay( x ), t[x].mark ^= 1, pushmark( x );
}
int findroot( int x ) {
    access( x ), Splay( x ), pushmark( x );
    while( ls(x) ) pushmark( x = ls(x) );
    return x;
}
void split( int x, int y ) {
    makeroot(x), access(y), Splay(y);
} 
void link( int x, int y ) {
    makeroot( x );
    if( findroot(y) != x ) t[x].fa = y;
}
bool check( int x, int y ) {
    makeroot( x );
    return findroot(y) == x;
}
void input() {
    n = read(), m = read();
    rep( i, 1, m ) {
        e[i].from = read(), e[i].to = read();
        if( e[i].from > e[i].to ) swap( e[i].from, e[i].to ); //swap, 方便统计 
        mc1[e[i].from * ( n + 1 ) + e[i].to] = i, w[i + n] = 1; //拆边,每条边的编号都是i+n,
        //同时在map内记录,方便查初始有那些边存在 
    }
    while( 1 ) {
        Opt[++ tot] = read(); //表示是那种操作 
        if( Opt[tot] == -1 ) break;
        From[tot] = read(), To[tot] = read(); 
        if( Opt[tot] == 0 ) {
            if( From[tot] > To[tot] ) swap( From[tot], To[tot] );
            Id[tot] = mc1[From[tot] * ( n + 1 ) + To[tot]];
            e[Id[tot]].c = 1; //标记这条边被用过了 
        }
    }
}
signed main()
{
    input(); //读入函数 
    rep( i, 1, m ) {
        if( !e[i].c ) { //若这条边没有被用过 
            int u = e[i].from, v = e[i].to;
            if( check( u, v ) )  split( u, v ), push(v); //如果u,v 在一个联通块内,则拉出u到v的链,然后打上标记 
            else link( e[i].from, i + n ), link( i + n, e[i].to ); //否则直接连边 
        }
    }
    drep( i, tot - 1, 1 ) {
        if( Opt[i] == 0 ) { //如果是0,就是连边操作,与前面类似 
            int u = From[i], v = To[i];
            if( check( u, v ) )  split( From[i], To[i] ), push(To[i]);
            else link( From[i], Id[i] + n ), link( Id[i] + n, To[i] );
        }
        if( Opt[i] == 1 ) //否则就是询问,直接split然后统计答案 
            split( From[i], To[i] ), ans[++Idnum] = t[To[i]].val;
    } 
    drep( i, Idnum, 1 ) printf("%d\n", ans[i]);
    return 0;
}

评论

  • GCCCCCCCCC
    超棒
  • oldherd
    orz神仙题解
作者: cppascalinux 更新时间: 2019-02-07 18:44  在Ta的博客查看 举报    3  

一个不用树链剖分和LCT的题解

其实是因为本蒟蒻不会树链剖分和LCT嘤嘤嘤


  • 前半部分的想法和树链剖分是一样的
    将所有操作按时间反转,将删边转化为加边。
    从最开始的图中随便取出一棵生成树,假设最开始树上所有边都是白边
    此后每添加一条非树边$(u,v)$,就将树上$u-v$的路径全部染黑

  • 然后不难发现,每次询问$(u,v)$,则$u-v$路径上的白边就是关键航线,$u-v$路径上的的白边数量就是答案
    路径染色,查询路径上白边数量,不难想到用树链剖分+线段树来维护,时间复杂度$O(N\cdot log^2N)$


  • 思考一下如何不用树链剖分
    发现每条边只用被染色一次黑的染多少次都是黑的
    令白边的边权为1,黑边的边权为0
    每次添加一条非树边$(u,v)$,就将$u-v$路径上所有未染黑的边边权都-1,并将这些边染黑
    这样每次询问$(u,v)$的时候,答案就是$u-v$路径的边权和

  • 如何保证每条边只被染黑一次?
    每次染黑一条路径$u-v$的时候,用并查集将路径上所有边$(a,b)$的$father$设置为$u-v$的$LCA(u-v)$的$father$,这样下次再访问到$(a,b)$这条边的时候,直接跳过这条边,到$LCA(u-v)$处
    由于每条边只会被缩一次,所以时间复杂度均摊$O(N)$

  • 每条边用较深的那个点来表示
    例如,边$(a,b)$中,$a$为$b$的儿子
    $(a,b)$的$father$用$a$的$father$表示
    $(a,b)$的边权用$a$的点权表示

  • 这部分有点复杂,详情可以见代码


  • 还剩一个小问题:如何不用树链剖分维护单点加,路径求和
    令$L(u)$表示$u$到根的边权和
    $u-v$路径的边权和即为$L(u)+L(v)-2L(LCA(u,v))$

  • 不难发现,每次将点$u$的点权$+x$,则对于$u$子树中所有点$v$,$L(v)$会$+x$,子树外所有点$p$的$L(p)$都不变
    又因为,同一棵子树中的点的$DFS$序是连续的
    问题就转化为了区间加,单点求值

  • 将正常的树状数组询问,修改时+,-的方向反过来,就得到了
    资瓷区间加,单点求值的树状数组
    (详情请见代码)


时间复杂度$O(N\cdot logN)$,瓶颈在树状数组,倍增$LCA$,std::map

完结撒花~

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#define lb(x) (x&-x)//二进制最低位
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
int n,m,cnt,tme;//点数,边数,操作总数,DFS时间戳
int hd[30009],eg[60009],nxt[60009],tot;//存图
int dfn[30009],ed[30009],dep[30009];//依次为:DFS序,子树中DFS序最大值,节点深度
int c[30009];//树状数组
int fn[30009];//并查集数组
int f[30009][16];//倍增数组
pii e[100009],q[40009];//边集,询问
int del[100009],ont[100009];//边是否被删除,是否为生成树上的边
int typ[40009],ans[40009];//询问的种类,答案
map<pii,int> mp;//记录边的编号
void add(int x,int val)//树状数组[1,x]区间加val
{
    for(int i=x;i;i-=lb(i))
        c[i]+=val;
}
int ask(int x)//x单点求值
{
    int ans=0;
    for(int i=x;i<=n;i+=lb(i))
        ans+=c[i];
    return ans;
}
int fnd(int x)//并查集
{
    return x==fn[x]?x:fn[x]=fnd(fn[x]);
}
void ins(int a,int b)//加边
{
    eg[++tot]=b;
    nxt[tot]=hd[a];
    hd[a]=tot;
}
void dfs(int x,int fa)
{
    dep[x]=dep[fa]+1;
    ed[x]=dfn[x]=++tme;//标记DFS序
    f[x][0]=fa;//标记父亲
    for(int i=1;i<=15;i++)//预处理倍增数组
        f[x][i]=f[f[x][i-1]][i-1];
    for(int i=hd[x];i;i=nxt[i])
        if(eg[i]!=fa)//防止返祖访问
        {
            dfs(eg[i],x);
            ed[x]=max(ed[x],ed[eg[i]]);//更新ed
        }
}
int getlca(int x,int y)//倍增求LCA
{
    if(dep[x]<dep[y])
        swap(x,y);
    int l=dep[x]-dep[y];
    for(int i=0;i<=15;i++)
        if(l&(1<<i))
            x=f[x][i];
    if(x==y)
        return x;
    for(int i=15;i>=0;i--)
        if(f[x][i]!=f[y][i])
            x=f[x][i],y=f[y][i];
    return f[x][0];
}
void modify(int x,int y)//核心:并查集缩点(其实和树链剖分的修改操作很像)
{
    int fx=fnd(x),fy=fnd(y),lca=getlca(x,y);
    while(fx!=fy)
    {
        if(dep[fx]<dep[fy])//优先将深的点向上跳
            swap(fx,fy);
        if(fx!=lca)//将fx到fx父亲的边的边权-1,若fx为LCA则不用修改
        {
            add(ed[fx],-1);//树状数组区间修改
            add(dfn[fx]-1,1);//树状数组区间修改
        }
        x=fnd(f[fx][0]);//fx父亲所在集合的根
        fn[fx]=x;//将fx的根设置为fx父亲所在集合的根
        fx=x;//继续向上跳
    }
}//这里每条边只会被修改一次,所以时间复杂度均摊O(N)
int query(int x,int y)//询问u-v路径的边权和
{
    return ask(dfn[x])+ask(dfn[y])-2*ask(dfn[getlca(x,y)]);
}
void init()
{
    for(int i=1;i<=n;i++)//初始化并查集
        fn[i]=i;
    for(int i=1;i<=m;i++)//得到一棵生成树
        if(!del[i])
        {
            int a=e[i].fi,b=e[i].se;
            if(fnd(a)!=fnd(b))//若a,b不连通
            {
                ont[i]=1;//标记树边
                fn[fnd(a)]=fnd(b);//并查集合并
                ins(a,b);//加边
                ins(b,a);//加边
            }
        }
    dfs(1,0);
    for(int i=2;i<=n;i++)//将所有边的边权设为1
    {
        add(ed[i],1);//树状数组区间修改
        add(dfn[i]-1,-1);//树状数组区间修改
    }
    for(int i=1;i<=n;i++)//初始化并查集
        fn[i]=i;
    for(int i=1;i<=m;i++)//添加未被删除的非树边
        if(!del[i]&&!ont[i])
            modify(e[i].fi,e[i].se);
}
void solve()
{
    for(int i=cnt;i>=1;i--)//倒序处理操作
    {
        if(!typ[i])
            modify(q[i].fi,q[i].se);//添加非树边
        else
            ans[i]=query(q[i].fi,q[i].se);//处理询问
    }
    for(int i=1;i<=cnt;i++)//正序输出
        if(typ[i])
            printf("%d\n",ans[i]);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1,a,b;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        if(a>b)
            swap(a,b);
        e[i]=pii(a,b);
        mp[e[i]]=i;//用map记录边的编号
    }
    int c,a,b;
    scanf("%d",&c);
    while(c!=-1)
    {
        scanf("%d%d",&a,&b);
        if(a>b)
            swap(a,b);
        q[++cnt]=pii(a,b);
        typ[cnt]=c;//记录操作种类
        if(!c)
            del[mp[q[cnt]]]=1;//这条边已被删除
        scanf("%d",&c);
    }
    init();
    solve();
    return 0;
}

评论

  • chenleyu
    nb
作者: zhengrunzhe 更新时间: 2018-12-23 00:15  在Ta的博客查看 举报    1  

Tarjan:e-dcc缩点+ 树剖+线段树/并查集

先说一个比较简单的版本poj3694 Network

题意:每次增加一条边,求图中桥的数量

首先进行一遍Tarjan求出所有的边双联通分量,然后缩点成树

得出初始图的桥的数量为树的边数即tot(边双数量)-1记作ans0

考虑添加一条边(x,y) (若用dcc[i]表示编号为i所在的双联通分量的编号)

1.dcc[x]==dcc[y]

两点同处于一个边双中,显然不会对图的桥数有影响

2.dcc[x]!=dcc[y]

dcc[x]与dcc[y]路径上的所有边都不会再是桥

考虑一种暴力的做法

先求出dcc[x]与dcc[y]的lca

然后暴力从dcc[x]暴力一个个跳到lca,跳过的点(除lca)若没有被标记则标记vis[i]=1

在同样地从dcc[y]往上跳,两次过程标记到的点数则是减少的桥的数量(同时也是当前两点间桥的数量)记作△ans

每次输出ans0=ans0-△ans

不过貌似poj能给过

考虑更加优秀的做法

每次有可能会跳过已经标记过的点,考虑并查集把已经标记过的压缩起来,每次跳的时候直接跳到集合的顶端就行了

另一种做法可以利用树剖+线段树,刚开始所有树边权都为1,每次先路径求和,为减少的桥数,然后把路径上的所有边权都改为0

现在回到这道题目

题意:每次断掉一条边,求两点间桥数

同样的,如果离线操作,把所有的操作先存下来,然后倒序断掉一条边的操作就变成了增加一条边,就转化成了刚刚的那道题,两点间的桥数便是△ans

首先先建一幅由没有被断掉的边构成的图(因为保证无论航线如何被破坏,任意时刻任意两个星球都能够相互到达,所以建出的图一定连通),进行缩点成树

然后倒序处理每一个操作,这里采用线段树,断边就是加边,路径边权赋0,询问就输出路径和

可以用一个map表示边是否被断掉,由于有重边(我一开始没想重边的wa了n编),应存边(a,b)被删去的次数,因为可能有多条(a,b),对于原图中的每一条边(a,b),若map[(a,b)]>0(代表这条边会被删去)就把map[(a,b)]--,否则说明这条边不会被删去,就连接(a,b)

#include<map>
#include<stack>
#include<cstdio>
#include<algorithm>
using namespace std;
template<class type>inline const void read(type &in)
{
    in=0;char ch=getchar();short fh=1;
    while (ch<48||ch>57)fh=ch=='-'?-1:fh,ch=getchar();
    while (ch>47&&ch<58)in=(in<<3)+(in<<1)+ch-48,ch=getchar();
    in*=fh;
}
const int N=3e4+10,M=1e5+10,Q=4e4+10;
int n,m,a[M],b[M];
stack<int>ans;
map<pair<int,int>,int>e;
struct question{int u,v,type;}q[Q]; //存储每个询问信息
class Edge
{
    private:
        int cnt;
    public:
        int head[N],to[M<<1],next[M<<1];
        inline const void addedge(int u,int v)
        {
            next[++cnt]=head[u];
            head[u]=cnt;
            to[cnt]=v;
        }
        inline const void connect(int u,int v)
        {
            addedge(u,v);
            addedge(v,u);
        }
}g,t;
class Double_Connected_Component //边双处理
{
    private:
        stack<int>s;
        int dfn[N],low[N],cnt;
    public:
        int dcc[N],tot;
    protected:
        inline const void tarjan(int u,int fa)
        {
            dfn[u]=low[u]=++cnt;s.push(u);int v;
            for (int i=g.head[u];i;i=g.next[i])
                if ((v=g.to[i])!=fa)
                    if (!dfn[v])tarjan(v,u),low[u]=min(low[u],low[v]);
                    else if (!dcc[v])low[u]=min(low[u],dfn[v]);
            if (low[u]!=dfn[u])return;tot++;
            do v=s.top(),s.pop(),dcc[v]=tot;while (u!=v);
        }
    public:
        inline const void tarjan()
        {
            for (int i=1;i<=n;i++)
                if (!dfn[i])
                    tarjan(i,0);
        }
        inline const void rebuild() //缩点成树
        {
            for (int i=1;i<=n;i++)
                for (int u,v,j=g.head[i];j;j=g.next[j])
                    if ((u=dcc[i])!=(v=dcc[g.to[j]]))
                        t.addedge(u,v);
        }
}dcc;
class Segment_Tree  //线段树(指针)
{
    private:
        struct tree
        {
            int sum;
            bool tag;
            tree *lson,*rson;
            inline const void pushup()
            {
                sum=lson->sum+rson->sum;
            }
            inline const void cover()
            {
                tag=1;sum=0;
            }
            inline const void pushdown()
            {
                if (!tag)return;
                lson->cover();
                rson->cover();
                tag=0;
            }
            inline const void update(int l,int r,int L,int R)
            {
                if (l>R||r<L)return;
                if (l>=L&&r<=R)return cover();
                pushdown();
                int mid=l+r>>1;
                lson->update(l,mid,L,R);
                rson->update(mid+1,r,L,R);
                pushup();
            }
            inline const int query(int l,int r,int L,int R)
            {
                if (l>R||r<L)return 0;
                if (l>=L&&r<=R)return sum;
                pushdown();
                int mid=l+r>>1;
                return lson->query(l,mid,L,R)+rson->query(mid+1,r,L,R);
            }
        }memory_pool[N<<2],*tail;
        inline const void init()
        {
            tail=memory_pool;
        }
        inline tree *spawn()
        {
            tree *p=tail++;
            p->tag=p->sum=0;
            p->lson=p->rson=NULL;
            return p;
        }
    public:
        tree *root;
        inline Segment_Tree(){init();}
        inline const void build(tree *&p,int l,int r)
        {
            p=spawn();
            if (l==r)return (void)(p->sum=(l!=1)); //边权转点权,1号点(根节点)上面没有边,权值为0
            int mid=l+r>>1;
            build(p->lson,l,mid);
            build(p->rson,mid+1,r);
            p->pushup();
        }
}sgt;
class Heavy_Light_Decomposition //树剖
{
    private:
        int size[N],top[N],fa[N],dep[N],dfn[N],wson[N],cnt;
    public:
        inline const void dfs(int p)
        {
            size[p]=1;
            for (int i=t.head[p];i;i=t.next[i])
            {
                int son=t.to[i];
                if (son==fa[p])continue;
                fa[son]=p;dep[son]=dep[p]+1;
                dfs(son);size[p]+=size[son];
                if (size[son]>size[wson[p]])wson[p]=son;
            }   
        }
        inline const void dfs(int p,int tp)
        {
            top[p]=tp;dfn[p]=++cnt;
            if (wson[p])dfs(wson[p],tp);
            for (int son,i=t.head[p];i;i=t.next[i])
                if (!dfn[son=t.to[i]])
                    dfs(son,son);
        }
        inline const void update(int a,int b)
        {
            while (top[a]^top[b])
            {
                if (dep[top[a]]<dep[top[b]])swap(a,b);
                sgt.root->update(1,dcc.tot,dfn[top[a]],dfn[a]);
                a=fa[top[a]];
            }
            if (dep[a]>dep[b])swap(a,b);
            sgt.root->update(1,dcc.tot,dfn[a]+1,dfn[b]);
        }
        inline const int query(int a,int b)
        {
            int ans=0;
            while (top[a]^top[b])
            {
                if (dep[top[a]]<dep[top[b]])swap(a,b);
                ans+=sgt.root->query(1,dcc.tot,dfn[top[a]],dfn[a]);
                a=fa[top[a]];
            }
            if (dep[a]>dep[b])swap(a,b);
            return ans+sgt.root->query(1,dcc.tot,dfn[a]+1,dfn[b]);
        }
}hld;
int main()
{
    read(n);read(m);
    for (int i=1;i<=m;i++)read(a[i]),read(b[i]);
    int qtot;
    for (qtot=1;read(q[qtot].type),~q[qtot].type;qtot++)
    {
        read(q[qtot].u);read(q[qtot].v);
        if (q[qtot].type)continue;
        e[make_pair(q[qtot].u,q[qtot].v)]++;
        e[make_pair(q[qtot].v,q[qtot].u)]++; //无向图,反过来的也要更改
    }
    for (int i=1;i<=m;i++)
        if (e.find(make_pair(a[i],b[i]))!=e.end()&&e[make_pair(a[i],b[i])])
            e[make_pair(a[i],b[i])]--,e[make_pair(b[i],a[i])]--;
        else g.connect(a[i],b[i]);
    dcc.tarjan();dcc.rebuild();
    hld.dfs(1);hld.dfs(1,1);
    sgt.build(sgt.root,1,dcc.tot);
    for (int i=qtot-1;i;i--)
        if (q[i].type)ans.push(hld.query(dcc.dcc[q[i].u],dcc.dcc[q[i].v])); //由于是倒序处理,所以输出也要倒过来,因为tarjan缩点的时候会用到栈,干脆也用栈来实现倒序好了
        else hld.update(dcc.dcc[q[i].u],dcc.dcc[q[i].v]);
    while (ans.size())printf("%d\n",ans.top()),ans.pop();
    return 0;
}
 
反馈
如果你认为某个题解有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。