[BZOJ 2115][Wc2011]Xor
转载请注明出处：http://danihao123.is-programmer.com/
这个可以有啊（赞赏）！
我们可以发现如果两点间如果有多条路径，那么任意两条路径在一个简单环里。
然后我们还发现，如果说是一个路径，一个环和这个路径有交边，那么走这个环走很多次没有意义（其实相当于从环的两边选一边走）。
然后这样可以发现，用1到n的路径来异或一个环，可以得到新的一条1到n的路径。
这样我们可以用DFS树来求出图上所有简单环的异或和，求出其线性基，然后随便找条1到n的路径，问题就变成了求这条路径和那个线性基的异或和最大是多少。然后这就是线性基乱搞好了……
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 | /************************************************************** Problem: 2115 User: danihao123 Language: C++ Result: Accepted Time:652 ms Memory:6544 kb****************************************************************/ #include <cstdio>#include <cstring>#include <cstdlib>#include <cctype>#include <algorithm>#include <utility>#include <queue>#include <set>#include <vector>typedef long long ll;const int maxn = 50005;const int maxm = maxn << 2;int first[maxn];int next[maxm], to[maxm];ll dist[maxm]; int rev[maxm];int add_edge(int u, int v, ll d) { static int cnt = 0; cnt ++; next[cnt] = first[u]; first[u] = cnt; to[cnt] = v; dist[cnt] = d; return cnt;}void ins_edge(int u, int v, ll d) { int e1 = add_edge(u, v, d); int e2 = add_edge(v, u, d); rev[e1] = e2; rev[e2] = e1;} const int maxb = 61;ll T[maxb];void insert(ll x) { for(int i = 60; i >= 0; i --) { if(!x) break; if((x & (1LL << i)) == 0) continue; if(T[i]) { x ^= T[i]; } else { for(int j = i - 1; j >= 0; j --) { if(x & (1LL << j)) { x ^= T[j]; } } for(int j = i + 1; j < maxb; j ++) { if(T[j] & (1LL << i)) { T[j] ^= x; } } T[i] = x; break; } }}ll sum[maxn];bool vis[maxn], used[maxm];void dfs(int x, ll s) { vis[x] = true; sum[x] = s; for(int i = first[x]; i; i = next[i]) { if(used[i]) continue; int v = to[i]; used[i] = used[rev[i]] = true; if(vis[v]) { insert((s ^ sum[v]) ^ dist[i]); } else { dfs(v, s ^ dist[i]); } }} #ifdef LOCAL#define LO "%I64d"#else#define LO "%lld"#endifint main() { int n, m; scanf("%d%d", &n, &m); for(int i = 1; i <= m; i ++) { int u, v; ll d; scanf("%d%d", &u, &v); scanf(LO, &d); ins_edge(u, v, d); } dfs(1, 0LL); ll ret = sum[n]; for(int i = 60; i >= 0; i --) { if(!T[i]) continue; if(!(ret & (1LL << i))) { ret ^= T[i]; } } printf(LO, ret); puts(""); return 0;} |
评论 (0)
