這道題要求從1到n的最大xor和路徑，存在重邊，允許經過重復點、重復邊。

第一行包含兩個整數N和 M， 表示該無向圖中點的數目與邊的數目。 接下來M 行描述 M 條邊，每行三個整數Si，Ti ，Di，表示 Si 與Ti之間存在 一條權值為 Di的無向邊。 圖中可能有重邊或自環。

輸出：僅包含一個整數，表示最大的XOR和（十進制結果）?

輸入

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

輸出

6
題目要求很清楚，看了大佬的博客，
不過還是自己手寫一下思路吧。
可以從1道n隨意找一條路徑然后求出他的初始的異或和,作為初始值。
然后找到所有的環。。
題解
題解
?

我們考慮如何得到答案，首先所有的環都是可以經過的。這是為什么呢？
一個邊權為非負整數的無向連通圖,節點編號為1到N,試求出一條從1號節點到N號節點的路徑,使得路徑上經過的邊得權值的XOR和最大.
假設我們從1號點開始走，走到一個環的起點，然后我們經過這個環以后回到了環的起點，這時我們可以直接回到起點。這樣，除了環上的路徑，其他的路徑都被抵消了。

那么我們就只選了了這個環，也就是說，任意一個環都是可以選的。
然后我們先把所有的環都選出來，選入線性基中，再選出任意一條從1到n的路徑，作為初始ans。初始ans異或線性基的最大值就是我們求的答案。為什么任意選一條路徑也是可行的呢？
我們選了一條路徑以后，如果存在一條更優的路徑，那么這兩條路徑肯定是構成一個環的，會被選入線性基中。那么我們再用初始的ans異或一下這個環，我們就會發現，初始的ans被抵消了，二更優的那條路徑留了下來。所以，我們選一個任意的初始ans是可行的。
于是這道題的實現就很明顯了。先找出所有環，構成線性基，然后找出初始ans。這兩步顯然是可以dfs一遍一起搞的。然后用ans去異或線性基。從高位開始往低位異或。如果當前ans異或這一位的數能使ans變大，那么就異或。最終得到的ans就是我們要求的答案。

所以根據這題，我們得到一個結論：任意一條1到n的路徑的異或和，都可以由任意一條1到n的路徑的異或和和一些環的異或和來組合得到。

?

#include<bits/stdc++.h> #include <iostream> #include <cmath> #include <cstdio> #include <stdlib.h> #include <ctime> using namespace std; typedef long long ll; typedef pair<int,int> PII; const int inf = 0x3f3f3f3f; const int mod = 1e9+7; const int maxn = 1e6 + 5; using namespace std; int n,m; struct Point{ll next,to,val; }edge[maxn*2]; ll head[maxn],cnt; ll cnn;//成環的個數 ll a[maxn];//線性基 ll A[maxn];//成環的點 ll d[maxn];//環中到i點的異或和 bool vis[maxn];//訪問標記 void init(){memset(head,0,sizeof(head));memset(vis,false,sizeof(0));memset(A,0,sizeof(A));cnt=0;cnn=0; } void add(ll u,ll v,ll w) {cnt++;edge[cnt].to=v;edge[cnt].val=w;edge[cnt].next=head[u];head[u]=cnt; } void dfs(int u) {vis[u]=true;for(int i=head[u];i;i=edge[i].next){int v=edge[i].to;if(!vis[v]){d[v]=d[u]^edge[i].val;dfs(v);}elseA[cnn++]=d[u]^d[v]^edge[i].val;//環的權值} } void build(ll p) {for(int i=62;i>=0;--i){if(p>>i&1)//if(p&ll(1ll<i)){if(a[i]==0){a[i]=p;break;}p^=a[i];}} } ll query_max() {ll ans=d[n];for(int i=62;i>=0;--i){if((ans^a[i])>ans)ans^=a[i];}return ans; } int main() {ll u,v,w;while(scanf("%d%d",&n,&m)!=EOF){init();for(int i=0;i<m;++i){scanf("%lld%lld%lld",&u,&v,&w);add(u,v,w),add(v,u,w);}dfs(1);for(int i=0;i<cnn;++i)build(A[i]);ll ans=query_max();cout<<ans<<endl;}return 0; }

?

總結

以上是生活随笔為你收集整理的【bzoj21115 [Wc2011] Xor 带全无向图中1道n经过路径权值的最大异或和(含有环）】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。