图论 c++ BZOJ2115 XOR（线性基）

前置知识：线性基

题目描述

有一个边权为非负数的无向连通图，节点编号为

1

1

1到

n

n

n。求一条从

1

1

1到

n

n

n的路径，使得路径上经过的边的边权的异或和最大。

路径可以重复经过点和边，当一条边在路径中出现多次时，其权值在计算异或和时也要被计算相应多的次数。

题解

如果图中没有环，那么

1

1

1到

n

n

n的无重边的路径显然是最优的。那么如果有环，我们可以先找到一条从

1

1

1到

n

n

n的路径，算出异或和。然后，用一次dfs求出每个环的异或和。对于一个环，我们可以从

1

1

1到

n

n

n的路径上任意取一个点，从这个点走到环，绕环一圈后走回这个点。环到点的路径被走过两次，异或两次等于不变，所以就相当于原来

1

1

1到

n

n

n的路径的异或和再异或上这个环的异或和。

也就是说，我们要选若干个环，使这些环的异或和最大。那么这道题就变成了求若干个数的最大异或和，可以用线性基来解决。不过需要注意的是，

1

1

1到

n

n

n的路径是必须要选的，不能将这条路径的异或和忽略了。

code

#include

using namespace std;

int n,m,x,y,tot,cnt,d[200005],l[200005],r[200005],v[100005];

long long z,ans,w[200005],dis[100005],a[200005],b[105];

void add(int xx,int yy,long long zz){

l[++tot]=r[xx];d[tot]=yy;r[xx]=tot;w[tot]=zz;

}

void dfs(int u){

v[u]=1;

for(int i=r[u];i;i=l[i]){

if(v[d[i]]){

a[++cnt]=dis[d[i]]^dis[u]^w[i];

}

else{

dis[d[i]]=dis[u]^w[i];

dfs(d[i]);

}

}

}

int main()

{

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

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

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

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

}

dfs(1);

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

for(int j=60;j>=0;j--){

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

if(b[j]) a[i]^=b[j];

else{

b[j]=a[i];break;

}

}

}

}

ans=dis[n];

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

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

}

printf("%lld",ans);

return 0;

}

推荐阅读