【bzoj2115】[Wc2011] Xor【高斯消元】

题目大意：给出一个无向有权图，找出一条从1到n的路径，使得路径上权值的异或和最大，路径可以重复走

Input

第一行包含两个整数N和 M，表示该无向图中点的数目与边的数目。接下来M 行描述 M 条边，每行三个整数Si，Ti ，Di，表示 Si 与Ti之间存在一条权值为 Di的无向边。图中可能有重边或自环。

Output

仅包含一个整数，表示最大的XOR和（十进制结果）。

Sample Input

5 7
1 2 2
1 3 2
2 4 1
2 5 1
4 5 3
5 3 4
4 3 2

Sample Output

思路:有空补

#include<cstdio>

#include<string.h>

#include<iostream>

#include<algorithm>

#define maxn 400009

#define LL long long

using namespace std;

LL head[maxn],next[maxn],point[maxn],value[maxn];

LL now,cir[maxn],xo[maxn],h,n,m,bin[maxn];

bool visit[maxn];

void add(int x,int y,LL v){

next[++now]=head[x];head[x]=now;

point[now]=y;value[now]=v;

}

void dfs(int k)

{

visit[k]=1;

for(int i=head[k];i;i=next[i]){

int u=point[i];

if(visit[u]==1)cir[++h]=xo[u]^xo[k]^value[i];

else xo[u]=xo[k]^value[i],dfs(u);

}

int main()

{

LL x,y,v;cin>>n>>m;

for(int i=1;i<=m;i++){

cin>>x>>y>>v;

add(x,y,v);add(y,x,v);

}dfs(1);bin[1]=1;

for(int i=2;i<=61;i++)bin[i]=bin[i-1]<<1;

int now=0;

for(int i=61;i>=1;i--)

{

int idx=now+1;

while((cir[idx]&bin[i])==0 && idx<=h)idx++;

if(idx==h+1)continue;

now++;

swap(cir[idx],cir[now]);

for(int j=1;j<=h;j++)if((cir[j]&bin[i])!=0 && j!=now)cir[j]^=cir[now];

}

for(int i=1;i<=h;i++)if((xo[n]^cir[i])>xo[n])xo[n]=xo[n]^cir[i];

cout<<xo[n]<<endl;

return 0;

}

巴特西

【bzoj2115】[Wc2011] Xor【高斯消元】

最新文章

热门文章