參考部落格：線性基學習筆記 orz
下面的題解來着該部落格
給定一個 n(n≤50000) 個點 m(m≤100000) 條邊的無向圖，每條邊上有一個權值。請你求一條從 1 到 n 的路徑，使得路徑上的邊權異或和最大。
分析
任意一條 1 到 n 的路徑的異或和，都可以由任意一條 1 到 n 路徑的異或和與圖中的一些環的異或和來組合得到。
為什麼？假如我們已經有一條 1 到 n 的路徑，考慮在出發之前，先走到圖中任意一個環上面，走一遍這個環，然後原路傳回，這樣我們既得到了這個環的異或值（走到環的路徑被走過了 2 次，抵消了），也傳回了點 1。我們可以對任意的環這樣做，進而獲得這個環的異或值。有了這個性質，不難驗證上述結論是正确的。
現在的解題思路就非常明确了，首先找出所有的環（利用 DFS 樹中的返祖邊來找環），然後找一條任意的 1 到 n 的路徑，其異或值為 s。則我們就需要選擇若幹個環，使得這些環上的異或值與 s 異或起來最大。這就轉化為線性基的問題了。
求出所有環的異或值的線性基，由于線性基的良好性質，隻需要從大到小考慮選擇每個線性基向量能否使得異或值更大即可，容易用貪心證明正确性。
證明：從高到低考慮每個二進制位，設目前的答案為 s，考慮到第 k 位，線性基向量中代表二進制位 k 的向量為 v。那麼對于第 k 位，一共有三種情況，我們分别考慮我們的選擇原則是不是正确的。
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=50000+100;
struct Edge{
int to;
ll len;
Edge(int to_=0,ll len_=0):to(to_),len(len_){}
};
vector<Edge>G[maxn];
ll dis[maxn];
bool vis[maxn];
ll cir[maxn*5],tot;
int n,m;
int ind;
inline void AddEdge(int u,int v,ll len){
G[u].push_back(Edge(v,len));
G[v].push_back(Edge(u,len));
}
void gauss(){
for(int i=62,j;i>=0;i--){
for(j=ind;j<=tot;j++) if(cir[j]&(1ll<<i)) break;
if(j<=tot){
swap(cir[j],cir[ind]);
for(j=1;j<=tot;j++) if(j!=ind && cir[j]&(1ll<<i)) cir[j]^=cir[ind];
ind++;
}
}
}
void dfs(int u){
int len=G[u].size();
vis[u]=true;
for(int i=0;i<len;i++){
Edge e=G[u][i];
int v=e.to;
if(!vis[v]){
dis[v]=dis[u]^e.len;
dfs(v);
}
else cir[++tot]=dis[u]^dis[v]^e.len;
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
int u,v;
ll len;
scanf("%d%d%lld",&u,&v,&len);
AddEdge(u,v,len);
}
tot=0;
ind=1;
dfs(1);
gauss();
ll tmp=dis[n];
for(int i=1;i<ind;i++) if((tmp^cir[i])>tmp) tmp^=cir[i];
printf("%lld\n",tmp);
}