Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | flux1.in, flux1.out | Sursă | |
| Autor | Autor necunoscut | Adăugată de |  Bogdan-Alexandru Stoica •fireatmyself |
| Timp execuţie pe test | 1.25 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Flux Maxim
Feedback astronomy: Fa enuntul clar, pune clar exact definitiile de la flux, adica pentru fiecare muchie sa se gaseasca F(u,v) <= C(u,v) astfel incat sa se respecte proprietatea aia cu suma fluxurilor care ies egala cu suma care intra, ca in nodul sursa nu intra nici o muchie etc.
Se da un graf orientat cu N noduri si M muchii, fiecare muchie avand o capacitate data. Se cere sa se determine fluxul maxim de la nodul 1 (sursa) la nodul N (destinatie).
Date de intrare
Pe prima linie a fisierul de intrare flux1.in se afla N si M. Urmeaza apoi M linii ce contin 3 numere naturale a, b si c, semnificand faptul ca exista muchie de la nodul a la nodul b avand capacitatea c.
Date de iesire
In fisierul de iesire flux1.out se va scrie fluxul maxim.
Restrictii
- 1 ≤ N ≤ 50
- 1 ≤ N ≤ 1225
- capacitatea fiecarei tevi este un numar natural nenul mai mic sau egal cu 150.
- daca in fisier exista muchia (a, b), cu siguranta nu va exista si muchia (b,a)
- fluxul maxim va fi ≤ 2 000 000 000
Exemplu
| flux1.in | flux1.out |
|---|---|
| 6 12 1 2 6 1 3 3 3 4 5 4 5 4 5 6 4 3 6 100 2 4 3 1 5 4 1 3 6 4 6 5 2 3 5 3 6 4 | 13 |
Indicatii de rezolvare
Problema se rezolva cu ajutorul algoritmului Ford Fulkerson, care are urmatorii pasi.
- se cauta un drum de la sursa (in cazul nostru, nodul 1) la destinatie (in cazul nostru N) cu orice algoritm (bfs, dfs, etc.).
- de pe acest drum se alege muchia de capacitate minima (fie ea i)
- din fiecare muchie a drumului ales se scade capacitatea c~i~ (astfel muchia i va avea capacitatea 0 si poate fi ignorata la urmatorii pasi)
- se creste fluxul cu c~i~ si se repeta de la pasul 1
- algoritmul se repeta de la pasul 1
Feedback Cosmin: pune n mare sa se poata implementa si dinic. Ar trebui ceruta eventual si taietura minima, ca multi nu stiu gasi taietura dupa ce au determinat fluxul maxim.
Probleme asemanatoare
infoarena - Trafic
