G 图上异或难题
图上异或难题
https://ac.nowcoder.com/acm/contest/63804/G
G 图上异或难题
这个有点水了啊。
考虑边权转点权,方法和证明类似于 这个,我们设每个点的点权为所有连边的边权异或和。问题转化为一堆数最大子集异或和,线性基板子。
证明为什么这样的转化是对的:如果涂黑为选中,对于一条边 ,如果都选中,那么异或之后会抵消。如果都没选中,就直接为 不影响结果。如果一个选中一个没选中, 恰好为边权。
图上异或难题
https://ac.nowcoder.com/acm/contest/63804/G
这个有点水了啊。
考虑边权转点权,方法和证明类似于 这个,我们设每个点的点权为所有连边的边权异或和。问题转化为一堆数最大子集异或和,线性基板子。
证明为什么这样的转化是对的:如果涂黑为选中,对于一条边 ,如果都选中,那么异或之后会抵消。如果都没选中,就直接为 不影响结果。如果一个选中一个没选中, 恰好为边权。
相关推荐