== include(page="template/taskheader" task_id="orient") ==
Poveste şi cerinţă...
Se da un graf orientat cu $N$ noduri si $M$ muchii. Fiecarei muchii i se asociaza un cost, numit cost de reorientare.
Prin a reorienta o muchie se intelege ca daca in graf exista muchia $(a, b)$ (adica muchie de la nodul $a$ spre nodul $b$), muchia se sterge si se plaseaza in locul ei muchia $(b, a)$ (de la nodul $b$ spre nodul $a$), operatia avand costul egal cu costul de reorientare al muchiei respective.
De asemenea, prin notiunea de ciclu intr-un graf se intelege o secventa de noduri $(v{~1~}, v{~2~}, ..., v{~k~})$, cu proprietatea ca pentru orice $i ≤ k-1$ in graf exista muchie de la nodul $v{~i~}$ spre nodul $v{~i+1~}$, si de asemenea exista muchie de la nodul $v{~k~}$ spre nodul $v{~1~}$.
h2. Cerinţă
Reorientati un numar de muchii din graful dat, astfel incat acesta sa contina cel putin un ciclu, iar costul tuturor operatiilor sa fie minim. Se garanteaza ca exista un numar de muchii (eventual $0$) ce pot fi reorientate astfel incat sa se formeze ciclu.
h2. Date de intrare
Fişierul de intrare $orient.in$ ...
Fişierul de intrare $orient.in$ contine pe prima linie doua numere naturale $N$ si $M$, separate prin cate un spatiu, reprezentand numarul de noduri, respectiv numarul de muchii ale grafului. Urmatoarele $M$ linii contin fiecare cate trei numere naturale $a$, $b$ si $c$, cu $a$ diferit de $b$, separate prin cate un spatiu, cu proprietatea ca in graf exista o muchie orientata de la nodul $a$ spre nodul $b$, avand costul de reorientare egal cu $c$.
h2. Date de ieşire
În fişierul de ieşire $orient.out$ ...
În fişierul de ieşire $orient.out$ se va gasi pe prima linie un singur numar natural, reprezentand costul minim obtinut prin reorientarea convenabila a unor muchii, astfel incat graful sa contina cel putin un ciclu.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $2 ≤ N ≤ 1000$
* $2 ≤ M ≤ 3000$
* $1 ≤ costul unei muchii ≤ 5000$
* Intre doua noduri $a$ si $b$ ale grafului exista cel mult o muchie (indiferent de orientarea acesteia).
* Daca graful contine deja un ciclu, raspunsul problemei va fi $0$.
* Un ciclu nu trebuie neaparat sa contina toate cele $N$ noduri ale grafului. Un ciclu poate contine minim $2$ noduri.
h2. Exemplu
table(example). |_. orient.in |_. orient.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5 5
1 2 2
3 2 10
3 4 3
4 1 1
4 5 4
| 6
|
h3. Explicaţie
...
Putem reorienta muchiile $(4, 1), (3, 4), (1, 2)$, obtinand un cost egal cu $1 + 3 + 2 = 6$, si ciclul $(1, 2, 3, 4)$. O alta varianta ar fi fost reorientarea muchiei $(3, 2)$, insa am fi obtinut un cost mai mare: $10$.
== include(page="template/taskfooter" task_id="orient") ==
