AcWing 228. 异或（dfs+线性基）打卡

题目:https://www.acwing.com/problem/content/230/

题意:有一个图,每条边有一个权值,现在求1-n的一条路径的最大异或和,一条边能经过多次,相应的也要计算那么多次权值

思路:首先最大异或和一看就是线性基的经典操作,然后主要是我们要如何确定这条路径,

我们首先随便计算出一条1-n路径上的最大异或和,然后再是一些环,因为一条路径异或上其他的环的话就是变成了一条新的路径

所以我们只要dfs出一条路径,然后存下所有的环,我们把这些环跑个线性基,然后就可以利用线性基的性质,如果异或当前基,会使值更大,就选,因为每个位只有一个值

1,然后说下离开始求得1-n路径上很远的环为什么也可以使用,因为我们以一点出发走过那个环再原路返回,相当于我们把去的路又异或没有了,只有环的值,现在我们只要

2,我们最开始选取的路径是否会影响最优问题,答案是不会,为什么呢,因为这条路径可以通过异或一些环来得到其他路径,所以这个不是问题

最后说下有个很坑的地方,你的记录环的个数那个数组要开很大,因为环的数量太多了

#include<bits/stdc++.h>

#define maxn 250005

#define mod 1000000007

using namespace std;

typedef long long  ll;

int n,m,cnt;

bool vis[maxn];

ll d[maxn],a[maxn],ins[];

vector<pair<ll,ll> > mp[maxn];

void dfs(ll x){

    vis[x]=;

    for(int i=;i<mp[x].size();i++){

        pair<ll,ll> q=mp[x][i];

        if(!vis[q.first]){

            d[q.first]=d[x]^q.second;

            dfs(q.first);

        }

        else{

            a[++cnt]=d[q.first]^d[x]^q.second;

        }

    }

}

void solve(){

    for(int i=;i<=cnt;i++)

    {

        for(int j=;j>=;j--)

        {

            if((a[i]>>j)&)

            {

                if(!ins[j])

                {

                    ins[j]=a[i];

                    break;

                }

                else

                    a[i]^=ins[j];

            }

        }

    }

    ll ans=d[n];

    for(int i=;i>=;i--){

        if((ans^ins[i])>ans) ans^=ins[i];

    }

    printf("%lld",ans);

}

int main(){

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

    ll x,y;

    ll z;

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

        scanf("%lld%lld%lld",&x,&y,&z);

        mp[x].push_back(make_pair(y,z));

        mp[y].push_back(make_pair(x,z));

    }

    dfs();

    solve();

    return ;

}

巴特西

AcWing 228. 异或（dfs+线性基）打卡

最新文章

热门文章

巴特西

AcWing 228. 异或 （dfs+线性基）打卡

最新文章

热门文章

AcWing 228. 异或（dfs+线性基）打卡