经典傻逼题

时间限制：10s 空间限制：512MB

题目描述

这是一道经典傻逼题，对经典题很熟悉的人也不要激动，希望大家不要傻逼。

考虑一张N个点的带权无向图，点的编号为1到N。对于图中的任意一个点集

（可以为空或者全集），所有恰好有一个端点在这个点集中的边组成的集合被称

为割。一个割的权值被定义为所有在这个割上的边的异或和。

一开始这张图是空图，现在，考虑给这张无向图不断的加边，加入每条边之

后，你都要求出当前权值最大的割的权值，注意加入的边永远都不会消失。

输入格式

输入的第一行包括一个数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

输出格式

输出M行，按顺序输出每一条边加入之后权值最大的割的权值。

同样，你也要以二进制形式输出，形式和输入格式中描述的形式一样。

样例输入

样例输出

1 0 0
101101
101101
110000

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

提示

没有写明提示

题目来源

没有写明来源