TopCoderOpen 2014 Round2C Medium CliqueGraph

無理やり定数倍高速化で解こうとして失敗した。
http://community.topcoder.com/stat?c=problem_statement&pm=13251

問題

N頂点からなるグラフがある。
このグラフはクリークを連結した形で構成されている。
各クリークは配列V[i]とsizes[j]で表現され、V[sizes[j]], V[sizes[j]+1], V[sizes[j]+2] ... V[sizes[j-1]-1]がクリークである。

この時、頂点対の最短距離の総和を求めよ。

解法

N<=2500のため、Warshall-FloydやDijkstraのように最悪O(N^3)かかる手法はTLEする。
今回の問題では、愚直に処理すると辺の数が大きいが、クリークを構成する頂点数及びクリーク数の積は高々len(V)であることを利用して処理を軽量化する。

P頂点のクリークを表現する際、愚直にP(P-1)/2辺で表現すると辺の数が多くなる。
ここはクリークを代表する仮想的な点を置き、そことP個の頂点を結ぶとP辺でクリークを表現できる。
(ただし頂点間の移動に2辺を通ることになるので、距離の計算には要注意)

この状態では辺は高々len(V)本なので、DijkstraをN回行ってもO(N*|V|*log|V|)でちょっと重いが何とか2sは切れる。
以下のコードはpriority_queue使ってるけど、各辺の距離は同じなので別に普通のqueueでも良かったね。

vector<int> E[5001];

class CliqueGraph {
	public:
	long long calcSum(int N, vector <int> V, vector <int> sizes) {
		int i,x,y,j;
		int SS=sizes.size();
		
		y=0;
		FOR(i,5000) E[i].clear();
		FOR(i,sizes.size()) {
			FOR(x,sizes[i]) {
				E[V[y+x]].push_back(2500+i);
				E[2500+i].push_back(V[y+x]);
			}
			y+=sizes[i];
		}
		
		ll ret = 0;
		FOR(i,N) {
			int dist[5001];
			FOR(j,5000) dist[j]=10000;
			dist[i]=0;
			priority_queue<pair<int,int> > Q;
			Q.push(make_pair(0,i));
			while(!Q.empty()) {
				pair<int,int> p=Q.top();
				Q.pop();
				int cd=-p.first;
				int cur=p.second;
				FOR(x,E[cur].size()) {
					int tar=E[cur][x];
					if(dist[tar]>cd+1) {
						dist[tar]=cd+1;
						if(tar<2500) ret+=dist[tar];
						Q.push(make_pair(-dist[tar],tar));
					}
				}
			}
		}
		return ret/4;
	}
}

まとめ

クリークをP(P-1)/2本の辺ではなく仮想点+P辺で表現するテクは、今後も使えそうだし覚えておかねば。