Inverseaza reviziile

Diferente pentru problema/lazy intre reviziile #7 si #1

Diferente intre titluri:

Lazy

lazy

Diferente intre continut:

== include(page="template/taskheader" task_id="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: $C1{~i~}$ – efortul care trebuie depus pentru a construi drumul si $C2{~i~}: C1{~i~} * C2{~i~}$ 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!

Poveste şi cerinţă...

h2. 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: $a{~i~}$ si $b{~i~}$ reprezentând oraşele pe care drumul $i$ le leagă, $C1{~i~}$ şi $C2{~i~}$.

Fişierul de intrare $lazy.in$ ...

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

În fişierul de ieşire $lazy.out$ ...

h2. Restricţii

* $1 ≤ N,M ≤ 200.000$
* $1 ≤ a{~i~}, b{~i~} ≤ N$
* $1 ≤ C1{~i~} < 10^17^$
* $-10^17^ < C2{~i~} < 10^17^$
* dacă există mai multe soluţii se acceptă oricare dintre ele

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. lazy.in |_. lazy.out |

| 3 3
1 2 1 7
2 3 3 2
1 3 2 3
| 1
3

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="lazy") ==

Nu exista diferente intre securitate.

Diferente intre topic forum:

5343