apm

Arbore partial de cost minim

* Pentru inca $30%$ din teste $N,M ≤ 5.000$
* Intre oricare doua noduri va exista decat o muchie.

h2. Exemplu

h2. Exemple

table(example). |_. apm.in |_. apm.out |
| 9 14

table(example). |_. apm.in |_. apm.out |_. apm.in|_. apm.out|
|9 14

1 2 10
1 3 -11
2 4 11

8 9 4
9 7 3
6 7 11

| 37
|
 
h3. Explicaţie
 
O solutie este sa se pastreze muchiile intre nodurile $7$ si $3$ cu costul {$4$},{$7$} si $4$ cu costul {$5$},{$7$} si $9$ cu costul {$3$},{$7$} si $6$ cu costul {$11$},{$9$} si $8$ cu costul {$4$},{$3$} si $1$ cu costul {$-11$},{$1$} si $2$ cu costul {$10$},{$2$} si $5$ cu costul {$11$}. Insumand costul $37$. Tin sa mentionez ca solutia nu este unica.
 
table(example). |_. apm.in |_. apm.out |
| 3 3

|37|3 3

1 2 -3
2 3 -4

4 1 -5
| -9
|

3 1 -5|-9|

h3. Explicaţie

h3. Explicatii

Desi ni s-ar parea convenabil sa introducem toate 3 muchiile , daca am face asta ar exista un ciclu si nu ar fi unic drumul dintre noduri.

_Exemplul 1_:O solutie este sa se pastreze muchiile intre nodurile $7$ si $3$ cu costul {$4$},{$7$} si $4$ cu costul {$5$},{$7$} si $9$ cu costul {$3$},{$7$} si $6$ cu costul {$11$},{$9$} si $8$ cu costul {$4$},{$3$} si $1$ cu costul {$-11$},{$1$} si $2$ cu costul {$10$},{$2$} si $5$ cu costul {$11$}. Insumand costul $37$. Solutia nu este neaparat unica.

h2. Indicaţii de rezolvare

_Exemplul 2_:Desi ni s-ar parea convenabil sa introducem toate 3 muchiile , daca am face asta ar exista un ciclu si nu ar fi unic drumul dintre noduri.
h2. Indicaţii de rezolvare

h2. Aplicatii

* "Radiatie":http://infoarena.ro/problema/radiatie

* 'Radiatie':problema/radiatie

* "Prim":http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=20&page=show_problem&problem=1748
== include(page="template/taskfooter" task_id="inversmodular") ==