Codeforces Round #250 DIV1 B問題/DIV2 D問題 - The Child and Zoo

Source

Codeforces Round #250 DIV1 B問題 (1000pt)
Codeforces Round #250 DIV2 D問題 (2000pt)
Problem description

問題概要

動物園を表す，$N$ 個のノード，$M$ 個の枝からなる連結な無向グラフが与えられる．
各ノード $k$ に対して，そのノードにいる動物の数 $A_k$ が与えられる．
あるノード $u$ からあるノード $v$ に移動するのに，（動物の数が少ないノードはつまらないので）通るノードの中で最も動物の少ないノードの動物の数を最大となるようなルートを通る．
その最大値を $f(u,v)$ と書く．
ランダムに異なる $2$ ノード $u,v$ を選ぶときの $f(u,v)$ の期待値を求める問題．

解法

$\sum f(u,v)$ を求めれば，後は，$N(N-1)$ で割れば良い．
枝の重みとして，両端の動物数のうちの少ない方を取る．
Union Findで枝の重みが大きい方から，ノードをつなげていく処理を行う．
Union Findでは，各連結部分の大きさ（含まれるノード数）も覚えておき，新しく繋がるときに，新しく行き来可能となるノードのペアの数と枝の重みをかけて，答えに足していけば良い．

C++のスパゲッティなコード

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define READER_BUF_SIZE 1048576
#define WRITER_BUF_SIZE 1048576
int reader_pt=READER_BUF_SIZE,reader_last;char reader_buf[READER_BUF_SIZE];
int writer_pt=0;char writer_buf[WRITER_BUF_SIZE];
#define mygc(c) {if(reader_pt==READER_BUF_SIZE)reader_pt=0,reader_last=fread(reader_buf,sizeof(char),READER_BUF_SIZE,stdin);(c)=reader_buf[reader_pt++];}
#define mypc(c) {if(writer_pt==WRITER_BUF_SIZE)writer_pt=0,fwrite(writer_buf,sizeof(char),WRITER_BUF_SIZE,stdout);writer_buf[writer_pt++]=(c);}
#define myed {fwrite(writer_buf,sizeof(char),writer_pt,stdout);writer_pt=0;}

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(int *x, int *y){reader(x);reader(y);}

void unionInit(int d[],int s){int i;rep(i,s)d[i]=i;}
int unionGet(int d[],int n){int t=n,k;while(d[t]!=t)t=d[t];while(d[n]!=n)k=d[n],d[n]=t,n=k;return n;}
int unionConnect(int d[],int a,int b){a=unionGet(d,a);b=unionGet(d,b);if(a==b)return 0;d[a]=b;return 1;}

void intIntIntSort(int d[],int m1[],int m2[],int s){int i=-1,j=s,k,t;if(s<=1)return;k=(d[0]+d[s-1])/2;for(;;){while(d[++i]<k);while(d[--j]>k);if(i>=j)break;t=d[i];d[i]=d[j];d[j]=t;t=m1[i];m1[i]=m1[j];m1[j]=t;t=m2[i];m2[i]=m2[j];m2[j]=t;}intIntIntSort(d,m1,m2,i);intIntIntSort(d+j+1,m1+j+1,m2+j+1,s-j-1);}

int N, M, A[200000];
int x[200000], y[200000], c[200000];

int ind[200000], sz[200000];

int main(){
  int i, j, k, l;
  double res = 0;

  reader(&N,&M);
  rep(i,N) reader(A+i);
  rep(i,M) reader(x+i, y+i), x[i]--, y[i]--;

  rep(i,M) c[i] = min(A[x[i]], A[y[i]]);
  intIntIntSort(c,x,y,M);

  unionInit(ind, N);
  rep(i,N) sz[i] = 1;

  for(k=M-1;k>=0;k--){
    i = unionGet(ind, x[k]);
    j = unionGet(ind, y[k]);
    if(i==j) continue;
    res += 2.0 * c[k] * sz[i] * sz[j];
    unionConnect(ind, i, j);
    l = unionGet(ind, i);
    sz[l] = sz[i] + sz[j];
  }

  res /= N;
  res /= N-1;
  printf("%.10f\n",res);

  myed;
  return 0;
}

Current time: 2024年04月23日20時02分17秒
Last modified: 2014年12月05日08時38分08秒 (by laycrs)
Tags: Competitive_Programming Codeforces CF250 CF_Div1_B CF_Div2_D
トップページに戻る

Logged in as: unknown user (not login)

ログイン：