TopCoder SRM 710 Div2 Hard MinMaxMax

久々に？Div2 Hardを自力で解けず。
https://community.topcoder.com/stat?c=problem_statement&pm=14545

問題

N頂点M辺の連結グラフが与えられる。
各頂点には重さV、各辺には重さWが設定されている。
2頂点u,v,間のコストD(u,v)は、u→vに至る経路のうち、(頂点の重さの最大値)×(辺の重さの最大値)の最小値とする。
各(u,v)に対するD(u,v)の総和を求めよ。

解法

一応以下の値をダイクストラ法で解くと解けないことはないが、O(N^2*M*logN)かかり、最後のlogNの分でTLEする。
f(s,a,b) := 頂点の初期位置sと、現在位置をaとし、経由した頂点の重さの最大値bであるときの経由した辺の重さの最大値の最小値

Warshall-Floid法をアレンジすると、O(N^3)で解ける。
各頂点対に対し、D(u,v)のほか、経由した辺の最大値の最小値E(u,v)を求めていこう。

ふつうのWF法では3重ループの一番外側の値は頂点番号を0番から順に見ていく。
しかしここでは頂点の重さvの小さい順に処理していこう。

初期状態では、E(u,v)はもともと辺がある場合はその値、ない場合は無限大相当の値が入っている。
ここで、頂点を増やすことで他の辺を利用可能となり、E(u,v)が小さくなることを考える。
その3重ループの一番外側の頂点番号をzとする。

zを介した移動経路が増えることで、下記の通りE(u,v)の値が小さくなる可能性がある。
E(u,v) = min(E(u,v), max(E(u,z),E(z,v))
一方経由する頂点の重さの最大値はV[z]となるので
D(u,v) = min(D(u,v), E(u,v) * min(V[x],V[y],V[z]))
で更新される。

ll minw[303][303];
ll mind[303][303];

class MinMaxMax {
	public:
	long long findMin(vector <int> a, vector <int> b, vector <int> w, vector <int> v) {
		int N=v.size();
		int i,x,y;
		pair<int,int> P[303];
		FOR(i,N) P[i]={v[i],i};
		sort(P,P+N);
		
		FOR(y,N) FOR(x,N) minw[x][y]=1LL<<40;
		FOR(y,N) FOR(x,N) mind[x][y]=1LL<<60;
		FOR(i,a.size()) minw[a[i]][b[i]]=minw[b[i]][a[i]]=w[i];
		
		FOR(i,N) {
			int z=P[i].second;
			FOR(x,N) FOR(y,N) {
				minw[x][y] = min(minw[x][y], max(minw[x][z],minw[z][y]));
				mind[x][y] = min(mind[x][y], 1LL*minw[x][y] * max({v[x],v[y],v[z]}));
			}
		}
		
		
		ll tot=0;
		FOR(y,N) FOR(x,y) tot+=mind[x][y];
		
		return tot;
	}
}

まとめ

ちゃんとWF法を理解しているか問われる問題でした。