The Child and Zoo

Enes Öncü'ye teşekkür ederiz.

Soru Metni

Size n düğüm ve m kenar içeren bir çizge veriliyor. Her düğümün bir değeri vardır.

İki düğüm arasındaki bir yolun değeri bu yol üzerindeki tüm düğümlerin değerlerinin en küçüğüne eşit oluyor.

f( p,q ) ise p den q ya giden yollardan değeri en büyük olan yolun değeri olarak tanımlanıyor.

 

Sizden istenen değerini bulmanız.

Yani tüm farklı p,q ikilileri için f(p,q) ların aritmetik ortalaması isteniyor.

İlk satırda n ve m (2 ≤ n ≤ 100000; 0 ≤ m ≤ 100000).

İkinci satırda düğümlerin değerleri a1, a2, ..., an (0 ≤ ai ≤ 100000).

Sonraki n satırda m adet kenar xi ve yi (1 ≤ xi, yi ≤ n; xi ≠ yi).

Örnek Girdiler

Girdi

4 3

10 20 30 40

1 3

2 3

4 3

Çıktı

16.666667

Girdi

3 3

10 20 30

1 2

2 3

3 1

Çıktı

13.333333

Girdi

7 8

40 20 10 30 20 50 40

1 2

2 3

3 4

4 5

5 6

6 7

1 4

5 7

Çıktı

18.571429

Not:

İlk örnek girdiyi düşünelim. 12 tane durum var:

•      p = 1, q = 3, f(p, q) = 10.

•      p = 2, q = 3, f(p, q) = 20.

•      p = 4, q = 3, f(p, q) = 30.

•      p = 1, q = 2, f(p, q) = 10.

•      p = 2, q = 4, f(p, q) = 20.

•      p = 4, q = 1, f(p, q) = 10.

Diğer 6 durum bunlara simetrik. Ortalamaları .

İkinci örnek girdiyi düşünelim. 6 tane durum var:

•      p = 1, q = 2, f(p, q) = 10.

•      p = 2, q = 3, f(p, q) = 20.

•      p = 1, q = 3, f(p, q) = 10.

Diğer 3 durum bunlara simetrik. Ortalamaları.

Linkler:http://codeforces.com/contest/438/problem/B

Çözüm Metni:

Öncelikle kenarlara belli bir değer verebiliriz. Eğer p düğümünden q düğümüne bir kenar varsa bu kenarı kullanırken hem p hem q düğümünden geçeceğiz. O zaman bu kenarın değerine min( a[p],a[q] ) diyebiliriz.

Elimizdeki kenarları değerlerine göre büyükten küçüğe sıralıyoruz. Ve elimize kenarları sıra sıra alıp bu kenarın daha önceden birbirine yol gelmeyen hangi düğümleri bağladığına bakıyoruz.

Mesela bu kenarın daha önce bağlı olmayıp şimdi bağladığı iki çizge grubundaki eleman sayıları s1 ve s2 olsun ve ekleyeceğimiz kenarın değeri b olsun. Bu s1 ve s2 elemanlı gruplardan birbirlerine b değerinde yollar olduğu bariz. Çünkü bundan önce gelen kenarların değerleri hep b den büyüktü ve bu iki grup arasında yol oluşuyorsa bu yolun maliyeti b olabilir. Peki niye daha büyük bir şey olamaz çünkü daha önce bu çizge parçalarından birbirine yol yoktu. O zaman s1*s2 tane p,q ikilisinin f(p,q) değeri b olur. Bu da toplamımızı s1*s2*b artırır. Eğer Simetriklerini de sayarsak 2*s1*s2*b artırır.

Sonuç olarak toplamımız ans ise ortalamamız ans/( n*(n-1) ) olur.

Algoritma:

Ayrık küme işlemlerini kullanacağız. Her kümede kaç tane eleman olduğunu kümenin atasında tutacağız. Yeni bir kenar geldiğinde eğer bu yolun birleştirdiği iki parça daha önceden birleştiyse bu kenar hiçbir f( p,q ) ' u en büyük yapamaz. Bu kenarı atlarız. Aksi taktirde cevabı yukarıda anlatıldığı şekilde güncelleriz ve bu iki ayrık kümeyi birleştiririz ve yeni kümenin eleman sayısı bu iki kümenin eleman sayısının toplamına eşit olur.

Çözüm Kodu:

#include <algorithm>

#include <string>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <cassert>

#include <queue>

#include <cstdlib>

#include <set>

#include <map>

#include <stack>

#include <cmath>

#include <ctime>

#define st          first

#define nd          second

#define mp          make_pair

#define pb          push_back

#define lli  long long int

#define all( gg )          gg.begin(),gg.end()

#define foreach( gg,itit )       for( typeof(gg.begin()) itit=gg.begin();itit!=gg.end();itit++ )

#define FP( ii,aa,bb )           for( lli  ii=aa;ii<=bb;ii++ )

#define FM( ii,aa,bb )           for( lli  ii=aa;ii>=bb;ii-- )

#define maxn        200000

using namespace std;

lli n,m,res,arr[maxn],ata[maxn],size[maxn];

pair< lli,pair<lli,lli> >        w[maxn];

int atabul( int nod ){

             return nod==ata[nod] ? nod : ata[nod] = atabul( ata[nod] );

}

void birlestir( int x,int y,lli c ){

             int a,b;

             a = atabul( x );

             b = atabul( y );

             res += size[a]*size[b]*c;

             size[a] += size[b];

             ata[b] = ata[a];

}

int main(){

             ios_base::sync_with_stdio( false );

       

             cin >> n >> m;

       

             FP( i,1,n )     cin >> arr[i],ata[i]=i,size[i]=1;

       

             FP( i,1,m ){

                    cin >> w[i].nd.st >> w[i].nd.nd;

                    w[i].st = min( arr[w[i].nd.st],arr[w[i].nd.nd] );

             }

       

             sort( w+1,w+m+1 );

       

             FM( i,m,1 ){

                    lli x,y,c;

                    x = w[i].nd.st;

                    y = w[i].nd.nd;

                    c = w[i].st;

                    if( atabul(x)!=atabul(y) )      birlestir( x,y,c );

             }

       

             cout << 2.0*res/(n*(n-1)) << endl;

}