BZOJ 2115 [Wc2011] Xor （线性基）

BZOJ 2115 [Wc2011] Xor （线性基）

Description

考虑一个边权为非负整数的无向连通图，节点编号为 1 到 N，试求出一条从 1 号节点到 N 号节点的路径，使得路径上经过的边权值的 XOR 和最大。路径可以重复经过某些点或边，当一条边在路径中出现了很多次时，其权值在计算 XOR 和时也要被计算相应多的次数。

Input

第一行包含两个整数 N 和 M ，表示该无向图中点的数目与边的数目。接下来 M 行描述 M 条边，每行三个整数 Si，Ti ，Di，表示 Si 与 Ti 之间存在一条权值为 Di 的无向边。图中可能有重边或自环。

Output

仅包含一个整数，表示最大的 XOR 和（十进制结果），注意输出后加换行回车。

Sample Input

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

Sample Output

6

思路

因为是无向图，且允许经过重复点以及重复边，所以我们最终所选择的路径可以看作是从 1 -> n 的一条主路径附带很多的环组成。

记每一个环所贡献的权值为 ai a i ，主路径权值为 disn d i s n ，接下来我们要选择某些 ai a i

显然我们可以找出 ai a i

接下来我们分析为什么这样的做法可行：

为什么每一个环可以无消耗的加入主路径：具体我们可以从 1 走到环内的一点，然后绕环走完所有的边再原路返回，因为总的权值是各边的异或和，所以来回走同一段路的消耗是 0 ，即每个环的权值我们都可以直接附加到主路径中。主路径如何选取：假设从 1 -> n 存在一条以上的路径，那么这些路径之间一定会存在一个或者多个环，此时我们讨论只有一个环的情况（多个环类似），设该环的权值为 p p ，主路径的权值为 disdis ，显然另一条路径的权值为 p⊕dis p ⊕ d i s

AC 代码

#include #define IO \ ios::sync_with_stdio(false); \ cin.tie(0); \ cout.tie(0);using namespace std;typedef long long LL;const int maxn = 2e5 + 10;struct node { int from; int to; int next; LL cost;} edge[maxn << 1];int head[maxn], tot;int n, m, idx;LL a[maxn], dis[maxn], p[maxn];void init() { memset(head, -1, sizeof(head)); memset(dis, -1, sizeof(dis)); tot = idx = 0;}void addedge(int u, int v, LL cost) { edge[tot].from = u; edge[tot].to = v; edge[tot].cost = cost; edge[tot].next = head[u]; head[u] = tot++;}void initBase() { for (int i = 0; i < idx; i++) { for (int j = 62; j >= 0; j--) { if ((p[i] >> j) & 1) { if (a[j] == 0) { a[j] = p[i]; break; } else { p[i] ^= a[j]; } } } }}void dfs(int x, LL cost) { if (dis[x] == -1) dis[x] = cost; else { p[idx++] = dis[x] ^ cost; return; } for (int i = head[x]; i != -1; i = edge[i].next) { dfs(edge[i].to, edge[i].cost ^ cost); }}void solve() { dfs(1, 0); initBase(); LL ans = dis[n]; for (int i = 62; i >= 0; i--) ans = max(ans, ans ^ a[i]); cout << ans << endl;}int main() {#ifdef LOCAL_IM0QIANQIAN freopen("test.in", "r", stdin); freopen("test.out", "w", stdout);#else IO;#endif // LOCAL_IM0QIANQIAN init(); cin >> n >> m; for (int i = 0; i < m; i++) { LL u, v, cost; cin >> u >> v >> cost; addedge(u, v, cost); addedge(v, u, cost); } solve(); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。