hypernet

Hypernet

== include(page="template/taskheader" task_id="hypernet") ==

Poveste si cerinta...

In galaxia noastra exista $N$ planete, numerotate de la $1$ la {$N$}. Fiecare planeta are un anumit numar de locuitori (planeta $i$ are {$Q{~i~}$} locuitori). Guvernul galaxiei doreste sa construiasca o retea compusa din $K$ hipercanale (canale de transport prin hiperspatiu) bidirectionale, fiecare hipercanal conectand $2$ planete distincte. Folosind reteaua construita, fiecare locuitor al fiecarei planete va dori sa viziteze fiecare din celelalte planete. Costul transportului printr-un hipercanal este de $1$ unitate monetare pentru orice locuitor al oricarei planete. Prin urmare, costul vizitarii planetei $j$ de catre un locuitor al planetei $i$ este egal cu numarul minim de hipercanale ce trebuie traversate pentru a ajunge de la planeta i la planeta j (vom numi acest numar {$dist{~i,j~}$}). Costul total al retelei de hipercanale este egal cu suma costurilor platite de fiecare locuitor al fiecarei planete:
!problema/hypernet?hypernet.gif!
 
h2. Cerinta
 
Determinati costul total minim al unei retele constand din $K$ hipercanale.

h2. Date de intrare

...

Prima linie a fisierului de intrare $hypernet.in$ contine $2$ numere intregi, separate printr-un spatiu: $N$ si {$K$}. A {$i$}-a din urmatoarele $N$ linii contine numarul intreg {$Q{~i~}$}, reprezentand numarul de locuitori ai planetei {$i$}.

h2. Date de iesire

...

In fisierul de iesire $hypernet.out$ afisati costul total minim al unei retele de hipercanale avand proprietatile specificate.

h2. Restrictii

* $... ≤ ... ≤ ...$

* {$1 ≤ N ≤ 50.000$}
* {$N-1 ≤ K ≤ N*(N-1)/2$}
* {$1 ≤ Q{~i~} ≤ 1.000.000$}

h2. Exemplu
table(example). |_. hypernet.in |_. hypernet.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 4 3
4
3
1
2
| 42
|
| 4 5
10
9
8
7
| 117

|

h3. Explicatie
 
...

== include(page="template/taskfooter" task_id="hypernet") ==

2041