BZOJ2322:[BeiJing2011]梦想封印(&&BZOJ3793) 线性基

思路:

首先必定是离线处理了.

然后呢,根据WC2011的最大异或和路径这道题目的做法,我们显然应该分成拆分成路径和环进行处理.

由于题目规定的是,从1开始的任意路径,所以我们得处理出从1开始到所有点结束时的异或和.

如果只是单独求一次的话怎么搞呢?

把所有的从起点开始的简单路径的异或和拿出来.

然后再把所有的简单环的异或和拿出来,搞成一个线性基.令线性基中有\(k\)个元素.

考虑一种算法,我们把所有简单路径都放在线性基中处理一下得到\(2^k\)种方案,但是会有重复!

若两条简单路径的异或和在线性基中消元之后的结果相同,那么这两个\(2^k\)种方案必定存在一一映射.(这个暂时不太会证,不过好像显然?)

至于不能为0的限制,就简单处理一下就好了.

可是现在要支持动态加边.

考虑加入一条边的影响.假设现在已经有一个线性基,以及若干在当前线性基下消元后不同的的若干简单路径.

加入一条边可能拓展从起点开始的有根生成树,从而多出一些简单路径,我们要尝试加入简单路径中;也可能多出一些新的环,我们要用这个去更新线性基.

这就是大体思路.

关键是维护不同的简单路径以及生成树.参考的Kanari神犇的代码.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
 
typedef long long LL;
 
namespace Fio{
    inline int getc(){
        static const int L=1<<15;static char buf[L],*fS=buf,*fT=buf;
        if(fS==fT){fT=(fS=buf)+fread(buf,1,L,stdin);if(fS==fT)return EOF;}
        return*fS++;
    }
    inline bool digit(char c){return c>='0'&&c<='9';}
    template<typename T>inline void Get(T&x){
        int c;while(!digit(c=getc()));x=c-'0';while(digit(c=getc()))x=(x<<1)+(x<<3)+c-'0';
    }
    char buf[20010*20],*o=buf;
    template<typename T>inline void print(T x){
        static int stk[100];int top=0;
        if(!x)*o++=48;else{for(;x;x/=10)stk[++top]=x%10;for(int i=top;i>=1;--i)*o++=48+stk[i];}
        *o++='\n';
    }
    inline void final(){fwrite(buf,1,o-buf,stdout);}
}
 
#define N 5010
#define M 20010
#define Q 20010
int n,m,q;
struct Edge{
    int u,v;LL l;bool ban;
    Edge(){}
    Edge(int _u,int _v,LL _l):u(_u),v(_v),l(_l){}
}E[M];
 
int head[N],next[M<<1],end[M<<1],ban[M<<1];LL len[M<<1];
inline void addedge(int a,int b,LL c){static int q=1;end[q]=b,next[q]=head[a],head[a]=q,len[q++]=c;}
inline void make(int a,int b,LL c){addedge(a,b,c),addedge(b,a,c);}
 
int seq[Q];
 
LL ins[64];int nums;
LL calc(LL x){
    for(int i=63;i>=0;--i)if((x>>i)&1)x^=ins[i];return x;
}
void insert(LL x){
    for(int i=63;i>=0;--i)if((x>>i)&1){
        if(!ins[i]){ins[i]=x,++nums;break;}else x^=ins[i];
    }
}
 
bool vis[N];LL w[N];
 
map<LL,int>S;int stk[N],top,sstk[N],stop;
 
int sav[N],get;
inline void setinqueue(){
    S.clear();stop=0;
    for(int i=1;i<=top;++i){
        int tmp=calc(w[stk[i]]);
        if(S[tmp]==0)S[tmp]=1,sstk[++stop]=stk[i];
    }
    for(int i=1;i<=get;++i){
        int tmp=calc(w[sav[i]]);
        if(S[tmp]==0)S[tmp]=1,sstk[++stop]=sav[i];
    }
    top=stop,memcpy(stk+1,sstk+1,stop*sizeof(int));
}
 
void extend(int x){
    vis[x]=1;if(x==1)sav[++get]=1;
    for(int j=head[x];j;j=next[j]){
        if(!vis[end[j]]){
            w[end[j]]=w[x]^len[j];
            sav[++get]=end[j];
            extend(end[j]);
        }
        else insert(w[x]^w[end[j]]^len[j]);
    }
}
 
LL getans(){
    return(1LL<<nums)*(top-1)+(1LL<<nums)-1;
}
 
LL res[Q];
int main(){
#ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
#endif
    Fio::Get(n),Fio::Get(m),Fio::Get(q);register int i;
    for(i=1;i<=m;++i)Fio::Get(E[i].u),Fio::Get(E[i].v),Fio::Get(E[i].l);
     
    for(i=1;i<=q;++i)Fio::Get(seq[i]),E[seq[i]].ban=1;
    for(i=1;i<=m;++i)if(!E[i].ban)make(E[i].u,E[i].v,E[i].l);
     
    get=0;extend(1);setinqueue();
     
    for(i=q;i>=0;--i){
        res[i]=getans();
         
        if(i==0)break;
        make(E[seq[i]].u,E[seq[i]].v,E[seq[i]].l);
        get=0;
        if(vis[E[seq[i]].u]&&vis[E[seq[i]].v])insert(w[E[seq[i]].u]^w[E[seq[i]].v]^E[seq[i]].l);
        else if(vis[E[seq[i]].u])extend(E[seq[i]].u);
        else if(vis[E[seq[i]].v])extend(E[seq[i]].v);
        setinqueue();
    }
     
    for(i=0;i<=q;++i)Fio::print(res[i]);
     
    return Fio::final(),0;
}