自动搬运

查看原文

来自洛谷，原作者为

	Accoty_AM 奋力一搏

搬运于2025-08-24 21:48:55，当前版本为作者最后更新于2019-08-12 16:10:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看到楼上两位大佬的题解没有证明，于是我就说两句

写在前面

做到这题时我思考了良久，看完题解后又有一种奇怪的感觉，如果你也觉得这道题有一种玄乎的感觉，不妨看一下这篇题解

策略

如果两个相同的数在不在同一行，给两个数所在的列的编号连一条边权为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边连成环是不可能的。

所以，这样连边后，列之间一定能形成完美的状态匹配，根据状态匹配贪心取最小即可

证毕