「BZOJ2115」[Wc2011] Xor

2014年12月12日4,6402

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

题解

所有路径实际是一条1-n的路径和一堆环

环用dfs求出。。。

然后就是高斯消元的 经典应用

注意T T

 

说点什么

提醒
avatar
WiFiMonster
WiFiMonster

黄学长,请问一下构造线性基可不可以用贪心高到低考虑𝑥的每一位,如果𝑥这位为0且线性基中有最高位为这一位的数,就让𝑥异或上这个数,还是必须要这样高斯消元

- 慕°
- 慕°

黄学长 这题为什么环的个数开到20W左右才能过?