P3430 [POI 2005] DWU-Double-row 题解

感觉是挺套路的题，考虑相邻位置之间建边，若值为 $i$ 的两个位置分别出现在第 $x$ 列和第 $y$ 列，那么：

• 若两个位置出现在同一行，则必须换，在 $x,y$ 之间连一条权值为 $1$ 的双向边。
• 若两个位置不出现在同一行，那么必须相对不换，在 $x,y$ 之间连一条权值为 $0$ 的双向边。

然后容易发现这是个二分图。直接二分图染色，对每个连通块把出现次数少的那个颜色对应的所有位置全部换位置即可满足条件。

总时间复杂度为 $O(n)$，可以通过该题。