[WC2011]最大XOR和路径 线性基

题解
考虑到如果图中存在一些环,那么我们就可以在不影响其它值的情况下获得这些环上的值。
具体证明:
考虑到我们从1点出发经过一些点以后我们可以到达环到链条的起点v,然后我们经过环又回到v,这样我们的取值就是从1-v路径上的值异或上环上的值,然后我们回到1,根据异或的性质,相当于我们取得了环上的值,所以我们把所有环上的值加入到一个线性基上,然后把任意一条1-n路上上的值异或线性基上的值取最大值,任意一条就好了,因为如果有多条从1-n的路径那么就形成了环,必定被包含在了线性基上。

#include <bits/stdc++.h>

const int MAXN = 100000;

using namespace std;

int n,m;
bool vis[MAXN];
long long d[MAXN],res[MAXN];
vector<pair<int,long long> >E[MAXN];

void insert(long long c){
    bitset<63>bit = c;
    for(int i = 62;i >= 0;i--){
        if(!bit[i]) continue;
        if(!d[i]) {
            d[i] = c;
            return;
        }
        else {
            c ^= d[i];
            bit = c;
        }
    }
}

void dfs(int u,long long ret){
    res[u] = ret;vis[u] = true;
    for(auto tmp : E[u]){
        int v = tmp.first;
        long long c = tmp.second;
        if(!vis[v]) dfs(v,ret^c);
        else insert(res[u]^res[v]^c);
    }
}

int main(){
    //freopen("test.in","r",stdin);
    scanf("%d %d",&n,&m);

    long long u,v,c;
    for(int i = 1;i <= m;i++){
        scanf("%lld %lld %lld",&u,&v,&c);
        E[u].push_back(make_pair(v,c));
        E[v].push_back(make_pair(u,c));
    }
    
    dfs(1,0);
    
    long long ret = res[n];
        
    for(int i = 62;i >= 0;i--) 
        if((ret^d[i]) > ret)
            ret ^= d[i];

    printf("%lld",ret);

    return 0;
}
Last modification:October 3rd, 2019 at 03:27 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment