Mは、各エントリが0 または 1 に等しい nxn 行列です。m ij は、行 i と列 j のエントリを示します。対角線のエントリは、いくつかの i に対する m iiの形式の 1 つです。行列 M の行 i と j を交換することは、次のアクションを意味します。k = 1, 2 ..... nの値 m ikと m jkを交換します。2 つの列の交換も同様に定義されます。行の対の一部と列の対の一部を (任意の順序で) 交換でき、すべての交換後に M のすべての対角要素が 1 に等しくなる場合、 Mは再配置可能であると言います。
エントリが 0 ～ 1 の行列 M が再配置可能かどうかを判断する多項式時間アルゴリズムを見つける必要があります。
これを解決するには max-flow/min-cut パラダイムを使用する必要があることはわかっていますが、この問題を max-flow 問題に関連付ける方法が見つかりません。
どんなヒントでも大歓迎です！