【BZOJ2115】【WC2011】最大XOR和路径

没学线性基今日考试爆炸的选手

为什么每次都是一考完发现刷题列表的下几个就是考的。。

线性基其实不难。。大概就是高斯消元一样的东西

这道题首先对第一个点dfs构一棵dfs树,那么上面会挂一些环

会发现在这个树上的xor有一个神奇的性质:选择其中的一个环并异或到当前异或和中,相当于反选了一些路径而用另外一些路径代替

那么答案就是在dfs树中n点到1点的异或和再异或上若干个环的异或和

这里犯了一个错误。。我允许了不选1到n的异或和。。

说点什么

您将是第一位评论人!

提醒
wpDiscuz