bzoj 2155 Xor-白红宇

bzoj 2155 Xor

阅读量：4878 次

发布时间：2019-06-11

本文共 1723 字，大约阅读时间需要 5 分钟。

题目大意：

求一条从$1 \rightarrow n$的路径是异或和最大

思路：

先随便求一棵生成树，然后求出所有环，对于所有环都可以去转一圈只取到这个环的贡献

那么就是线性基裸题了

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              10 #include
               
                11 #define ll long long12 #define db double13 #define inf 213906214314 #define MAXN 5010015 #define MOD 99824435316 #define maxi 123456789123456789LL17 #define rep(i,s,t) for(register int i=(s),i##__end=(t);i<=i##__end;++i)18 #define dwn(i,s,t) for(register int i=(s),i##__end=(t);i>=i##__end;--i)19 #define ren for(register int i=fst[x];i;i=nxt[i])20 #define pb(i,x) vec[i].push_back(x)21 #define pls(a,b) (a+b)%MOD22 #define mns(a,b) (a-b+MOD)%MOD23 #define mul(a,b) (1LL*(a)*(b))%MOD24 using namespace std;25 inline ll read()26 {27 ll x=0,f=1;char ch=getchar();28 while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}29 while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}30 return x*f;31 }32 ll p[70],dis[MAXN],val[MAXN<<2];33 int n,m,fst[MAXN],to[MAXN<<2],nxt[MAXN<<2],cnt,vis[MAXN];34 void add(int u,int v,ll w) {nxt[++cnt]=fst[u],fst[u]=cnt,to[cnt]=v,val[cnt]=w;}35 void ins(ll x) {dwn(i,63,0) if((x>>i)&1){ if(!p[i]){p[i]=x;break;}x^=p[i];};}36 ll query(ll x) {ll res=x;dwn(i,63,0) res=max(res,res^p[i]);return res;}37 void dfs(int x)38 {39 vis[x]=1;ren if(!vis[to[i]]) dis[to[i]]=dis[x]^val[i],dfs(to[i]);40 else ins(dis[x]^dis[to[i]]^val[i]);41 }42 int main()43 {44 n=read(),m=read();int a,b;ll c;45 rep(i,1,m) a=read(),b=read(),c=read(),add(a,b,c),add(b,a,c);46 dfs(1);printf("%lld\n",query(dis[n]));47 }