G 图上异或难题

图上异或难题

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

G 图上异或难题

这个有点水了啊。

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

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

Code

全部评论

相关推荐

11-02 09:49
已编辑
货拉拉_测试(实习员工)
热爱生活的仰泳鲈鱼求你们别卷了:没事楼主,有反转查看图片
点赞 评论 收藏
分享
11-09 01:22
已编辑
东南大学 Java
高级特工穿山甲:羡慕,我秋招有家企业在茶馆组织线下面试,约我过去“喝茶详谈”😢结果我去了发现原来是人家喝茶我看着
点赞 评论 收藏
分享
评论
10
收藏
分享
牛客网
牛客企业服务