TopCoder SRM 561 Div2 Hard FoxAndTouristFamilies

続いてDiv2 Hard。
これはなかなかお手頃な問題。
http://community.topcoder.com/stat?c=problem_statement&pm=11811

木構造のグラフが与えられる。また、複数の家族の初期位置が与えられる。
各家族は、初期位置以外の点を目的地としてランダムに選んで初期位置から移動するとき、全家族が通る辺の数の期待値を答える。

これは、各辺に対して各家族が目的地として初期位置から辺を挟んで反対側にいる確率を掛け合わせ、辺ごとの和を取ればよい。
各点が辺を挟んでどちら側にいるかは、先にFloydで点同士の距離を計算しておき、辺の両端の点の近い方にいると考えればよい。

static const int FMAX = 100;
int inf=1<<29;
int dist[FMAX+1][FMAX+1],edge[FMAX+1][FMAX+1];
void floyd(int MV) {
	int i,j,k;
	FOR(i,MV) FOR(j,MV) dist[i][j]=edge[i][j];
	FOR(i,MV) FOR(j,MV) FOR(k,MV) dist[j][k] = min(dist[j][k], dist[j][i]+dist[i][k]);
}

class FoxAndTouristFamilies {
	public:
	int V,F;
	int closer(int L,int R,int T){ return (dist[L][T] < dist[R][T])?0:1; }
	int NL(int L,int R){
		int i,j=0;
		FOR(i,V) if(dist[i][L] < dist[i][R]) j++;
		return j;
	}
	
	double expectedLength(vector <int> A, vector <int> B, vector <int> f) {
		int i,j;
		V=A.size()+1;
		F=f.size();
		FOR(i,V) FOR(j,V) edge[i][j]=inf;
		FOR(i,V) edge[i][i]=0;
		FOR(i,A.size()) edge[A[i]][B[i]]=edge[B[i]][A[i]]=1;
		floyd(V);
		double res=0;
		FOR(i,A.size()) {
			int nL = NL(A[i],B[i]);
			int nR = V-nL;
			double can=1;
			FOR(j,F) {
				int h = f[j];
				
				if(closer(A[i],B[i],h)==0) can *= nR / (double)(V-1);
				else can *= nL / (double)(V-1);
			}
			res += can;
		}
		return res;
	}

};

まとめ

これはすぐ回答が思いついたし１発でSystem Testに通ったので良かった。
ついでにFloydアルゴリズムもライブラリにしといた。