BZOJ2115 [WC2011] Xor

2015.02.03 16:29 Tue| 1 visits oi_2015| 2015_刷题日常| Text

Solution

线性基的第一题。

集合 S 中有若干个数,任取其一个非空子集得到其异或和,所有能得到的异或和组成了一个集合 P。P 可以称为 S 的异或空间。

容易证明如下结论:对于集合中 S 的两个数 $a_i, a_j(a_i!=a_j)$,进行操作 $a_i^=a_j$ ,则集合S'的异或空间等于集合S的异或空间。

那么我们通过若干的变换,总可以保证得到异或空间的必要元素数目为 $\log\max N$。

这些元素组成的集合称为集合 S 的线性基。

        ——By wyfcyx

线性基的样子就是元素的最高非零位的位数互不相同(就像是高斯消元消出来的上三角)。

对于这道题而言,找到一条从起点到终点的路径,和图中所有的简单环,分别求出它们中所有元素的异或和。由于这条路径去到一个环之间的路径一定会走过两次,异或和为 0,不需考虑。这样就只需先求出所有环的权值之间的线性基,之后求出这条路径长度所能异或得到的最大值就是答案。

Code

#include <bits/stdc++.h>
using namespace std;

#define N 50005
#define M 200005

inline long long read()
{
    long long x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int n, m, head[N]; bool vis[N]; long long dist[N];

struct graph
{
    int next, to; long long val;
    graph() {}
    graph(int _next, int _to, long long _val)
    : next(_next), to(_to), val(_val) {}
} edge[M];

inline void add(int x, int y, long long z)
{
    static int cnt = 0;
    edge[++cnt] = graph(head[x], y, z);
    head[x] = cnt;
}

struct liner_base
{
    long long base[64];
    void insert(long long x)
    {
        for (int i = 63; i >= 0; --i)
        {
            if ((x >> i) & 1)
            {
                if (base[i]) x ^= base[i];
                else { base[i] = x; break; }
            }
        }
    }
} lb;

void dfs(int x)
{
    for (int i = head[x]; i; i = edge[i].next)
    {
        int y = edge[i].to;
        if (vis[y])
            lb.insert(dist[x] ^ dist[y] ^ edge[i].val);
        else
        {
            vis[y] = 1;
            dist[y] = dist[x] ^ edge[i].val;
            dfs(y);
        }
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        long long x = read(), y = read(), z = read();
        add(x, y, z), add(y, x, z);
    }
    vis[1] = 1;
    dfs(1);
    for (int i = 63; i >= 0; --i)
        if (!((dist[n] >> i) & 1))
            dist[n] ^= lb.base[i];
    cout << dist[n] << endl;
}