XSY1762

题意

给定一张(n)个点(m)条边的无向图。每个顶点有一个颜色，要么是黑，要么是白。我们想进行一些操作，使得最终每一条边的两个端点都是不同的颜色。每一次操作，你可以将一条边的两个端点交换颜色。求最少的操作次数和具体的操作方式。(nleq 500)

做法

黑白染色
原来是黑色的(i)：(Slongrightarrow i(flow:1,cost:0))
最后是黑色的(i)：(ilongrightarrow T(flow:1,cost:0))
边((u,v))：(ulongrightarrow v(flow:infty,cost:1),vlongrightarrow u(flow:infty,cost:1))

跑最小费用流即可，对于一条路径((x_1,x_2,...,x_k))（不包括(S,T)）
若(k>1)，(x_1=1,x_k=0)，需要用(k-1)次具体操作，仅将(x_1)与(x_k)交换

(101000100)，(|10|1000|100|)，(|01|0001|001|)，(|00|1000|101|)
具体来讲，划分为，左端点为(1)，区间内其他为(0)的极大区间，这样的区间，然后每个左端点的(1)移到右端点，再把中间的右端点(1)移到相邻区间的左端点