G 图上异或难题

图上异或难题

https://ac.nowcoder.com/acm/contest/63804/G

G 图上异或难题

这个有点水了啊。

考虑边权转点权,方法和证明类似于 这个,我们设每个点的点权为所有连边的边权异或和。问题转化为一堆数最大子集异或和,线性基板子。

证明为什么这样的转化是对的:如果涂黑为选中,对于一条边 ,如果都选中,那么异或之后会抵消。如果都没选中,就直接为 不影响结果。如果一个选中一个没选中, 恰好为边权。

Code

全部评论

相关推荐

牛客60022193...:大厂都招前端,他们觉得AI能替代前端,可能他们公司吊打btaj吧
点赞 评论 收藏
分享
评论
10
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务