描述

分析

• 我把文库里的粘了过来.

• 只知道点1到点N的一条路径和图中若干个环，就能通过异或，表示成所有路径。那么，需要多少环才能保证必定能表示成所有路径呢？其实，并不需要很多， 因为一些环可以通过其他的环异或得到，只需保证环是相互 独立的，两两之间存在着不同的边(乘数)。构建一棵生成树，统计非树边与生成树形成的环即可，最多只有M-N+1个环。可用dfs实现，时间复杂度为O(M)。

• 结合上述性质，可以设计贪心说法：将x表示成二进制数，从高位到低位枚举，当前位能取1则取1。

  1. 从高位到低位枚举当前位；
  2. 在a数组中选取一个当前位为1的数a[i]，假如不存在a[i]，则转1）；
  3. 假如x的当前位为0,则x=x xor a[i]；
  4. 将a数组中所有当前位为1的数a[j]与a[i]异或，a[j]=a[j] xor a[i]， 转1）。

• 最终x保证必定是最大的，时间复杂度为O (NB)。（N为a数组的大小，B为二进制位数）

• 看了上面的解析就去打了, 结果好几次都 WA. 然后跟HZWER的代码对比, 发现他在步骤2中选过的元素在后面再进行步骤2时不去考虑了.
• 资料里怎么没说…

• 改了这个地方就对了

• 1直接左移62位是会报错的. 但一次一次来就没事…

• 这个题到底和高斯消元和线性基的关系在哪?

代码

https://code.csdn.net/snippets/619907

• 首页: http://blog.csdn.net/qq_21110267