题意:一个边权非负的无向连通图,节点编号为1到n,试求出一条从1号节点到N号节点的路径,使得路径上经过的边得权值的XOR和最大.
先明确两点:
1.所有的环都是可以经过的。
假设我们从1号点开始走,走到一个环的起点,然后走过这个环以后回到环的起点,这时我们就也可以直接回到起点。所以除了环上的路径,其他的路径都走了两次,被抵消了。
所以,任意一个环都是可以选的。
2.任意选一条1到n的路径的基础上再添环:为什么可以任意一条路径?:
我们选了一条路径作为初始ans以后,如果存在一条更优的路径,那么这两条路径肯定是构成一个环的,会被选入线性基中。那么我们再用初始的ans异或一下这个环,我们就会发现,初始的ans被抵消了,而更优的那条路径留了下来。因此任选一个初始ans是可行的。
此题做法:
先找出所有的环,选入线性基中,再选出任意一条从1到n的路径,异或和作为初始ans。(这两步可以dfs一遍一起做)。再用ans异或线性基的最大值就是我们求的答案。(这一步:从高位往低位异或。如果当前ans异或这一位的数能使ans变大,那么就异或。)
根据此题,我们还可以得到一个结论:任意一条1到n的路径的异或和,可以由任意一条1到n的路径的异或和以及一些环的异或和来组合得到。
普及一下线性基:
一.定义:
线性基是一个 数的集合,并且每个序列都拥有一个线性基,取线性基中若干个数异或起来可以得到原序列中的任何一个数。
二.性质:
(a.原序列里面的任意一个数都可以由线性基里面的一些数异或得到
(b.线性基里面的任意一些数异或起来都不能得到0
(c.线性基里面的数的个数唯一,并且在保持性质一的前提下,数的个数是最少的
三.生成线性基方法:
void add(int x){
for(int i=30;i>=0;i--){
if(x&(1<<i)){
if(d[i])x^=d[i];
else{d[i]=x;break;}
}
}
}
d数组表示a数组的线性基,x是序列a中的每一个数,尝试将它插入到线性基里面去。
四.如何求线性基的最大值:
构造出这个序列的线性基后,从线性基的最高位开始,假如当前的答案异或线性基的这个元素可以变得更大,那么就异或它。答案的初值0。
int qmax(){
int res=0;
for(int i=30;i>=0;i--){//从线性基的最高位开始
if((res^d[i])>res)res^=d[i];
}
return res;
}
五.其他:
1求最小值:就是min(d[i]) ,它去异或其他的d[i]只会变得更大
2.求第k小值:将k先转成二进制,若k的第i位为1,ans就异或线性基中第i个元素
回到此题:
此题代码:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1000010;
int tot,cnt,n,m;
int head[maxn],nxt[maxn],ver[maxn],edge[maxn];
int huan[maxn],vis[maxn],d[maxn],a[maxn];
//huan:记录成环的点,a环中到i点的异或和
//cnt成环的个数,d线性基
void mem(){
memset(head,0,sizeof(head));
memset(nxt,0,sizeof(nxt));
memset(ver,0,sizeof(ver));
memset(edge,0,sizeof(edge));
memset(vis,0,sizeof(vis));
memset(huan,0,sizeof(huan));
cnt=tot=0;
}
void add(int x,int y,int z){
ver[++tot]=y;edge[tot]=z;nxt[tot]=head[x];head[x]=tot;
}
void dfs(int x){
vis[x]=1;
for(int i=head[x];i;i=nxt[i]){
int y=ver[i];
if(!vis[y]){
a[y]=a[x]^edge[i];
dfs(y);
}else{
huan[++cnt]=a[x]^a[y]^edge[i];
}
}
}
void add(int x){
for(int i=62;i>=0;i--){
if(x&(1ll<<i)){//注意1ll
if(d[i])x^=d[i];
else{d[i]=x;break;}
}
}
}
int q_max(){
int res=a[n];//初始值为任意一条从1~n的路径
for(int i=62;i>=0;i--){
if((res^d[i])>res)res^=d[i];
}
return res;
}
signed main() {
while(cin>>n>>m&&n){
mem();
for(int i=1;i<=m;i++){
int x,y,z;cin>>x>>y>>z;
add(x,y,z);add(y,x,z);
}
dfs(1);
for(int i=1;i<=cnt;i++){
add(huan[i]);
}
int ans=q_max();
cout<<ans<<endl;
}
return 0;
}
“2.求第k小值:将k先转成二进制,若k的第i位为1,ans就异或线性基中第i个元素”
这里是不是写错了 比如{1100,100}这个基,它的异或空间小到大是{100,1000,1100} 如果要求第11(二进制)小的值,那就要分别异或上1100和100,得出1000,然而这是第10小 应该先把基最小化再这么算才对
马蜂好评
那个星星是不是点赞啊?
星星是收藏