阿狸和桃子正在玩一个游戏游戲是在一个带权图G=(V, E)上进行的,设节点权值为w(v)边权为c(e)。游戏规则是这样的:
1.阿狸和桃子轮流将图中的顶点染色阿狸会将顶点染成红色,桃子会将顶点染成粉色已经被染过色的点不能再染了,而且每一轮都必须给一个且仅一个顶点染色
2.为了保证公平性,节点的个数N为偶數
3.经过N/2轮游戏之后,两人都得到了一个顶点集合对于顶点集合S,得分计算方式为
由于阿狸石头剪子布输给了桃子所以桃子先染色。兩人都想要使自己的分数比对方多且多得越多越好。如果两人都是采用最优策略的求最终桃子的分数减去阿狸的分数。
本题大意为每囚选一个点最后输出先选的人的点边权值和减去后选人的点边权值和。