Codeforces #250 Div1 B. The Child and Zoo

Bの割には少しややこしい。
http://codeforces.com/contest/438/problem/B

問題

N個の頂点からなる連結グラフが与えられる。
各頂点には数値A[i]が振られている。

ある点p→qに至るパスの値とは、p→qに至るまでに経由する各頂点の最小値である。
この時、f(p,q)はp→qに至るパスのうち、適切なパスを選ぶことで得られるパスの値の最大値とする。
f(p,q)の全p,qの平均値、すなわちを答えよ。

解法

f(p,q)は、p→qに至るパスのうち、そこを通らないといけない頂点の最小値である。
逆に、グラフを値の大きな点から順に構築していき、ある点を追加したときに初めて移動可能となるパスp→qがあると、f(p,q)の値はその追加した点の値となる。

よって、値の大きい順にグラフを構築していき、Union-findを使って連結済み頂点を管理して、値rの点を追加することで初めて連結した点同士について、f(p,q)=rを足し合わせていけばよい。

class UF {
	public:
	static const int ufmax=100002;
	int ufpar[ufmax],ufrank[ufmax];
	UF() { init();}
	void init(){int i; FOR(i,ufmax) { ufpar[i]=i; ufrank[i]=0; } }
	int find(int x) {	return (ufpar[x]==x)?(x):(ufpar[x] = find(ufpar[x]));}
	int operator[](int x) {return find(x);}
	void unite(int x,int y) {
		x = find(x); y = find(y);
		if(x==y) return;
		if(ufrank[x]<ufrank[y]) ufpar[x]=y;
		else {ufpar[y]=x; if(ufrank[x]==ufrank[y]) ufrank[x]++;}
	}
};

int N,M;
int A[100001],rev[100001];
pair<int,int> P[100001];
vector<int> E[100001];
int num[100001];
double ret=0;
UF uf;
void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>M;
	
	uf.init();
	FOR(i,N) {
		cin>>x;
		P[i]=make_pair(x,i);
		num[i]=0;
	}
	sort(P,P+N);
	reverse(P,P+N);
	FOR(i,N) rev[P[i].second]=i;
	
	FOR(i,M) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	FOR(i,N) {
		int id=P[i].second;
		set<int> S;
		int nt=0;
		FOR(j,E[id].size()) if(rev[E[id][j]]<i) S.insert(uf[E[id][j]]);
		ITR(it,S) ret += P[i].first*1LL*num[*it]*nt, nt+=num[*it];
		ret += nt*(ll)P[i].first;
		ITR(it,S) uf.unite(id,*it);
		num[uf[id]]=nt+1;
	}
	
	_P("%.12lf\n",2*ret/(N*(N-1.0)));
}

まとめ

アプローチはあってたのに、2か所もオーバーフロー作りこんでしまった…。