[ cassey @ 19.06.2005. 01:22 ] @
Da evo jos jednog zadatka za koji nemam bas nekih sjajnih ideja (barem ne lepo uoblicenih)...

Data je mreza cevi sa cvorova (ne znam kako se ovo tacno prevodi na srpskom) i za svaku cev je dat njen kapacitet. Takodje, odredjene cevi moraju zadovoljavati uslov da pri pustanju vode kros izvor one budu u potpunosti napunjene vodom, dok ostale mogu ali ne moraju. Treba napisati program koji nalazi minimalnu kolicinu vode potrebu za putanje u izvor da bi odredjene cevi bili u potpunosti pune, i za navedenu kolicinu vode stampati koliki je protok kroz svaku cev u mrezi.

InPut:
Prvi red: = broj cvorova i broj grana
2..M+1 red: = cvorovi i su spojeni cevlju kapaciteta . Ukoliko je tada cev mora biti u potpunosti napunjena, a ne mora
i

OutPut:
Prvi red: = minimalni protok koji zadovoljava gore navedene uslove
Drugi red: niz = kolika kolicina vode protice kroz i-tu cev
Ukoliko takav protok ne postoji stampati sta god vec...


Primer [1]:

4 4
1 2 2 0
2 4 1 1
1 3 2 1
3 4 3 0

3
1 1 2 2

Primer [2]:

4 4
1 2 1 0
2 4 2 1
1 3 3 1
3 4 2 0

Impossible

(Time limit per test: 2 sec. Memory limit per test: 1024 KB)... smrc...
[ Mihajlo Cvetanović @ 20.06.2005. 09:00 ] @
Recimo da se cevi kapaciteta 2 i 3 slivaju u cev kapaciteta 4. Koja je količina vode koja protiče kroz prve dve cevi?
[ cassey @ 20.06.2005. 11:10 ] @
Ne razumem pitanje?! Znaci ovde ti vaze isti uslovi kao i kod obicnog Flow-a, znaci ona (nazovi) Kirkohova pravila: kolika kolicina ucdje u neki cvor tolika mora da i izadje...
[ Mihajlo Cvetanović @ 20.06.2005. 16:22 ] @
Primer

1 2 2 0
2 4 2 0
1 3 3 0
3 4 3 0
4 5 4 0

Kroz putanju 1-2-4 kapacitet je 2, kroz 1-3-4 kapacitet je 3. U zbiru to je 5, ali kroz cev 4-5 kapacitet je 4, pa ne može svih 5 (litara u sekundi) da prođe. Kako se onda raspodeljuje tih maksimalnih 4 (litra u sekundi) po putanjama 1-2-4 i 1-3-4?
[ cassey @ 20.06.2005. 17:40 ] @
Ma to ti je nebitno. Za mrezu koju si naveo (ne vezano za zadatak) protok je 4. E sad moze i da kroz 1-2-4 tece 1 litar a kroz 1-3-4 dva pa da se u 4-5 nadju 4 litra ili moze 1-2-3 da tece 2, kao i kroz 1-3-4. Ti Flow definises kao maksimalnu kolicinu vode koja moze da tece a to je u ovom slucaju 4 a ne 5. E npr. ako je ovde uslov da 1-2 i 3-4 budu skroz pune (za zadatak) onda streba stampati da nema resenje. Nadam se da znas sta je Flow?!
[ Mihajlo Cvetanović @ 21.06.2005. 12:22 ] @
Kako nebitno, kad se to traži kao odgovor? Ne znam šta je tačno ulaz a šta izlaz Flow algoritma, spominje se u jednoj TOP temi, ali nisam se udubljivao.
[ cassey @ 21.06.2005. 13:21 ] @
Pa niko nije rekao da postoji jedinstveno resenje. Ti treba da stampas samo jedno... Tebi je samo bitno da vaze ti uslovi za protok i da su te odredjene cevi skroz pune vode... Mada ako neznas Flow, ne verujem da ces bas uspeti da resis ovaj zadatak (mozda je gresim, ali sve moje ideje se svode na neku modifikaciju polaznog grafa pa zatim pustanje obicnog Flow-a)...