== include(page="template/taskheader" task_id="aparare") ==
Poveste şi cerinţă...
Se consideră $N$ puncte strategice aflate în administrarea Ministerului Apărării (MA). Pentru $M$ perechi de puncte se cunoaşte costul de conectare directă, în caz că se doreşte realizarea conectării directe a punctelor din acea pereche.
# Să se aleagă un număr de perechi de noduri a căror conectare va fi efectiv implementată, dintre cele $M$, astfel încât, la finalul lucrării, între oricare dintre cele $N$ noduri să existe comunicare directă sau indirectă prin conexiunile realizate şi, în plus, costul total al lucrărilor să fie minim (se garantează că acest lucru este întotdeauna posibil).
# Comandamentul Trupelor de Uscat (CTU) va prelua $5$ dintre cele $N$ noduri, astfel încât, conform strategiei de conectare stabilită la (1), comunicarea între oricare dintre cele $5$ noduri să se realizeze fie direct, fie folosind numai puncte preluate de CTU. Ştiind că toate costurile de conectare (stabilite la (1)) dintre cele $5$ puncte vor fi plătite de CTU, să se aleagă convenabil cele $5$ noduri astfel încât costul conectărilor (de la (1)) rămase în responsabilitatea MA să fie minim.
h2. Date de intrare
Fişierul de intrare $aparare.in$ ...
Fişierul de intrare $aparare.in$ conţine pe prima linie valoarea lui $N$, numărul de puncte strategice, urmată de valoarea lui $M$, numărul de perechi de puncte strategice pentru care se ştie costul de conectare directă. Pe fiecare din următoarele $M$ linii, se găsesc câte $3$ numere: $i$, $j$ şi $c$ ({$1 ≤ i < j ≤ N$}) separate printr-un spaţiu, cu semnificaţia că pentru a conecta direct punctele $x$ şi $y$ trebuie plătit costul $c$.
h2. Date de ieşire
În fişierul de ieşire $aparare.out$ ...
În fişierul de ieşire $aparare.out$ va conţine pe prima linie un număr natural reprezentând costul total de conectare de la (1), iar pe linia a doua costul total rămas după preluarea de către CTU a celor $5$ puncte strategice alese convenabil.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $5 ≤ N ≤ 100 000$
* $2 * N ≤ M ≤ N * (N - 1) / 2$
* $M ≤ 500 000$
* Costurile de conectare sunt numere naturale strict pozitive, *distincte două câte două*, de cel mult $9$ cifre fiecare.
* Costul de conectare de la nodul $i$ la nodul $j$ este acelaşi cu costul de conectare de la nodul $j$ la nodul $i$, oricare ar fi $1 ≤ i, j ≤ N$.
* Se acordă $40%$ din punctaj pentru prima valoare corectă şi $100%$ din punctaj pentru ambele valori corecte. *Pentru a primi punctaj parţial trebuie să afişaţi ambele valori cerute.*
h2. Exemplu
table(example). |_. aparare.in |_. aparare.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 6 15
1 2 5
1 3 3
2 3 11
1 4 7
2 4 2
3 4 1
1 5 6
2 5 10
3 5 4
4 5 14
1 6 9
2 6 16
3 6 8
4 6 20
5 6 18
| 18
2
|
h3. Explicaţie
...
Se conectează perechile: $1 - 3$, $3 - 4$, $3 - 5$, $3 - 6$, $2 - 4$ obţinându-se costul total minim $18$.
Se preiau de către CTU punctele $1$, $3$, $4$, $5$ şi $6$, cu costurile aferente de conectare, MA plătind doar conectarea $2 - 4$ cu costul $2$.
== include(page="template/taskfooter" task_id="aparare") ==
