Fişierul intrare/ieşire:lazy.in, lazy.outSursăRMMS 2011 - Ziua 1
AutorAndrei ParvuAdăugată deandrei.12Andrei Parvu andrei.12
Timp execuţie pe test0.6 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Lazy

Toată lumea ştie că muncitorii din România sunt foarte leneşi. Unul dintre aceşti muncitori este Dorel, care lucrează pentru o companie care construieşte drumuri prin ţară. Ieri el a primit o nouă cerinţă: i s-au specificat N oraşe din România (numerotate de la 1 la N), M străzi bidirecţionale (numerotate de la 1 la M) care nu sunt încă construite, fiecare legând exact două oraşe; dintre aceste drumuri el trebuie să selecteze şi să construiască N-1 astfel încât toate oraşele să devină conectate. Din păcate aceasta problemă nu este foarte simplă pentru Dorel: fiecare drum i are asociat două costuri: C1i – efortul care trebuie depus pentru a construi drumul si C2i: C1i * C2i fiind profitul luat de pe urma construirii drumului. Bineînţeles Dorel vrea să muncească cât mai puţin posibil aşa că cel mai important lucru este ca suma costurilor drumurilor construite să fie minimă; dacă există mai multe moduri de a construi drumuri astfel încât costul total să fie minim, Dorel dorşte ca profitul total (suma profiturilor pentru fiecare drum) să fie maxim.
Voi trebuie să rezolvaţi problema lui Dorel!

Date de intrare

Pe prima linie a fişierului lazy.in se află două numere N şi M, numărul de oraşe, respectiv numărul de drumuri. Urmează M linii, a i-a din aceste linii are 4 numere naturale: ai si bi reprezentând oraşele pe care drumul i le leagă, C1i şi C2i.

Date de ieşire

Fişierul de ieşire lazy.out trebuie să conţină N-1 numere reprezentând indecşii (conform fişierului de intrare) drumurilor care trebuie alese de Dorel.

Restricţii

  • 1 ≤ N,M ≤ 200.000
  • 1 ≤ ai, bi ≤ N
  • 1 ≤ C1i < 1017
  • -1017 < C2i < 1017
  • dacă există mai multe soluţii se acceptă oricare dintre ele

Exemplu

lazy.inlazy.out
3 3
1 2 1 7
2 3 3 2
1 3 2 3
1
3
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content