$1,2,...,N$ を並べ替えた順列がある。2つの異なる数字 $i$, $j$ を選んで入れ替えることを繰り返してソートされた状態( $1,2,...,N$ の順番に並んだ状態)にしたい。 数字 $i$, $j$ を入れ替える度にコストが $c_{i,j}$ 必要になる。
順列 $p$ に対して、 $p$ をソートするのに必要な最小コストを $f(p)$ とする。 $f(p)$ のとりうる最大値を求めよ。
入力は以下のフォーマットに従う。与えられる数は全て整数である。
$N$ $c_{1,1}$ $c_{1,2}$ $...$ $c_{1,N}$ $c_{2,1}$ $c_{2,2}$ $...$ $c_{2,N}$ $...$ $c_{N,1}$ $c_{N,2}$ $...$ $c_{N,N}$
最大値を1行に出力せよ。
3 0 1 3 1 0 8 3 8 0
5
もっとも必要コストが大きい順列は$\{1,3,2\}$で、
以上の操作によりコスト5でソートでき、またこれが最善であることが証明できる。 他の順列もコスト5以下でソートできることを示すことができる。