题目链接：http://acm.uestc.edu.cn/#/problem/show/1219
题目大意是给了一张图，然后要求一个点通过路径回到这个点，使得xor和最大。
这是CCPC南阳站的一道题。当时只读了题目发现并不会。
这是一个典型的xor高斯消元。
需要预先dfs出所有的独立回路。
然后线性组合独立回路的xor和，使得ans最大。
最近做过类似的题目，直接粘代码。
需要注意这里独立回路的数组开maxM是不够的，会RE。
代码：
方法一：线性基（O(63n)）
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <algorithm> #include <set> #include <map> #include <queue> #include <string> #define LL long long using namespace std; const int maxN = 50005; const int maxM = 100005; int n, m, top; LL p[maxN], s[maxM*2]; bool vis[maxN]; //链式前向星 struct Edge { int to, next; LL val; }edge[maxM*2]; 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, -1, sizeof(head)); cnt = 0; } void dfs(int now, int fa) { vis[now] = true; int k; for (int i = head[now]; i != -1; i = edge[i].next) { k = edge[i].to; if (k == fa) continue; if (vis[k]) s[top++] = p[now]^p[k]^edge[i].val; else { p[k] = p[now]^edge[i].val; dfs(k, now); } } } void input() { initEdge(); memset(vis, false, sizeof(vis)); scanf("%d%d", &n, &m); int u, v; LL w; for (int i = 0; i < m; ++i) { scanf("%d%d%lld", &u, &v, &w); addEdge(u, v, w); addEdge(v, u, w); } } //xor高斯消元求线性基 //时间复杂度O(63n) int xorGauss(int n) { int row = 0; for (int i = 62; i >= 0; i--) { int j; for (j = row; j < n; j++) if(s[j]&((LL)1<<i)) break; if (j != n) { swap(s[row], s[j]); for (j = 0; j < n; j++) { if(j == row) continue; if(s[j]&((LL)1<<i)) s[j] ^= s[row]; } row++; } } return row; } void work() { top = 0; p[1] = 0; dfs(1, 0); int row; row = xorGauss(top); LL ans = 0; for (int i = 0; i < row; ++i) ans = max(ans, ans^s[i]); printf("%lld\n", ans); } int main() { //freopen("test.in", "r", stdin); int T; scanf("%d", &T); for (int times = 0; times < T; ++times) { printf("Case #%d: ", times+1); input(); work(); } return 0; }
方法二：高斯消元判断是否有解（之前博客讲过）（O(63*63n)）
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <algorithm> #include <set> #include <map> #include <queue> #include <string> #define LL long long using namespace std; const int maxN = 50005; const int maxM = 100005; const int len = 63; int num, a[64][maxM*2]; bool vis[maxM]; LL p[maxN]; //链式前向星 struct Edge { int to, next; LL val; //int val; }edge[maxM*2]; 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, -1, sizeof(head)); cnt = 0; } LL xorGauss(int n) { LL ans = 0; for (int i = len-1; i >= 0; i--) { int j; for (j = 0; j < n; j++) { if (a[i][j] && !vis[j]) { vis[j] = true; ans += (LL)1<<i; break; } } if(j == n) { if(a[i][n] == 0) ans += (LL)1<<i; } else { for (int k = i-1; k >= 0; k--) { if (a[k][j]) { for (int v = 0; v <= n; v++) a[k][v] ^= a[i][v]; } } } } return ans; } void dfs(int now, LL val) { if (p[now] != -1) { LL t; t = p[now]^val; for (int j = 0; t > 0; ++j) { a[j][num] = t&1; t >>= 1; } num++; return; } p[now] = val; int k; for (int i = head[now]; i != -1; i = edge[i].next) { k = edge[i].to; dfs(k, val^edge[i].val); } } void input() { int n, m; scanf("%d%d", &n, &m); initEdge(); int u, v; LL w; for (int i = 0; i < m; ++i) { scanf("%d%d%lld", &u, &v, &w); addEdge(u, v, w); addEdge(v, u, w); } memset(p, -1, sizeof(p)); num = 0; dfs(1, 0); } void init() { memset(a, 0, sizeof(a)); memset(vis, false, sizeof(vis)); input(); for (int i = 0; i < len; i++) a[i][num] = 1; } void work() { LL ans; ans = xorGauss(num); //cout << num << endl; printf("%lld\n", ans); } int main() { //freopen("test.in", "r", stdin); int T; scanf("%d", &T); for (int times = 0; times < T; ++times) { printf("Case #%d: ", times+1); init(); work(); } return 0; }
ACM学习历程—UESTC 1219 Ba Gua Zhen（dfs && 独立回路 && xor高斯消元）
原文：http://www.cnblogs.com/andyqsmart/p/4970038.html
