AOJ2230: How to Create a Good Game

LP MinCostFlow

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2230

LP双対の問題。似たような問題でLongest Shortest Pathがあるのでそれの解説スライドを見ながら考察した。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2736


まず最長距離の双対を取ってポテンシャルに言い換える。
すると条件は
max (Σx)
s.t.
d[t]-d[s]<=D (双対変数F)
d[u]-d[v]+xe<=-le (for all e=(u,v)) (双対変数fe)
となる。(新しくdという変数を追加するのがポイント)

これの双対をとると
min Σ(-ce*fe)+D*F
(sから出る辺のfeの合計)>=F ...(1)
(vから出る辺のfeの合計)-(uに入る辺のfeの合計)>=0 ...(2)
(tに入る辺のfeの合計)<=F ...(3)
fe >= 1 ...(4)

(2)について考えると、各点で水が足される可能性があるとみてよい。
なのでF'(>=F)だけsから流されたとすると、tはF''(>=F')だけ水を受け取ることになる。
しかし、(3)の条件よりF''=F'=Fとなり、
(1)(2)(3)<=>
(sから出る辺のfeの合計)=F
(vから出る辺のfeの合計)-(uに入る辺のfeの合計)=0
(tに入る辺のfeの合計)=Fとなり、これは流量条件である。

(4)と合わせてこの問題は、
各辺1の最小流量制約があるグラフにおいて、M=(Fだけ水を流したときのコスト)+D*Fを最小化する問題に言い換えられた。

Fを固定すれば
(Fだけ水を流したときのコスト)については最小費用流で最小化すればよい。

また流量FのフローはF本のsからtへのpathに分解できることに留意すると、
流量をさらに1増やしたとき新しくpathが追加されるが、その長さはDより小さい。
よってFを増やすとMは必ず大きくなるので、F=(すべての辺をpathでカバーする際の本数の最小値)となる。これはにぶたんで求めてもいいし、sとtに辺を張って一発で求めることもできる。
にぶたんのupper_boundをMではなくNにしてしまいこれのせいで時間を無限に溶かした。過去の自分のブログを見返したら同じミスをしていて笑った。

また上の式を見てもらえばわかるが、最小費用流の双対は
d[u]-d[v]+xe<=leのような形をしていることがわかる。
http://tokoharuland.hateblo.jp/entry/2016/12/06/223614
を見て貰えばわかるが、最大流量の制約も追加すると式はd[u]-d[v]+xe-ye<=leのようになる。3or4変数の式がたくさん出てきたら最小費用流の双対を疑うべき。


下はsからtへ辺を張る方法でFを求めている。

int N, M, F;
int A[MAX_N], B[MAX_N], C[MAX_N];
int S[MAX_N];

void solve() {
	cin >> N >> M;
	MCF::init(N);
	rep(i, 0, M) {
		cin >> A[i] >> B[i] >> C[i];
		MCF::add_edge(A[i], B[i], inf, 0);
		MCF::add_edge(A[i], B[i], 1, -2);
	}
	MCF::add_edge(0, N - 1, inf, -1);
	int f = MCF::get(0, N - 1, M) + 3 * M;

	int res = 0;
	int s = N, t = N + 1;
	MCF::init(N + 2);
	S[0] = -f;
	S[N - 1] = f;
	rep(i, 0, M) {
		MCF::add_edge(A[i], B[i], inf, -C[i]);
		S[A[i]]++; S[B[i]]--;
		res += -C[i];
	}
	int d = MCF::get_longest(0, N - 1);
	F = 0;
	rep(i, 0, N) {
		if(S[i] > 0) MCF::add_edge(i, t, S[i], 0);
		if(S[i] < 0) {
			MCF::add_edge(s, i, -S[i], 0);
			F += -S[i];
		}
	}
	res += MCF::get(s, t, F);
	cout << res + d * f << "\n";
}

高難易度の問題はWA出すと本質が間違っているのではないかと疑いがち。自信を持ってください。