【BZOJ2115】【WC2011】最大XOR和路径

没学线性基今日考试爆炸的选手

为什么每次都是一考完发现刷题列表的下几个就是考的。。

线性基其实不难。。大概就是高斯消元一样的东西

这道题首先对第一个点dfs构一棵dfs树，那么上面会挂一些环

会发现在这个树上的xor有一个神奇的性质：选择其中的一个环并异或到当前异或和中，相当于反选了一些路径而用另外一些路径代替

那么答案就是在dfs树中n点到1点的异或和再异或上若干个环的异或和

这里犯了一个错误。。我允许了不选1到n的异或和。。

// <2115.cpp> - Wed Aug  3 16:26:56 2016
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int gi(){
    int res=0,fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return fh*res;
}
lol gl(){
    lol res=0,fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return fh*res;
}
const int MAXN=50010;
const int MAXM=200010;
const int INF=1e9;
int bt=1,b[MAXN],next[MAXM],to[MAXM];lol val[MAXM];
inline void add(lol z,int y,int x){
    next[++bt]=b[x];b[x]=bt;to[bt]=y;val[bt]=z;
    next[++bt]=b[y];b[y]=bt;to[bt]=x;val[bt]=z;
}
bool vis[MAXN];
lol dis[MAXN],h[MAXM];
int tot;
void dfs(int x,int f){
    vis[x]=1;
    for(int i=b[x];i;i=next[i]){
        if((i^f)==1)continue;
        if(vis[to[i]]){
            if(i&1)h[++tot]=dis[x]^dis[to[i]]^val[i];
            continue;
        }
        dis[to[i]]=dis[x]^val[i];
        dfs(to[i],i);
    }
}
int main(){
    int n=gi(),m=gi();
    for(int i=1;i<=m;i++)add(gl(),gi(),gi());
    dfs(1,0);
    lol ans=dis[n];
    for(lol p=1ll<<62;p;p>>=1){
        int fd=0;
        for(int i=1;i<=tot;i++)
            if(h[i]&p)
                if(fd)h[i]^=h[fd];
                else fd=i;
        if(fd&&!(ans&p))ans^=h[fd];
        h[fd]=0;
    }
    printf("%lld\n",ans);
    return 0;
}

// <2115.cpp> - Wed Aug 3 16:26:56 2016

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int gi(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

lol gl(){

lol res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int MAXN=50010;

const int MAXM=200010;

const int INF=1e9;

int bt=1,b[MAXN],next[MAXM],to[MAXM];lol val[MAXM];

inline void add(lol z,int y,int x){

next[++bt]=b[x];b[x]=bt;to[bt]=y;val[bt]=z;

next[++bt]=b[y];b[y]=bt;to[bt]=x;val[bt]=z;

}

bool vis[MAXN];

lol dis[MAXN],h[MAXM];

int tot;

void dfs(int x,int f){

vis[x]=1;

for(int i=b[x];i;i=next[i]){

if((i^f)==1)continue;

if(vis[to[i]]){

if(i&1)h[++tot]=dis[x]^dis[to[i]]^val[i];

continue;

}

dis[to[i]]=dis[x]^val[i];

dfs(to[i],i);

}

int main(){

int n=gi(),m=gi();

for(int i=1;i<=m;i++)add(gl(),gi(),gi());

dfs(1,0);

lol ans=dis[n];

for(lol p=1ll<<62;p;p>>=1){

int fd=0;

for(int i=1;i<=tot;i++)

if(h[i]&p)

if(fd)h[i]^=h[fd];

else fd=i;

if(fd&&!(ans&p))ans^=h[fd];

h[fd]=0;

}

printf("%lld\n",ans);

return 0;

}