Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | fmcm.in, fmcm.out | Sursă | Arhiva educationala |
| Autor | Arhiva Educationala | Adăugată de |  Paul-Dan Baltescu •pauldb |
| Timp execuţie pe test | 0.3 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
Flux maxim de cost minim
Se da o retea de transport sub forma unui graf orientat cu N noduri si M arce. Fiecare arc are asociate o capacitate si un cost pentru fiecare unitate de flux. In graf se afla 2 noduri distincte, notate cu S si D, ce reprezinta sursa si, respectiv, destinatia retelei. Sa se determine costul minim pentru a se transmite o cantitate maxima de flux de la sursa la destinatie.
Date de intrare
Pe prima linie a fisierului de intrare fmcm.in, se afla 4 numere intregi N M S D cu semnificatia din enunt. Pe urmatoarele M linii se afla cate 4 numere x y c z, fiecare astfel de grup reprezentand un arc de la x la y cu capacitatea c si costul z.
Date de ieşire
În fisierul de iesire fmcm.out se va afla un numar intreg reprezentand valoarea costului minim pentru a transmite o cantitate maxima de flux de la sursa la destinatie.
Restricţii
- 1 ≤ N ≤ 350
- 1 ≤ M ≤ 12 500
- 1 ≤ c ≤ 10 000
- 1 ≤ z ≤ 100
- Se garanteaza ca nu exista nici un arc care sa intre in S si nici un arc care sa iasa din D.
- Pentru simplitate, vom considera ca daca exista muchie de la x la y, atunci ea e unica si nu va exista muchie de la y la x.
Exemplu
| fmcm.in | fmcm.out |
|---|---|
| 5 7 1 5 1 2 9 5 1 3 2 4 2 3 3 3 2 4 2 1 3 4 2 2 3 5 10 7 4 5 3 4 | 86 |
Explicaţie
...
