CF1610F Mashtali: a Space Oddysey

题意

现在有一个由 $n$ 个节点 $m$ 条边组成的无向图，每条边的边权 $w\in\{1, 2\}$
令 ${d^+}_u$ 表示 $u$ 所有出边的权值和，令 ${d^-}_u$ 表示 $u$ 所有入边的权值和，一个点 $u$ 是好的，当且仅当 $|{d^+}_u-{d^-}_u|=1$
给每一条边定向，使得图上好的点最多，输出任意一种方案

$n,m\le3\times10^5$

题解

令 $c_{w, u}$ 表示点 $u$ 边权为 $w$ 的边的个数，$s_{w, u}$ 表示点 $u$ 边权为 $w$ 的出边的数量减去边权为 $w$ 的入边的数量

上界 $\sum\limits_u [c_{1, u}\bmod 2=1]$ 能够达到

考虑欧拉回路

建立新图，对于原图上一条边 $(u, v, w)$，若 $w=1$，新图上有 $(u, v)$，否则有 $(u+n, v+n)$

可以保证 $|s_{w,u}|=c_{w,u}\bmod 2$

若 $c_{1, u}\bmod 2=c_{2, u}\bmod 2=1$，还要保证 $\text{sgn}(s_{1, u})\not=\text{sgn}(s_{2, u})$，连边 $(u, u+n)$

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

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

时间复杂度为 $\Theta(n+m)$

代码 codeforces submission 145198606