题目大意：

给你一张n个点，m条边的无向图，每条边都有一个权值，求：1到n的路径权值和的最大值。

题解：

任意一条路径都能够由一条简单路径（任意一条），在接上若干个环构成（如果不与这条简单路径相连就走过去再走回来）。

那么在对这些环进行分类：

1、直接与简单路径相连

相交的重复部分不算就可以了。

2、不与简单路径相连

我们需要跑过去，再跑回来对吧，这样的话，不管我们是怎么跑的，非环的路径对答案的贡献始终为0,（抵消了嘛）。

这样的话，我们只需要用这几个环来构造线性基即可，最后再找个最大值就行啦！

代码：

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int N=50005,M=200005;

ll b[65],dist[M],d[N],z,ans;

int head[N],vet[M],nxt[M],n,m,x,y,tot;

bool vis[N],used[M];

void add(int x,int y,ll z){

    nxt[++tot]=head[x];

    vet[tot]=y;

    head[x]=tot;

    dist[tot]=z;

}

void insert(ll x){

    for (int i=63;i>=0;i--)

        if (x>>i)

            if (b[i]) x^=b[i];

            else {b[i]=x; break;}

}

void dfs(int u){                              //找环

    vis[u]=true;

    for (int i=head[u];i;i=nxt[i]){

        int v=vet[i];

        if (!vis[v]){

            d[v]=d[u]^dist[i];

            dfs(v);

        } else

            if (!used[i^1]){

                used[i^1]=true;

                insert(d[u]^d[v]^dist[i]);

            }

    }

}

int main(){

    scanf("%d %d",&n,&m); tot=1;

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

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

        add(x,y,z); add(y,x,z);

    }

    dfs(1);

    ans=d[n];

    for (int i=63;i>=0;i--)

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

    printf("%lld\n",ans);

    return 0;

}

巴特西

[WC 2011]最大Xor和路径

题目大意：

题解：

代码：

最新文章

热门文章