Readme

2123.Minimum-Operations-to-Remove-Adjacent-Ones-in-Matrix

本题的难点在于如何看出这是一个二分图最大匹配问题。

我们只考虑图中为1的点，每两个相邻的1之间看做存在一条边。我们发现这个图中肯定不会出现“含有奇数个节点的环”，故此图肯定可以被分割为二分图。在本题的语境就是，我们可以将所有为1的节点分为AB两组，每组内部没有边连接，所有的边都跨越这AB两组之间。

很显然，如果我们将B组里的节点都翻转为0，那么原图就会变得满足条件（原先的边现在跨接的两端是1和0）。于是根据题意，我们希望二分图的划分策略是让A里的元素越多越好，B里的元素越少越好。

那么B集合少到极致意味着什么呢？意味着B里的每一个元素都会有至少一条边通向A（否则我们就可以把它放入A而不影响二分图）；但是反之不一定，A里的某些元素可能没有边通向B（当然也不可能通向A的其他元素，否则违反了二分图的定义）。此时，我们回顾一下二分图的最大匹配的定义：指的是选取最多的跨接AB的边，但是所选取的边都不能有公共顶点。于是我们可以推理：因为B一定有一条边指向A，那么二分图的最大匹配边的数目一定就是B的个数。

于是本题就只需要套用匈牙利算法的模板，代码和1820.Maximum-Number-of-Accepted-Invitations 非常相似。