有M，一个n × n的矩阵，每一项等于0或1。m <子> ij子> i。交换矩阵M的第i行和第j行表示以下动作:我们将值mik和mjk交换为k = 1,2 .....n.交换两列类似地定义。我们说M是可重新排列的，如果有可能交换其中的一些行对和一些列对(在任何序列中)在所有的交换之后，M的所有对角线项都等于1。
我需要找到一个多项式时间算法来确定一个矩阵是否0-1项的M是可重新排列的
我知道我必须使用最大流量/最小切割范式来解决这个问题，但我找不到一种将这个问题与最大流量问题联系起来的方法。
欢迎任何提示!
很容易证明一个矩阵是可重排的当且仅当Sn中存在一个排列pi，使得Mi, pi(i)对每一个i都= 1。
这样的排列恰好是在二部图中，当Mij = 1时，每一行有一个顶点，每一列有一个顶点，并且在第i行和第j列之间有一条边的完美匹配。
用max-flow在二部图中寻找最大匹配是很简单的;当最大匹配是完美匹配时，你有一个可重新排列的矩阵