bzoj 2115 线性基

时间：2021-01-24 08:47:13

这种路径异或问题，可以转换为一条路径和若干个环的线性组合，然后就能用线性基搞了。

复习了一波线性基。

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define PII pair<int, int>

#define PLI pair<LL, int>

#define ull unsigned long long

using namespace std;

const int N = 1e5 + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + ;

int n, m;

LL d[N];

bool vis[N];

vector<PLI> edge[N];

struct Base {

    vector<LL> a;

    void add(LL x) {

        for(int i = ; i < a.size(); i++)

            x = min(x, x^a[i]);

        if(!x) return;

        for(int i = ; i < a.size(); i++)

            a[i] = min(a[i], a[i]^x);

        a.push_back(x);

    }

    LL getMx(LL ans) {

        for(int i = ; i < a.size(); i++)

            ans = max(ans, ans^a[i]);

        return ans;

    }

} base;

void dfs(int u, int fa) {

    vis[u] = true;

    for(int i = ; i < edge[u].size(); i++) {

        int v = edge[u][i].se; LL w = edge[u][i].fi;

        if(v == fa) continue;

        if(vis[v]) {

            base.add(d[u]^d[v]^w);

        } else {

            d[v] = d[u] ^ w;

            dfs(v, u);

        }

    }

}

int main() {

    scanf("%d%d", &n, &m);

    for(int i = ; i <= m; i++) {

        int u, v; LL w;

        scanf("%d%d%lld", &u, &v, &w);

        edge[u].push_back(mk(w, v));

        edge[v].push_back(mk(w, u));

    }

    dfs(, );

    printf("%lld\n", base.getMx(d[n]));

    return ;

}

/*

*/

相关文章