G 图上异或难题

图上异或难题

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

G 图上异或难题

这个有点水了啊。

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

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

Code

全部评论

相关推荐

不愿透露姓名的神秘牛友
11-24 20:53
点赞 评论 收藏
分享
11-26 17:09
华南理工大学 后端
offer选择 华为 蚂蚁 pdd
蚂蚁 基架java (n+6)*16 签字费若干
点赞 评论 收藏
分享
10-10 17:54
点赞 评论 收藏
分享
头像
11-13 11:12
门头沟学院 Java
点赞 评论 收藏
分享
11-26 15:52
西京学院 Java
点赞 评论 收藏
分享
评论
10
收藏
分享

全站热榜

正在热议
# 拼多多求职进展汇总 #
240857次浏览 2051人参与
# 实习，投递多份简历没人回复怎么办 #
2448329次浏览 34802人参与
# 北方华创开奖 #
68081次浏览 558人参与
# 25届秋招总结 #
426514次浏览 4314人参与
# 虾皮求职进展汇总 #
101004次浏览 811人参与
# 地方国企笔面经互助 #
7424次浏览 18人参与
# 阿里云管培生offer #
65729次浏览 1769人参与
# ai智能作图 #
35900次浏览 439人参与
# 中兴求职进展汇总 #
471274次浏览 2453人参与
# 我在牛爱网找对象 #
75257次浏览 556人参与
# 双非有机会进大厂吗 #
106302次浏览 1335人参与
# 实习想申请秋招offer，能不能argue薪资 #
38111次浏览 313人参与
# 机械求职避坑tips #
24240次浏览 252人参与
# 发工资后，你做的第一件事是什么 #
10848次浏览 53人参与
# 25届机械人为了秋招做了哪些准备？ #
26827次浏览 366人参与
# 投格力的你，拿到offer了吗？ #
47938次浏览 337人参与
# 我的实习求职记录 #
6146492次浏览 84093人参与
# 投递实习岗位前的准备 #
1193973次浏览 18511人参与
# 机械人怎么评价今年的华为 #
158508次浏览 1354人参与
# 在职场上，你最讨厌什么样的同事 #
6496次浏览 98人参与
# 实习与准备秋招该如何平衡 #
726195次浏览 8569人参与
# 华为工作体验 #
112553次浏览 871人参与
牛客网
牛客企业服务