Luogu4643 [国家集训队] 阿狸和桃子的游戏

题意 ： 给出一张 个点 条边的无向图，边有边权，可正可负。

两人轮流对点染色，先手将点染成黑色，后手将点染成白色，每个点只能被染色一次。

记 为点集 的导出子图的边权和。

设最终黑色点的集合为 ，白色点的集合为 ，则这轮游戏的得分为 。

先手想最大化这个值，后手想最小化这个值，若两人均采用最佳决策，问最终游戏的得分。

，，时限 。

---

结论题。

将每个点的点权设为与其相连的边权和的一半。设 为点集 的点权和。

对于任意一种局面， 。

• 证明：对于权为 的边 。

  若 一个 ，一个属于 ，则在 中无贡献。在 中则是两边各加 ，恰好抵消。

  若 均 则在 中 贡献了 。在 中贡献了 。

  均 的情况类似。

  综上，每条边的贡献都相同。

对于转化后的问题，只需要每次贪心选取点权最大的点即可。

时间复杂度 。