题目意思非常简单,给你一张图,然后图中不能选最大相邻点,最后最大的选中的点的权值
很容易想到 没有上司的舞会 这种树形 DP 题目,但是显然,这,并不是一棵树
根据题目可得,每一个人只会有一条出边,即,这张图中,一张节点个数为 $n$ 的联通块,会有 $n$ 条边
环套树没得跑了
即每一个联通块中一定有一条边,删掉后就是树了
设这条边为 $u – v$ 的边,则 $\max(f_{u,0}, f_{u,1})$ 就是这个联通块的答案
建双向边判环即可
至于代码中的 xor ,当反向边即可
Continue reading “Luogu P2607 [ZJOI2008]骑士”