题意
做法
结论:合法的必要条件为图为二分图
证明:
一条边的两端(a_i)奇偶性不同
我们的操作可以描述成:
(a_u-a_v=1)或(|a_u-a_v|=1)
考虑差分约束
(a_u-a_v=1)显然
(|a_u-a_v|=1)考虑化成(a_u-a_vle 1,a_v-a_ule 1)
正确性:
即证明(|a_u-a_v|=1)不会存在(a_u=a_v)
我们发现上述连边均满足(a_i)奇偶不同,故不会存在(a_u=a_v)的情况
剩下的比较简单就不讲了
结论:合法的必要条件为图为二分图
证明:
一条边的两端(a_i)奇偶性不同
我们的操作可以描述成:
(a_u-a_v=1)或(|a_u-a_v|=1)
考虑差分约束
(a_u-a_v=1)显然
(|a_u-a_v|=1)考虑化成(a_u-a_vle 1,a_v-a_ule 1)
正确性:
即证明(|a_u-a_v|=1)不会存在(a_u=a_v)
我们发现上述连边均满足(a_i)奇偶不同,故不会存在(a_u=a_v)的情况
剩下的比较简单就不讲了