题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2115
题目大意是求一条从1到n的路径，使得路径xor和最大。
可以发现想枚举1到n的所有路径是不行的。
首先有个结论：一个无向连通图G中有且仅有M-N+1个独立回路。
独立回路是指任意一个都不能由其他回路构成。
引用一段数学归纳法证明：
“M=N-1时，树，结论成立
设M=K时结论成立，当M=K+1时，任取G中一条边e，G-e中有K-N+1个独立回路，且
任取一个包含e的回路C，显然独立于之前的回路
任意两个包含e的回路C1与C2，C12=C1+C2是G-e的回路，C2不独立
故能且仅能增加一个包含e的独立回路
从而G中恰有(K+1)-N+1个独立回路，证毕”
有了这个就会发现，如果已经有一条1到n的路径，那么通过与上述的独立回路线性组合，就能表示所有1到n的路径。
然后通过dfs可以构造所有独立回路：记录dfs过程中xor的和，如果遇到访问过的节点，说明构成了一个环，也就是独立回路。
此处想了一个优化，标记一个时间戳，只有遍历到时间戳小于等于本身的结点，才能构成一个回路。这样应该就能正好得到（m-n+1)个独立回路了。
然后接下来对独立回路得到的xor和进行xor高斯消元，得到一组向量基。
然后由于向量基互相线性无关，而且对于一个向量基k，它总大于比它小的基的线性组合。
然后ans一开始赋值为p[n]，表示1到n的某一条路径。
然后ans = max(ans, ans^s[i])来更新ans。
代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <string>
#include <queue>
#include <vector>
#define LL long long using namespace std; const int maxN = ;
const int maxM = ;
int n, m;
LL p[maxN], s[maxM];
int top, vis[maxN]; //链式前向星
struct Edge
{
int to, next;
LL val;
}edge[maxM*]; int head[maxN], cnt; void addEdge(int u, int v, LL w)
{
edge[cnt].to = v;
edge[cnt].next = head[u];
edge[cnt].val = w;
head[u] = cnt;
cnt++;
} void initEdge()
{
memset(head, -, sizeof(head));
cnt = ;
} void input()
{
initEdge();
int u, v;
LL w;
for (int i = ; i < m; ++i)
{
scanf("%d%d%lld", &u, &v, &w);
addEdge(u, v, w);
addEdge(v, u, w);
}
top = ;
memset(vis, -, sizeof(vis));
} void dfs(int now, int fa, int t)
{
vis[now] = t;
int k;
for (int i = head[now]; i != -; i = edge[i].next)
{
k = edge[i].to;
if (k == fa) continue;
if (vis[k] != -)
{
if (vis[k] <= t)
s[top++] = p[now]^p[k]^edge[i].val;
}
else
{
p[k] = p[now]^edge[i].val;
dfs(k, now, t+);
}
}
} //xor高斯消元求线性基
//时间复杂度O(63n)
int xorGauss(int n)
{
int row = ;
for (int i = ; i >= ; i--)
{
int j;
for (j = row; j < n; j++)
if(s[j]&((LL)<<i))
break;
if (j != n)
{
swap(s[row], s[j]);
for (j = ; j < n; j++)
{
if(j == row) continue;
if(s[j]&((LL)<<i))
s[j] ^= s[row];
}
row++;
}
}
return row;
} void work()
{
p[] = ;
dfs(, , );
int row;
row = xorGauss(top);
LL ans = p[n];
for (int i = ; i < row; ++i)
ans = max(ans, ans^s[i]);
printf("%lld\n", ans);
} int main()
{
//freopen("test.in", "r", stdin);
while (scanf("%d%d", &n, &m) != EOF)
{
input();
work();
}
return ;
}