algorithm - 最大流量应用：重新排列矩阵

Question

有M，一个 nxn 矩阵，每个条目等于 0 或 1。 m _ij 表示第 i 行和第 j 列中的条目。对角线条目是某些 i的 m _{ii形式之一。}交换矩阵 M 的 i 和 j 行表示以下操作：我们交换值 m _ik和 m _jk，因为 k = 1, 2 ..... n。交换两列的定义类似。如果可以交换一些行对和一些列对（以任何顺序），那么我们说M是可重排的，使得在所有交换之后，M 的所有对角线条目都等于 1。

我需要找到一个多项式时间算法来确定具有 0-1 个条目的矩阵 M 是否可重新排列。

我知道我必须使用 max-flow/min-cut 范例来解决这个问题，但是我找不到将这个问题与 max-flow 问题联系起来的方法。

欢迎任何提示！

Answer 1

很容易证明矩阵是可重排的当且仅当在 S _n中存在一个置换 pi使得每个 i 的 M _{i, pi(i)} = 1。

这样的排列只是二分图中的完美匹配，每行有一个顶点，每列有一个顶点，当 M _ij = 1 时，第 i 行和第 j 列之间有一条边。

使用 max-flow 在二分图中找到最大匹配非常简单；当最大匹配是完美匹配时，您有一个可重新排列的矩阵。