是我喜欢的典题，直接秒掉！

蒟蒻的第一篇紫题题解qwq

~~你个【数据删除】，做了道这么水还这么典的紫也要被你拉出来炫耀吗？~~

前置知识：线性基

首先，做过P4151 [WC2011] 最大XOR和路径这题的人就会知道，无向图上一条

x

到

y

的异或路径一定可以用另一条

x

到

y

的异或路径异或上若干个环得到。

~~不过做过 P4151 的应该都会这题，不用看题解了吧……~~

不知道这个结论也没关系，我们感性理解一下：

考虑这两条路径上端点相同但路径完全不重叠的一个部分，设两个端点分别为

x'

和

y'

。因为这是一张无向图，所以第二条路径上的边全都可以反过来走，这样，我们可以从

x'

出发走第一条路径上的边到

y'

，再从

y'

出发走第二条路径上的边到

x

，相当于我们走了一个环。

而异或有个美妙的性质就是自己异或自己会变成

0

，这等价于一条路径走了偶数次之后相当于没走。所以我们走了一次第二条路径，就等价于我们走了一次这个环之后又走了一次第一条路径。

对于整条路径的其他部分也进行相同的考虑，我们不难得出上面的结论。

那么这个结论有什么用呢？

当我们确定了起点

x

后，对于每一个从 $x$ 出发可以到达的点 $y$ ，我们只需要确定两点之间的一条路径，再将从

x

出发能到达的环的权值加入异或线性基，便可以轻松确定答案。

至于如何找出所有从

x

出发能到达的环……这个可以直接 dfs。具体地，我们在从

x

出发 dfs，如果在点

y

碰到了在当次 dfs 中已经走过的点

z

，说明

x \rightarrow y \rightarrow z \rightarrow x

形成了一个环（毕竟这是无向图）。设

dis_{y}

为从

x

出发走到

y

的权值 （只更新一次），那么这个环的权值就是

dis_y \operatorname{xor} w_i \operatorname{xor} dis_z

。（和 P4151 一样的处理方法）

那么这道紫题就被我们水灵灵地做完了~

CPP

#include <bits/stdc++.h>
#define N 500
#define M 20000
#define K 10
#define INF 114514
#define mod 1
#define int1 int
using namespace std;
int1 n,m,i,j,ans;
int1 xxj[K + 5];//xian xing ji，线性基（
int1 dis[N + 5];
int1 hea[N + 5],nex[M + 5],to[M + 5],w[M + 5],bs;
bool vis[N + 5];
// 快读部分已省略
void add_edge(const int1 x,const int1 y,const int1 z){//链式前向星建边
	nex[++bs] = hea[x],hea[x] = bs,to[bs] = y,w[bs] = z;
	return ;
}
void two_edge(const int1 x,const int1 y,const int1 z){//建双向边
	add_edge(x,y,z),add_edge(y,x,z);
	return ;
}
void insert(int1 x){
    for(int1 i = K; i >= 0; i--){
        if((x >> i) & 1){
            if(!xxj[i]){
                xxj[i] = x;
                return ;
            }
            x ^= xxj[i];
        }
    }
    return ;
}
void dfs(const int1 x,const int1 s){
    dis[x] = s,vis[x] = 1;
    for(int1 i = hea[x]; i; i = nex[i]){
        int1 y = to[i];
        if(!vis[y]){
            dfs(y,s ^ w[i]);
        }else{
            insert(s ^ w[i] ^ dis[y]);
        }
    }
    return ;
}
int main(){
    n = read(),m = read();
    for(i = 1; i <= m; i++){
        const int1 x = read(),y = read();
        two_edge(x,y,read());
    }
    ans = INF;
    for(int1 x = 1; x <= n; x++){//枚举起点
    	for(i = 1; i <= n; i++){
    		dis[i] = 0;
    		vis[i] = 0;
		} 
		for(i = 0; i <= K; i++){
			xxj[i] = 0;
		}
		dfs(x,0);
    	for(int1 y = 1; y <= n; y++){//枚举终点
    		if(x == y || !vis[y]){//起点必须可达终点，且起点和终点不能相同
    			continue;
			}
			int1 s = dis[y];
		    for(i = K; i >= 0; i--){
		        s = min(s,s ^ xxj[i]);
		    }
		    ans = min(ans,s);
		}
	}
	if(ans == INF){
		pe(-1);
		return 0;
	} 
    pe(ans);
	return 0;
}

是我喜欢的典题，直接秒掉！

文章操作

相关推荐

评论

是我喜欢的典题，直接秒掉！