95
95
Kategória: |
Feladat
- Megoldás
|
Évfolyam: |
9. |
Kulcsszó: |
Irányított gráfok |
Lektorálás: |
Nem lektorált |
A Ford-Fulkerson-probléma
Feladat
Adott egy irányított gráf minden élén egy számmal. Az egyik csúcs a fúrótorony, a másik az olajfinomító. Ki kell választani olyan élek sorozatát, amivel egy óra alatt a legtöbb olaj jut el a fúrótoronyból az olajfinomítóba, ha az egyes számok azt jelentik, hogy egy óra alatt mennyi olaj tud átfolyni a vezetéken.