题目链接

传送门

Description

这是一道经典傻逼题,对经典题很熟悉的人也不要激动,希望大家不要傻逼。考虑一张N个点的带权无向图,点的编号为1到N。 对于图中的任意一个点集(可以为空或者全集),所有恰好有一个端点在这个点集中的边组成的集合被称为割。 一个割的权值被定义为所有在这个割上的边的异或和。一开始这张图是空图, 现在,考虑给这张无向图不断的加边, 加入每条边之后,你都要求出当前权值最大的割的权值, 注意加入的边永远都不会消失。

Input

输入的第一行包括一个数ID表示数据编号, 如第一组数据中的ID = 1。注意样例数据中的ID = 0。
接下来的第一行包括两个整数N,M表示图的点数和总共加的边。
接下来M行,每行三个正整数x,y,w表示在点x和点y之间加入一条权值为w的边。
注意x和y可能相同,两条不同的边也可能连接了同一对点。
此外, w将以二进制形式从高位向低位给出,比如, 6 = 110(2),因此如果边权为 6,那么w将会是110。
1 ≤ N≤ 500, 1 ≤ M ≤ 1000, 0 ≤ L < 1000, 1 ≤ x,y≤ N

Output

输出M行,按顺序输出每一条边加入之后权值最大的割的权值。
同样,你也要以二进制形式输出,形式和输入格式中描述的形式一样。

Sample Input

0 3
6
1 2 1
1 2 1
3 3 111
1 3 101101
1 2 1011
2 3 111011

Sample Output

1 0 0
101101
101101
110000

样例解释

前三条边加入之后的答案较为显然,考虑后三条边,加入第六条边之前, 考虑点集{1,2},它对应的割只有第四条边, 因此答案就是第四条边的权值,考虑加入最后一条边以后的情况,此时点集{1,2}对应的割变成了第四条边和第六条边组成的集合,权值也发生了相应的改变。 点集{2}对应的割是第五条边和第六条边组成的集合, 可以证明这就是权值最大的割,权值为1011(2) ⊕ 111011(2) =110000(2)

题解

这个题发现一条边如果出现两次就没有贡献
这显然是一个异或问题啊
我们把每条边的权值异或到点上
然后针对每条边的时间来进行线段树的建树
把每条边的影响都找出来
然后我们在线段树上面进行分治
由于线性基不能回溯 所以我们每次下传的时候带着线性基一起下传
扫到叶子节点的时候就可以输出了
暴力计算时间复杂度有点大 我们用bitset优化
异或的结果用线性基来维护
然后发现这个题直接维护最大值就TLE了
考虑优化
发现我们在求kth小的时候有一个全新版本的线性基
就是把正常建出来的线性基拆开的那个
这个东西非常优雅 最大值就是全都异或到一起
这样的话我们就免了手写bitset比较的操作
时间复杂度得到了优化这样就过了

代码