CF1610F Mashtali: a Space Oddysey

题意

现在有一个由 个节点 条边组成的无向图，每条边的边权
令 表示 所有出边的权值和，令 表示 所有入边的权值和，一个点 是好的，当且仅当
给每一条边定向，使得图上好的点最多，输出任意一种方案

题解

令 表示点 边权为 的边的个数， 表示点 边权为 的出边的数量减去边权为 的入边的数量

上界 能够达到

考虑欧拉回路

建立新图，对于原图上一条边 ，若 ，新图上有 ，否则有

可以保证

若 ，还要保证 ，连边

再添加一个节点 ，与目前度数为奇数的点连边

最后跑一遍欧拉回路定向，把边的方向对应回原图

时间复杂度为

代码 codeforces submission 145198606