TopCoder SRM 626 Div1 Medium NegativeGraphDiv1、Div2 Hard NegativeGraphDiv2

本番はうまい回答が思いつかなかった。
http://community.topcoder.com/stat?c=problem_statement&pm=13218
http://community.topcoder.com/stat?c=problem_statement&pm=13247

問題

N頂点からなるグラフがあり、そこに正整数値のコスト付の有向辺がE個与えられる。
この有向辺は同じ頂点対に複数複数張られることもあるし、辺の始点終点が同じ場合もある。
ここでグラフをたどり0番の頂点からN-1番の点に移動する際、コストの総和を最小化したい。

ここで、最大charges回だけ移動時のコストを加算でなく減算することができる場合、最小コストを答えよ。

Div2 HardではDiv1 MediumよりChargesの回数が少ない。

解法

まず、前提として以下の2つをWarshall-Floydを使って求めておく。

• 任意の二頂点の最短移動コスト。O(N^3)で求められる。
• 任意の二頂点の移動経路において、1回だけコスト減算を使った場合の最短移動コスト。O(N^4)で求められる。

後は数値の累乗処理のような感じで前者の最短移動コストを減らしていく。
後者をDoublingするとしてx回コスト減算を使ったコストから2*x回コスト減算を使ったコストを求める。
同様に1,2,4...,2^y回コスト減算を使った場合の最短移動コストを求められるので、chargesの2進数表記と一致する回数の最短移動コストを用いて、最初に求めて二点間の最短移動コストを更新して最小値を取っていけばよい。

log(charges)回Warshall-Floydを行うのでO(N^3*log(charges))で処理可能。

ll cost[51][51],one[51][51];
ll cost2[51][51],one2[51][51];
ll mamat[51][51];

class NegativeGraphDiv1 {
	public:
	long long findMin(int N, vector <int> from, vector <int> to, vector <int> weight, int charges) {
		int i,x,y,z;
		int E=from.size();
		
		FOR(x,N) FOR(y,N) cost[x][y]=one[x][y]=1LL<<60;
		FOR(x,N) FOR(y,N) mamat[x][y]=-1;
		FOR(x,N) cost[x][x]=one[x][x]=0;
		FOR(i,E) {
			cost[from[i]-1][to[i]-1]=min(cost[from[i]-1][to[i]-1],(ll)weight[i]);
			mamat[from[i]-1][to[i]-1]=max(mamat[from[i]-1][to[i]-1],(ll)weight[i]);
		}
		
		FOR(x,N) FOR(y,N) FOR(z,N) cost[y][z]=min(cost[y][z],cost[y][x]+cost[x][z]);
		FOR(x,N) FOR(y,N) FOR(z,N) FOR(i,N) if(mamat[z][i]>=0) one[x][y]=min(one[x][y],cost[x][z]-mamat[z][i]+cost[i][y]);
		
		while(charges>0) {
			if(charges&1) {
				FOR(x,N) FOR(y,N) cost2[x][y]=1LL<<60;
				FOR(x,N) FOR(y,N) FOR(z,N) cost2[y][z]=min(cost2[y][z],cost[y][x]+one[x][z]);
				FOR(x,N) FOR(y,N) cost[x][y]=cost2[x][y];
			}
			FOR(x,N) FOR(y,N) one2[x][y]=1LL<<60;
			FOR(x,N) FOR(y,N) FOR(z,N) one2[y][z]=min(one2[y][z],one[y][x]+one[x][z]);
			FOR(x,N) FOR(y,N) one[x][y]=one2[x][y];
			charges>>=1;
		}
		return cost[0][N-1];
	}
}

まとめ

600ptとはいえ、Doublingに気づけばコード量はさほど多くない。