Fişierul intrare/ieşire:orient.in, orient.outSursăInfoarena Monthly 2012, Runda 6
AutorVlad IonescuAdăugată decezar305Mr. Noname cezar305
Timp execuţie pe test1.5 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Orient

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 (v1, v2, ..., vk), cu proprietatea ca pentru orice i ≤ k-1 in graf exista muchie de la nodul vi spre nodul vi+1, si de asemenea exista muchie de la nodul vk spre nodul v1.

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.

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 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.

Date de ieşire

Î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.

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.

Exemplu

orient.inorient.out
5 5
1 2 2
3 2 10
3 4 3
4 1 1
4 5 4
6

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content