夏晓光(loveJY)的博客

首先我们随便走走会发现如果我们走了重复路,就会消掉那一段,而走重复路的先决条件是走一个环

所以我们可以考虑线性基

就是找出所有环把他们的异或值当做元素

然后我们随便找到一条合法的路径,拿他去跑线性基,跑出最大值

然后得到的就是答案qaq

正确性是我们这样每条边在环内的都一定被计入了

而所有的环都能被用这样的环异或出来

同时我们一定存在一条路径可以做到把各个元素异或上

code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e5 + 7;
const int MAXM = 2e5 + 7;
int ccnt, home[MAXN], nxt[MAXM], to[MAXM], vis[MAXN];
int n, m;
ll a[MAXN], c[MAXN], ans, w[MAXM];
inline void ct(int x, int y, ll z) {
	ccnt++;
	nxt[ccnt] = home[x];
	home[x] = ccnt;
	to[ccnt] = y;
	w[ccnt] = z;
}

inline void ins(ll x) {
	// printf("!!%lld?\n", x);
	for(ll i = 63; i >= 0; --i) {
		// if(x == 1115964016452419888)
		// printf("%lld\n", i);
		if(x >> i & 1) {
			// if(x == 1115964016452419888)
			// 	printf("%lld?%lld %lld?%lld\n", x, i, c[i], x ^ c[i]);
			if(c[i]) {
				x = x ^ c[i];
			} else {
				c[i] = x;
				break;
			}
			// puts("qwq");
		}
		// puts("??");
	}
	// puts("qwq");
	return ;
}

inline void dfs(int u, int F) {
	vis[u] = 1;
	// printf("%d %d\n", u, F);
	for(int i = home[u]; i; i = nxt[i]) {
		int v = to[i];
		if(v == F)continue;
		if(!vis[v]) {
			a[v] = a[u] ^ w[i];
			dfs(v, u);
		} else
			ins(w[i]^a[u]^a[v]);
	}
	// puts("exit");
	return ;
}

int main() {
	scanf("%d%d", &n, &m);
	ll z = 0;
	for(int i = 1, x, y; i <= m; ++i) {
		scanf("%d%d%lld", &x, &y, &z);
		ct(x, y, z);
		ct(y, x, z);
	}
	dfs(1, 0);
	// puts("qwq");
	ans = a[n];
	// printf("%lld?\n", ans);
	for(ll i = 63; i >= 0; --i) {
		if((ans ^ c[i]) > ans) {
			// printf("%lld %lld\n", i, c[i]);
			ans = ans ^ c[i];
		}
	}
	printf("%llu\n", ans);
	return 0;
}