题解
考虑到如果图中存在一些环,那么我们就可以在不影响其它值的情况下获得这些环上的值。
具体证明:
考虑到我们从1点出发经过一些点以后我们可以到达环到链条的起点v,然后我们经过环又回到v,这样我们的取值就是从1-v路径上的值异或上环上的值,然后我们回到1,根据异或的性质,相当于我们取得了环上的值,所以我们把所有环上的值加入到一个线性基上,然后把任意一条1-n路上上的值异或线性基上的值取最大值,任意一条就好了,因为如果有多条从1-n的路径那么就形成了环,必定被包含在了线性基上。
#include <bits/stdc++.h>
const int MAXN = 100000;
using namespace std;
int n,m;
bool vis[MAXN];
long long d[MAXN],res[MAXN];
vector<pair<int,long long> >E[MAXN];
void insert(long long c){
bitset<63>bit = c;
for(int i = 62;i >= 0;i--){
if(!bit[i]) continue;
if(!d[i]) {
d[i] = c;
return;
}
else {
c ^= d[i];
bit = c;
}
}
}
void dfs(int u,long long ret){
res[u] = ret;vis[u] = true;
for(auto tmp : E[u]){
int v = tmp.first;
long long c = tmp.second;
if(!vis[v]) dfs(v,ret^c);
else insert(res[u]^res[v]^c);
}
}
int main(){
//freopen("test.in","r",stdin);
scanf("%d %d",&n,&m);
long long u,v,c;
for(int i = 1;i <= m;i++){
scanf("%lld %lld %lld",&u,&v,&c);
E[u].push_back(make_pair(v,c));
E[v].push_back(make_pair(u,c));
}
dfs(1,0);
long long ret = res[n];
for(int i = 62;i >= 0;i--)
if((ret^d[i]) > ret)
ret ^= d[i];
printf("%lld",ret);
return 0;
}