RUPC 2014 day3 G : Derangement
問題
長さnの順列p[i]が与えられる。
この順列を並べ替えて、完全順列(すべてのiについて、p[i]≠iが成り立つ順列)にしたい。
並べ替えは、i番目の要素とj番目の要素をコスト|i - j| * (p[i] + p[j])かけて入れ替えることを繰り返して行う。
完全順列にするために必要なコストの最小値を求めよ。
制約条件
n≦100
方針
コストはp[i]とp[j]を独立に分離できる。
更に、元の位置と最終位置の差だけが、係数になるとしていい。
(途中で戻ったりしない入れ替え方法が必ずあるので)
なので、p[i]を位置jに送るときのコストというのは一意に定まる。
ので、最小費用流を使えば合計の最小コストが求まる。
ソースコード
int main(){ int n, p[100]; cin >> n; rep(i, n) cin >> p[i]; int s = 2 * n, t = 2 * n + 1; costflowGraph<int> g(2 * n + 2); rep(i, n){ g.add(s, i, 1, 0); g.add(i + n, t, 1, 0); } rep(i, n) rep(j, n) if(p[i] != j + 1){ g.add(i, j + n, 1, abs(i - j) * p[i]); } cout << g.min_cost_flow(s, t, n) << endl; return 0; }