//bzoj上的題面太丑了，導致VJ的題面也很丑，于是這題用洛谷的題面

題面描述

XOR（異或）是一種二元邏輯運算，其運算結果當且僅當兩個輸入的布爾值不相等時才為真，否則為假。 XOR 運算的真值表如下（\(1\) 表示真， \(0\) 表示假）：

而兩個非負整數的 XOR 是指將它們表示成二進制數，再在對應的二進制位進行 XOR 運算。

譬如 \(12\) XOR \(9\) 的計算過程如下：

故 \(12\) XOR \(9\) = 5$。

容易驗證， XOR 運算滿足交換律與結合律，故計算若干個數的 XOR 時，不同的計算順序不會對運算結果造成影響。從而，可以定義 \(K\) 個非負整數 \(A_1，A_2，……，A_{K-1}，A_K\)的 XOR 和為

\(A_1\) XOR \(A_2\) XOR …… XOR \(A_{K-1}\) XOR \(A_K\)

考慮一個邊權為非負整數的無向連通圖，節點編號為 \(1\) 到 \(N\)，試求出一條從 \(1\) 號節點到 \(N\) 號節點的路徑，使得路徑上經過的邊的權值的 XOR 和最大。

路徑可以重復經過某些點或邊，當一條邊在路徑中出現了多次時，其權值在計算 XOR 和時也要被計算相應多的次數，具體見樣例。

輸入格式

輸入文件 xor.in 的第一行包含兩個整數 \(N\) 和 \(M\)， 表示該無向圖中點的數目與邊的數目。

接下來 \(M\) 行描述 \(M\) 條邊，每行三個整數 \(S_i\)， \(T_i\) ， \(D_i\)， 表示 \(S_i\) 與 \(T_i\) 之間存在一條權值為 \(D_i\) 的無向邊。

圖中可能有重邊或自環。

輸出格式

輸出文件 xor.out 僅包含一個整數，表示最大的 XOR 和（十進制結果）。

輸入輸出樣例

輸入 #1

5 71 2 21 3 22 4 12 5 14 5 35 3 44 3 2

輸出 #1

6

說明/提示

【樣例說明】

如圖，路徑\(1 \rightarrow 2 \rightarrow 4 \rightarrow 3 \rightarrow 5 \rightarrow 2 \rightarrow 4 \rightarrow 5\)對應的XOR和為

\(2\) XOR \(1\) XOR \(2\) XOR \(4\) XOR \(1\) XOR \(1\) XOR \(3 = 6\)

當然，一條邊數更少的路徑\(1 \rightarrow 3 \rightarrow 5\)對應的XOR和也是\(2\) XOR \(4 = 6\)。

【數據規?！?/p>

對于 \(20 \%\) 的數據，\(N \leq 100，M \leq 1000，D_i \leq 10^{4}\)；

對于 \(50 \%\) 的數據，\(N \leq 1000，M \leq 10000，D_i \leq 10^{18}\)；

對于 \(70 \%\) 的數據，\(N \leq 5000，M \leq 50000，D_i \leq 10^{18}\)；

對于 \(100 \%\) 的數據，\(N \leq 50000\)， \(M \leq 100000\)，\(D_i \leq 10^{18}\)。

解題思路

看了題解可知，這題先dfs一遍圖，隨便找一條從起點到終點的路，求出路上的異或值，同時把所有搜索到的環的異或值全部加入線性基，然后把那條路上的異或值放到線性基里，找能夠異或到的最大值，然后就是答案。敷衍

這題的思想有點像我這學期高數剛學的格林公式，不知道的就別管這個詞了。我們從那條路起點\(1\)出發，到達路中間的一個點\(x\)，然后離開這條路，通過某一段 \(x \rightarrow y\) 走到某個環上的一個點\(y\)，然后從點\(y\)開始繞環一周，回到點\(y\)，再從點\(y\)通過剛才那段\(y \rightarrow x\) 回到點\(x\)，再接著走完那條路剩下的部分\(x\rightarrow n\)。由“異或兩次同一個數相當于沒有異或”的性質可以知道，\(x\rightarrow y\)和\(y\rightarrow x\)就互相抵消了，于是答案就是\(1\rightarrow n\)的異或值再異或上那個環的異或值。再多走幾個環，就再多異或幾個環就好。

那么為什么最開始隨便選一條路就好呢？是這樣：假設存在兩條路可以從\(1\)到\(n\)，那么因為是無向圖，這兩條路就成了一個環，我們dfs過程中就會把這個環加入線性基。走了其中一條路，再走這個環，就相當于走了另一條路。

源代碼

#include<stdio.h>const int MAXN=5e5+5,MAXM=4e5+5; typedef long long ull; int n,m;struct Edge{int nxt,to;ull w; }e[MAXM<<1]; int cnt=1,head[MAXN]; inline void add(int u,int v,ull w) {e[cnt]={head[u],v,w};head[u]=cnt++;e[cnt]={head[v],u,w};head[v]=cnt++; }ull b[64]={0};//線性基 inline void addb(ull a) {for(int i=62;~i;i--){if(a>>i){if(b[i]) a^=b[i];else{b[i]=a;return;}}} } inline ull mx(ull ans) {for(int i=62;~i;i--)if((ans^b[i])>ans) ans^=b[i];return ans; } bool vis[MAXN]; ull dis[MAXN];//從1搜過來的值 void dfs(int u) {vis[u]=1;for(int i=head[u];i;i=e[i].nxt){int v=e[i].to;if(vis[v])addb(dis[v]^dis[u]^e[i].w);else{dis[v]=dis[u]^e[i].w;dfs(v);}} } int main() {//freopen("test.in","r",stdin);scanf("%d%d",&n,&m);while(m--){int u,v;ull w;scanf("%d%d%lld",&u,&v,&w);add(u,v,w);}dfs(1);printf("%lld\n",mx(dis[n]));return 0; }

轉載于:https://www.cnblogs.com/wawcac-blog/p/11324239.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的洛谷 P4151 BZOJ 2115 [WC2011]最大XOR和路径的全部內容，希望文章能夠幫你解決所遇到的問題。

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