== include(page="template/taskheader" task_id="orient") ==
Se da un graf orientat cu $N$ noduri si $M$ muchii. Prin a reorienta o muchie se intelege ca daca in graf exista muchia $(a, b)$ (adica muchie de la nodul $a$ spre nodul $b$), o poate sterge si plasa in locul ei muchia $(b, a)$ (de la nodul $b$ spre nodul $a$).
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~ $.
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. Cerinta
h2. Cerinţă
Reorientati un numar minim de muchii din graful dat, astfel incat acesta sa contina cel putin un ciclu. Se garanteaza ca exista un numar de muchii (eventual $0$) ce pot fi reorientate astfel incat sa se formeze ciclu.
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$ 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 doua numere naturale distincte $a$ si $b$, separate prin cate un spatiu, cu proprietatea ca in graf exista o muchie orientata de la nodul $a$ spre nodul $b$.
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$ se va gasi pe prima linie un singur numar natural, reprezentand numarul minim de muchii care trebuie reorientate pentru a forma un ciclu.
Î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 ≤ 2000$
* $2 ≤ M ≤ 5000$
* $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.
table(example). |_. orient.in |_. orient.out |
| 5 5
1 2
3 2
3 4
4 1
4 5
| 1
1 2 2
3 2 10
3 4 3
4 1 1
4 5 4
| 6
|
h3. Explicaţie
Putem reorienta muchia $(3 2)$, obtinand astfel ciclul: $(1, 2, 3, 4)$.
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") ==
