BZOJ2322:[BeiJing2011]梦想封印(&&BZOJ3793) 线性基
思路:
首先必定是离线处理了.
然后呢,根据WC2011的最大异或和路径这道题目的做法,我们显然应该分成拆分成路径和环进行处理.
由于题目规定的是,从1开始的任意路径,所以我们得处理出从1开始到所有点结束时的异或和.
如果只是单独求一次的话怎么搞呢?
把所有的从起点开始的简单路径的异或和拿出来.
然后再把所有的简单环的异或和拿出来,搞成一个线性基.令线性基中有k个元素.
考虑一种算法,我们把所有简单路径都放在线性基中处理一下得到2k种方案,但是会有重复!
若两条简单路径的异或和在线性基中消元之后的结果相同,那么这两个2k种方案必定存在一一映射.(这个暂时不太会证,不过好像显然?)
至于不能为0的限制,就简单处理一下就好了.
可是现在要支持动态加边.
考虑加入一条边的影响.假设现在已经有一个线性基,以及若干在当前线性基下消元后不同的的若干简单路径.
加入一条边可能拓展从起点开始的有根生成树,从而多出一些简单路径,我们要尝试加入简单路径中;也可能多出一些新的环,我们要用这个去更新线性基.
这就是大体思路.
关键是维护不同的简单路径以及生成树.参考的Kanari神犇的代码.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 | #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; } |