久々に?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法を理解しているか問われる問題でした。