BZOJ2115【WC2011】Xor <线性基>

Problem

【WC2011】Xor

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;259MB}$

Description


Input

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

Output

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

Sample Input

5 7
1 2 2
1 3 2
2 4 1
2 5 1
4 5 3
5 3 4
4 3 2

Sample Output

6

Hint


标签：线性基

Solution

线性基经典题。

对于一条非简单的路径，其异或和等于其中的简单路径异或和异或上经过的环的异或和，即选取一条简单路径和若干环，此简单路径到环的那段路径会经过两次，因而异或和消成$0$。
因此只用选出一条从$1$到$n$的简单路径异或和，再异或上若干环的异或和使总和最大即可。
于是暴力$\mathrm{DFS}$找到简单路径异或和和所有环的异或和，对所有环的异或和求线性基，贪心选最大和即可。

Code

#include <bits/stdc++.h>
#define SZ 60
#define MAX_N 50000
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m;
lnt b[SZ+5], dis[MAX_N+5]; bool mrk[MAX_N+5];
vector <int> G[MAX_N+5]; vector <lnt> E[MAX_N+5];
void insert(lnt x) {
    for (int i = SZ; ~i; i--) if (x>>i&1) {
        if (b[i]) x ^= b[i];
        else {b[i] = x; break;}
    }
}
void DFS(int u) {
    for (int i = 0, v; i < (int)G[u].size(); i++)
        if (mrk[v = G[u][i]]) insert(dis[u]^dis[v]^E[u][i]);
        else dis[v] = dis[u]^E[u][i], mrk[v] = true, DFS(v);
}
int main() {
    read(n), read(m);
    for (int i = 0, u, v; i < m; i++) {
        lnt c;	read(u), read(v), read(c);
        G[u].push_back(v), E[u].push_back(c);
        G[v].push_back(u), E[v].push_back(c);
    }
    DFS(1);	lnt mx = dis[n];
    for (int i = SZ; ~i; i--)
        if (!(mx>>i&1)) mx ^= b[i];
    return printf("%lld\n", mx), 0;
}