题解 P3430 【[POI2005]DWU-Double-row】
看到楼上两位大佬的题解没有证明，于是我就说两句
写在前面
做到这题时我思考了良久，看完题解后又有一种奇怪的感觉，如果你也觉得这道题有一种玄乎的感觉，不妨看一下这篇题解
策略
如果两个相同的数在不在同一行，给两个数所在的列的编号连一条边权为0的边
如果两个相同的数在同一行，给两个数所在的列的编号连一条边权为1的边
给每个联通块的点黑白染色（1边连接的点颜色相反，0边连接的点颜色相同），答案每次加上每个联通块黑点和白点个数的最小值（联通块是什么，请往下看）
证明
数的性质
首先我们分析这个题给出的数的性质，发现两个相同数在同一行的话，必须把一个数交换下去，那我们不妨设每一列交换后状态为黑,交换前状态为白，显然一个列要么被交换了，要么没被交换。我们连1的边说明这两列一定不在同一个状态里，连0的边说明两列一定在同一个状态里。
联通快性质
首先，我们只给相同的数所在的列连边，考虑所有可能有贡献的边（有贡献指不是自环的边），最多n个相同的数，所以最多n条边。每一列有两个格子，所以每一列最多连两条边，于是，联通块的性质很显然了，要么是环，要么是链。
染色性质
首先，如果联通块是链，那黑白染色取最小色块是非常显然的，因为交换最小需要改变的状态是最优的且一定可行的
的我们考虑环，环上唯一存在的问题就是，是否会出现奇数个权值为1的边，使两点不能匹配
我们先考虑一组不需要交换的数列，例如
1 2 3 4 5
5 1 2 3 4这里面的数两两相连，构成了一个边权都为0的图，接着考虑发生冲突
1 2 3 3 4
4 1 2 5 5我们知道每列最多连两条边，如果这一列发生冲突，则此列剩余能连的边只剩下一条，另一列冲突同理，此时发生冲突的行里可用点减少了两个，我们又知道，如果用0边连接两个列，需要每行各取一个点，所以我们想把这冲突的两列用奇数个1边连成环是不可能的。