异或

题目链接

题意

给一个带边权的无向联通图（5e4个点）。
x到y的路径距离定义为x点到y点的路径上的边权异或和。
问从1到n的最远路径是多少（异或和）。
一个边、点可以走无数次。

题解。

题解很聪明，而我很笨拙 hhhhhh
因为要求1~n的路径上的边权异或和最大。
1、如果有环，如果想要这个权值，那么这个环的权值一定是取的。
因为是异或，所以

这样走，会发现只多了一个环的贡献。
2、可以选一个从1~n的路径然后从环里面选几个使得异或最大。
为什么可以这样？
因为如果只有这一条路径从1~n。那么答案就是那个。
如果有其他路径，那么一定会构成环！！（因为是无向图）
构成环，在上面已经统计过了，如果选环上的另一条的答案更优，这条路径异或环的路径，得到的就是另一个路径的答案。！很nice

于是题目就变成了从一些值中选出来几个，与路径的值异或，使答案最大。
这个可以用线性基。
so~ 我为什么就想不到呢，我好菜。

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <cmath>
#include <set>
#include <cstring>
#include <string>
#include <bitset>
#include <stdlib.h>
#include <time.h> 
using namespace std;
typedef long long ll;
typedef pair<int,ll> pii;
typedef unsigned long long ull;
#define st first
#define sd second
#define mkp make_pair
#define pb push_back
void wenjian(){
   freopen("concatenation.in","r",stdin);freopen("concatenation.out","w",stdout);}
void tempwj(){
   freopen("hash.in","r",stdin);freopen("hash.out","w",stdout);}
ll gcd(ll a,ll b){
   return b == 0 ? a : gcd(b,a % b);}
ll qpow(ll a,ll b,ll mod){
   a %= mod;ll ans = 1;while(b){
   if(b & 1)ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans;}
struct cmp{
   bool operator()(const pii & a, const pii & b){
   return a.second > b.second;}};
int lb(int x){
   return  x & -x;}

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9+7;
const int maxn = 5e4+5;
std::vector<pii> vv[maxn];
ll dis[maxn];
int vis[maxn];
ll a[maxn];
void add(ll num)
{
   
	for (int i = 62; i >= 0; i -- )
	{
   
		if((num >> i) & 1)
		{
   
			// ll x = 3;
			// printf("%lld %d %lld %d %d %lld\n",num,i,num >> i,3 >> i,i,x >> 64);
			if(a[i] == 0)
			{
   
				a[i] = num;
				return;
			}
			else
			{
   
				num ^= a[i];
			}
		}
	}
}

void dfs(int x,ll num,int fa)
{
   
	// printf("%d %d\n",x,num);
	dis[x] = num;
	vis[x] = 1;
	for (int i =0 ; i< vv[x].size(); i ++ )
	{
   
		pii t = vv[x][i];
		if(t.st == fa)
			continue;
		if(vis[t.st])
		{
   
			// printf("%lld %d %d 11111111111111\n",num ^ t.sd ^ dis[t.st],t.st,x);
			add(num ^ t.sd ^ dis[t.st]);
		}
		else
			dfs(t.st,num ^ t.sd,x);
	}
}


int main()
{
   
	// printf("%d\n",3 >> 64);
	int n,m;
	scanf("%d%d",&n,&m);
	for (int i =1; i <= m; i ++ )
	{
   
		int x,y;
		ll val;
		scanf("%d%d%lld",&x,&y,&val);
		vv[x].pb(mkp(y,val));
		vv[y].pb(mkp(x,val));
	}
	dfs(1,0,0);
	ll x = dis[n];
	 // printf("%lld\n",x);
	for (int  i= 64 ; i >= 0; i -- )
	{
   
		if(a[i])
		{
   
			// printf("%lld %d\n",a[i],i);
			x = max(x,x ^ a[i]);
		}
	}
	printf("%lld\n",x);
}