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か所もオーバーフロー作りこんでしまった…。