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;
}