首页 > 题解 > bzoj 2115 [Wc2011] Xor

bzoj 2115 [Wc2011] Xor

Description

Input

第一行包含两个整数N和 M, 表示该无向图中点的数目与边的数目。 接下来M 行描述 M 条边,每行三个整数Si,Ti ,Di,表示 Si 与Ti之间存在 一条权值为 Di的无向边。 图中可能有重边或自环。

Output

仅包含一个整数,表示最大的XOR和(十进制结果),注意输出后加换行回车。

Sample Input

5 7

1 2 2

1 3 2

2 4 1

2 5 1

4 5 3

5 3 4

4 3 2

Sample Output

6

HINT

题解

我们可以先随便dfs一个1到n的路径,再把剩下的环都找出来,那么所有的路径都可以由这个随便的路径和一些环的组合得出。

可以分情况讨论一下:假如这个环和这个路径没有交集,那么它可以跑到环上再回来,就只有这个环的贡献。

假设存在一条更优的路径从1到n,那么这条路径与我们原来的路径构成了一个环,也就会统计,那么这个环会被经过,那么最后的情况相当于是走了两遍原来选取的路径,抵消之后走了一次这个最优路径。

这样就把所有的环的异或和加到线性基里,用路径的异或和在里面匹配就好了。


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×