Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

[Zadatak] Flow construction

[es] :: Art of Programming :: [Zadatak] Flow construction

[ Pregleda: 3810 | Odgovora: 6 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

cassey
Andreja Ilic
Nis

Član broj: 57788
Poruke: 188
212.200.11.*



+1 Profil

icon [Zadatak] Flow construction 19.06.2005. u 01:22 - pre 200 meseci
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...
Math is like love. A simple idea but it can get complicated.
 
Odgovor na temu

Mihajlo Cvetanović
Beograd

Moderator
Član broj: 37636
Poruke: 1236



+93 Profil

icon Re: [Zadatak] Flow construction 20.06.2005. u 09:00 - pre 200 meseci
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?
 
Odgovor na temu

cassey
Andreja Ilic
Nis

Član broj: 57788
Poruke: 188
212.200.11.*



+1 Profil

icon Re: [Zadatak] Flow construction 20.06.2005. u 11:10 - pre 200 meseci
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...
Math is like love. A simple idea but it can get complicated.
 
Odgovor na temu

Mihajlo Cvetanović
Beograd

Moderator
Član broj: 37636
Poruke: 1236



+93 Profil

icon Re: [Zadatak] Flow construction 20.06.2005. u 16:22 - pre 200 meseci
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?
 
Odgovor na temu

cassey
Andreja Ilic
Nis

Član broj: 57788
Poruke: 188
212.200.11.*



+1 Profil

icon Re: [Zadatak] Flow construction 20.06.2005. u 17:40 - pre 200 meseci
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?!
Math is like love. A simple idea but it can get complicated.
 
Odgovor na temu

Mihajlo Cvetanović
Beograd

Moderator
Član broj: 37636
Poruke: 1236



+93 Profil

icon Re: [Zadatak] Flow construction 21.06.2005. u 12:22 - pre 200 meseci
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.
 
Odgovor na temu

cassey
Andreja Ilic
Nis

Član broj: 57788
Poruke: 188
212.200.11.*



+1 Profil

icon Re: [Zadatak] Flow construction 21.06.2005. u 13:21 - pre 200 meseci
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)...
Math is like love. A simple idea but it can get complicated.
 
Odgovor na temu

[es] :: Art of Programming :: [Zadatak] Flow construction

[ Pregleda: 3810 | Odgovora: 6 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.