题目:https://www.acwing.com/problem/content/230/
题意:有一个图,每条边有一个权值,现在求1-n的一条路径的最大异或和,一条边能经过多次,相应的也要计算那么多次权值
思路:首先最大异或和一看就是线性基的经典操作,然后主要是我们要如何确定这条路径,
我们首先随便计算出一条1-n路径上的最大异或和,然后再是一些环,因为一条路径异或上其他的环的话就是变成了一条新的路径
所以我们只要dfs出一条路径,然后存下所有的环,我们把这些环跑个线性基,然后就可以利用线性基的性质,如果异或当前基,会使值更大,就选,因为每个位只有一个值
1,然后说下离开始求得1-n路径上很远的环为什么也可以使用,因为我们以一点出发走过那个环再原路返回,相当于我们把去的路又异或没有了,只有环的值,现在我们只要
2,我们最开始选取的路径是否会影响最优问题,答案是不会,为什么呢,因为这条路径可以通过异或一些环来得到其他路径,所以这个不是问题
最后说下有个很坑的地方,你的记录环的个数那个数组要开很大,因为环的数量太多了
#include<bits/stdc++.h> #define maxn 250005 #define mod 1000000007 using namespace std; typedef long long ll; int n,m,cnt; bool vis[maxn]; ll d[maxn],a[maxn],ins[100]; vector<pair<ll,ll> > mp[maxn]; void dfs(ll x){ vis[x]=1; for(int i=0;i<mp[x].size();i++){ pair<ll,ll> q=mp[x][i]; if(!vis[q.first]){ d[q.first]=d[x]^q.second; dfs(q.first); } else{ a[++cnt]=d[q.first]^d[x]^q.second; } } } void solve(){ for(int i=1;i<=cnt;i++) { for(int j=63;j>=0;j--) { if((a[i]>>j)&1) { if(!ins[j]) { ins[j]=a[i]; break; } else a[i]^=ins[j]; } } } ll ans=d[n]; for(int i=63;i>=0;i--){ if((ans^ins[i])>ans) ans^=ins[i]; } printf("%lld",ans); } int main(){ scanf("%d%d",&n,&m); ll x,y; ll z; for(int i=0;i<m;i++){ scanf("%lld%lld%lld",&x,&y,&z); mp[x].push_back(make_pair(y,z)); mp[y].push_back(make_pair(x,z)); } dfs(1); solve(); return 0; }