算法
差分约束
观察到 \(a_i\) 最后是确定唯一的 + 我是从差分约束专题来的 ，考虑对于 \(a_i\) 的约束条件进行差分约束。
转化约束条件
观察到，
\[\left\{ \begin{array}{lr} b = 0, \lvert {a_u - a_v} \rvert = 1, & \\ b = 1, a_u + 1 = a_v & \end{array} \right. \]\[\Downarrow \]\[\left\{ \begin{array}{lr} a_u, a_v \in \mathbb{Z}, & \\ b = 0, a_u + 1 \geq a_v \text{ 或 } a_v + 1 \geq a_u \text{ 且 } a_u \neq a_v, & \\ b = 1, a_u + 1 \geq a_v \text{ 且 } a_u + 1 \leq a_v & \end{array} \right. \]都可以作为约束条件。
但是需要解决 \(a_u = a_v\) 的情况。
观察到原图如果不是一个二分图(存在奇环)，那么不管对于环上每一边 \((u, v)\) 的权值取 \(-1\) 还是 \(1\) ，必不可能使 \(\sum w = 0\) 。
所以原图一定是二分图。
处理方式
根据二分图性质处理
在没有奇环的情况下，一条边相连的两个点的 \(dis\) 一定奇偶性不同 ( \(w \in \{ 1, -1 \}\) 每次跑一条边必定改变 \(dis\) 奇偶性，只有存在奇环时，才能出现奇偶性不变的情况)，是不可能出现 \(a_i=a_j\) 的。
因此可以直接跑一遍即可。
终于搞懂了, 耗时 \(2 \text{ } \rm{hours}\) 。
二分图 trick
令当前考虑的边为 \((u, v)\), 其中 \(u\) 为偶数点，
令 \(a_u = 2b_u, a_v = 2b_v + 1\) ，
即可将 \(\lvert {a_u-a_v}\rvert \leq 1\) 转化为 \(b_v\leq b_u\leq b_v+1\) ，这样差值内的整数就只有 \(0/1\) 了。
这个思路来源于 ningago 的题解 。
跑差分约束
无论如何，最后枚举 \(0\) 势点，跑差分约束即可。
不会的见 差分约束模板 。
最短路应用
具体见 FutaRimeWoawaSete 的题解 。
代码
后补
总结
边权 \(\in \{ 1, -1 \}\) 时，拥有一些特殊的性质。
对于绝对值不等式，考虑变形 trick 。
标签：text,奇偶性,差分,约束,leq,array,Capitalism From： https://www.cnblogs.com/YzaCsp/p/18538982