BZOJ2115 [WC2011] XOR

Ameiyo · 2019-08-02 16:34:00 · 个人记录

BZOJ2115 [WC2011] XOR

题目链接

一道很好的题目。

首先，题目要的答案与异或有关。

由于异或的特殊性质，我们可以先随便选出一条路径，在通过选择把不优的部分去掉，或者是换成别的路径，来得到最终的结果。

详细的说，我们可以先随便处理出 1 到 n 的某个路径上的值，然后在看看跑环会不会更优。

对于所有的环，我们选择他的时候有两种情况：

1. 他与当前已经选择的路径没有交集，那么由于图连通，选择他所对应的的决策就是从路径上走过去，再走回之前的路径，由此走两边的路径会被异或抵消，这么走的权值就是环上的总权值。
2. 他与当前已经选择的路径存在交集，那么选择他所对应的的决策就是换一条路径走，因为重复的部分被抵消了。

为什么一开始随便选一条路径就可以了呢？根据 1 与 n 是否在一个环里分别按照上述证明即可。

#define ll long long
#define reg register
#define rep(i, a, b) for (reg int i = (a), i##end = (b); i <= i##end; ++i)
#define dep(i, a, b) for (reg int i = (a), i##end = (b); i >= i##end; --i)

template <typename _typer> inline _typer read() {
    _typer init = 0;
    char ch = getchar(), k = 0;
    for ( ; !isdigit(ch); ch = getchar()) k = (ch == '-');
    for ( ; isdigit(ch); ch = getchar())
        init = (init << 3) + (init << 1) + (ch ^ 48);
    return k ? -init : init;
}
const ll N = 50005, INF = 1e9;
const ll M = 100005, LogVal = 63;

/*******************************************************************************
 *
 * https://www.cnblogs.com/ljh2000-jump/p/5869925.html
 *
 ******************************************************************************/


struct LinearBasis {
    ll d[LogVal + 5];
    void clear() { memset(d, 0, sizeof d); }
    LinearBasis() { clear(); }
    int Insert(ll x) {
        dep (i, LogVal, 0) if ((x >> i) & 1) {
            if (d[i]) x ^= d[i];
            else {
                rep (j, 0, i - 1) if ((x >> j) & 1) x ^= d[j];
                rep (j, i + 1, LogVal) if ((d[j] >> i) & 1) d[j] ^= x;
                d[i] = x;
                return true;
            }
        }
        return false;
    }
    ll QueryMx(ll ans) {
        dep (i, LogVal, 0) if ((ans ^ d[i]) > ans) ans ^= d[i];
        return ans;
    }
} BV;

int n, m;
struct EDGE {
    int to, nex; ll cost;
} edge[M << 1];
int head[N], cntedge;
void Addedge(int u, int v, ll w) {
    edge[++cntedge] = (EDGE) { v, head[u], w };
    head[u] = cntedge;
}

int vis[N]; ll w[N], Cir[M << 1]; // 到 1 的路径上的异或和
void Dfs(int u, int fa) {
    vis[u] = true;
    for (int i = head[u], v; i; i = edge[i].nex) {
        v = edge[i].to;
        if (!vis[v]) w[v] = w[u] ^ edge[i].cost, Dfs(v, u);
        else if (v != fa) Cir[++Cir[0]] = w[u] ^ w[v] ^ edge[i].cost;
    }
}

int main() {
    n = read<int>(), m = read<int>();
    rep (i, 1, m) {
        int x = read<int>(), y = read<int>();
        ll w = read<ll>();
        Addedge(x, y, w); Addedge(y, x, w);
    }
    Dfs(1, 0);
    rep (i, 1, Cir[0]) BV.Insert(Cir[i]);
    cout << BV.QueryMx(w[n]) << endl;
    return 0;
}