Fişierul intrare/ieşire:circulatie.in, circulatie.outSursăAlgoritmiada 2013, Runda 2
AutorAdrian VladuAdăugată deGheorgheMihaiMihai Gheorghe GheorgheMihai
Timp execuţie pe test1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Circulatie

Se numeste graf bipartit un graf ale carui noduri pot fi partitionate in 2 multimi astfel incat orice muchie are capetele in multimi distincte. In aceasta problema vom considera ca graful este deja partitionat, ambele multimi avand noduri numerotate de la 1 la N. Fie un asemenea graf bipartit cu 2 * N noduri unde fiecare nod are gradul 3(este conectat cu alte 3 noduri). Marele Intelept iti da urmatoarea sarcina. Tu trebuie sa orientezi muchiile grafului si sa le atribui costuri naturale cuprinse in intervalul [1, 3] astfel incat pentru orice nod, suma costurilor muchiilor care intra in nod sa fie egala cu suma costurilor muchiilor care ies din nod.

Orice solutie este acceptata.

Date de intrare

Fişierul de intrare circulatie.in va contine pe prima linie numarul natural N reprezentand numarul de noduri din graf. Pe urmatoarele 3 * N linii vor fi cate 2 numere naturale a si b reprezentand faptul ca exista muchie de la nodul a din prima multime la nodul b din a doua multime.

Date de ieşire

Fişierul de ieşire circulatie.out va contine 3 * N linii de forma a b c, semnificand faptul ca muchia a - b ( a din prima multime si b din a doua multime) va avea costul c. Daca orientarea muchiei este a -> b, c va fi pozitiv. Altfel, c va fi negativ.

Restricţii

  • 3 ≤ N ≤ 105

Exemplu

circulatie.incirculatie.out
3
1 1
1 2
2 3
3 1
2 2
1 3
3 2
3 3
2 1
1 2 -2
2 3 -3
2 2 1
3 2 1
1 1 1
1 3 1
2 1 2
3 1 -3
3 3 2
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?