考虑一个* n二进制矩阵。此矩阵的每个单元格最多具有4个邻居（如果存在）。如果它们的邻居和它们的值不相等，我们称此矩阵的两个单元格不兼容。我们为每个不兼容的对支付$ b。同样，我们可以通过支付$ a来更改单元格的值。
问题是找到此矩阵的最低成本。
我已经使用过回溯功能，并找到的算法O(2 ^ (n * n))。有人可以帮助我找到更有效的算法吗？
O(2 ^ (n * n))
这个想法归因于Greig，Porteous和Seheult。将矩阵视为具有电容能力的有向图，其顶点对应于矩阵条目，并且从每个顶点到其四个邻居的弧均具有容量 b 。引入另外两个顶点，一个源和一个汇点，以及一个容量为 a的 弧：从源到具有相应0条目的每个顶点，再从每个顶点具有相应1条目的容量 到 弧。找到最小切割；更改后值为0的条目是剪切的源侧的顶点，而更改后值为1的条目是剪切的宿侧的顶点。
削减成本正是您的目标。的能力的 一个 从源弧，那些跨越切口对应于从0变为1的能力的 一个 到水槽弧，那些跨越切口对应于从1变为0的能力的 b 弧，穿过切口的弧对应于从0到1的弧的情况。
