| Prethodna tema :: Sljedeća tema |
| Autor/ica |
Poruka |
Gost
|
|
| [Vrh] |
|
ZELENIZUBNAPLANETIDO
SADE
Forumaš(ica)
Pridružen/a: 04. 03. 2004. (19:56:15)
Postovi: (54F)16
Lokacija: hm?
|
 Postano: 23:23 ned, 21. 8. 2005 Naslov: |
    |
|
|
1. korak: pogledas vrhove koji se "vide" iz izvora [i]s[/i] (iliti [i]skeniras izvor[/i]). Uoceni cvor kojem je dopusteni kapacitet veci od toka (nazovimo ga [i]i[/i]) labeliramo sa dvije informacije: prethodni cvor (s) i dopustena promjena toka [i]d_i[/i]. Simbolicki:
ako: [latex]C_{si}-F_{si}>0[/latex], cvoru [i]i[/i] dodijelimo labelu [latex](s, d_i)[/latex] gdje je [latex]d_i=C_{si}-F_{si}[/latex]
2. korak: skeniramo iz [i]i[/i]. Eventualni cvor [i]j[/i] za koji vrijedi [latex]C_{ij}-F_{ij}>0[/latex] postavimo labelu (i, d_j) gdje je [latex]d_j=\min\{d_i, C_{ij}-F_{ij}\}[/latex].
3. korak: ako smo u zadnjem koraku labelirali ponor, moguce je povecanje toka po putu kojeg smo upravo markirali (zato zapisujemo prethodne cvorove) i to u vrijednosti zapisanoj u labeli pridruzenoj ponoru i pocnes od pocetka, od koraka 1.
ako su svi skenirani cvorovi iz prethodnog koraka vec oznaceni labelama - ne postoji put povecanja toka, u suprotnom nastavi sa 2. korakom.
1. korak: pogledas vrhove koji se "vide" iz izvora s (iliti skeniras izvor). Uoceni cvor kojem je dopusteni kapacitet veci od toka (nazovimo ga i) labeliramo sa dvije informacije: prethodni cvor (s) i dopustena promjena toka d_i. Simbolicki:
ako:  , cvoru i dodijelimo labelu  gdje je 
2. korak: skeniramo iz i. Eventualni cvor j za koji vrijedi  postavimo labelu (i, d_j) gdje je  .
3. korak: ako smo u zadnjem koraku labelirali ponor, moguce je povecanje toka po putu kojeg smo upravo markirali (zato zapisujemo prethodne cvorove) i to u vrijednosti zapisanoj u labeli pridruzenoj ponoru i pocnes od pocetka, od koraka 1.
ako su svi skenirani cvorovi iz prethodnog koraka vec oznaceni labelama - ne postoji put povecanja toka, u suprotnom nastavi sa 2. korakom.
_________________ 
Pupoljak nije negiran. Rekao sam to i ponovit cu to jos jedanput. Pupoljak NIJE negirAn.
MADD
(Mothers Against Dirty Dialectics)
Based on a true story. NOT.
Ko ih sljivi, mi sviramo punk  |
|
| [Vrh] |
|
Nesi
Inventar Foruma
(Moderator)
Pridružen/a: 14. 10. 2002. (14:27:35)
Postovi: (E68)16
Spol: 
Sarma: -
|
| Postano: 23:39 ned, 21. 8. 2005 Naslov: |
|
|
|
ok, ajmo probat :wink:
sastoji se od 2 dijela, prvo cu ugrubo da uhvatis ideju:
[b]početak[/b] = tok sa vrijednostima 0 (ili neke druge)
[b]dio A[/b][list][*]traži put povećanja toka
[*]ako takav put ne postoji, tada je tok maximalan, tj. algoritam zavr[ava
[*]ako takav put postoji :arrow: vrši se dio B
[/list:u]
[b]dio B[/b][list][*]povećava zadani tok duž puta povećanja toka ([latex]f \rightarrow f'[/latex])
[*]na novi tok primjenimo dio A
[/list:u]
idemo sad lijepo raspisati
moj savjet je da si zemes neki tok (ima toga solidno medju zadacima iz MM) i prvo oznacis sve vrhove - klasicno je da im das slova :-) redom.... i onda primjenjujes step-by-step iduce stvari...
[b]dio A:[/b][list][b]korak 1.[/b][*]odaberi proizvoljan luk [latex]l[/latex] iz izvora i za koji je [latex]f(l) < c(l) (l=(i,v_1))[/latex]
[*]ako takav vrh [latex]v_1[/latex] ne postoji, tok je max, tj. algoritam završava
[*]u suprotnom, vrhu [latex]v_1[/latex] pridruži oznaku [latex](i,a_1)[/latex] gdje je [latex]a_1=c(l)-f(l)[/latex]
[b]korak 2.[/b][*]pretpostavimo da smo odabrali vrhove [latex]i, v_1, \dots , v_k[/latex]
[*]vrh [latex]v_{k+1}[/latex] biramo tako da (slučajevi)
a) za luk [latex]l=(v_k,v_{k+1})[/latex] vrijedi [latex]f(l) > c(l)[/latex]
odnosno
b) za luk [latex]l=(v_{k+1},v_k)[/latex] vrijedi [latex]f(l)>0[/latex]
[*]vrhu [latex]v_{k+1}[/latex] pridružimo oznaku, u slučaju
a) [latex](v_k,a_{k+1})[/latex] tako da [latex]a_{k+1}=min\{c(l)-f(l),a_k\}[/latex]
b) [latex](v_k^-,a_{k+1})[/latex] tako da je [latex]a_{k+1}=min\{f(l),a_k\}[/latex]
[*]ako takav vrh [latex]v_{k+1}[/latex] ne postoji, vraćamo se nazad koristeći oznake, dok ne dođemo do vrha [latex]v_j (j>k)[/latex] iz kojeg možemo uočiti neoznačeni vrh sa svojstvom a) ili b)
- taj vrh uzmemo za [latex]v_{j+1}[/latex]
- ako takav [latex]v_j[/latex] ne postoji, tok je maximalan
[b]korak 3.[/b][*]korak 2. ponavljaj dok ne dođeš do ponora [latex]p[/latex] i tada prijeđi na dio B
[/list:u]
[b]dio B:[/b][list][b]korak 1.[/b][*]pogledaj oznaku za [latex]p[/latex], neka je ona [latex](v_m,a)[/latex]
[*]povećaj tok na luku [latex](v_m,p)[/latex] za [latex]a[/latex]
[b]korak 2.[/b][*]pretpostavimo da smo došli do vrha [latex]v_k[/latex]
[*][latex]v_k[/latex] nosi oznaku:
a) [latex](v_{k-1},a_k)[/latex]
ili
b) [latex](v_{k-1}^-,a_k)[/latex]
[*]u slučaju
a) povećamo tok na luku [latex](v_{k-1},v_k)[/latex] za [latex]a[/latex]
b) smanjimo tok na luku [latex](v_k,v_{k-1})[/latex] za [latex]a[/latex]
[b]korak 3.[/b][*]korak 2. ponavljamo sve dok ne dođemo do izvora [latex]i[/latex]
[*]izbrišemo sve oznake i idemo na dio A
[/list:u]
[b]čvorovi moraju biti kirchoffovi[/b] :!:
to je vise-manje to, i prepisano sa mog salabahtera...
a sad, idemo na registraciju :g:
ok, ajmo probat
sastoji se od 2 dijela, prvo cu ugrubo da uhvatis ideju:
početak = tok sa vrijednostima 0 (ili neke druge)
dio A- traži put povećanja toka
- ako takav put ne postoji, tada je tok maximalan, tj. algoritam zavr[ava
- ako takav put postoji
 vrši se dio B
dio B- povećava zadani tok duž puta povećanja toka (
 )
- na novi tok primjenimo dio A
idemo sad lijepo raspisati
moj savjet je da si zemes neki tok (ima toga solidno medju zadacima iz MM) i prvo oznacis sve vrhove - klasicno je da im das slova  redom.... i onda primjenjujes step-by-step iduce stvari...
dio A:korak 1.- odaberi proizvoljan luk
 iz izvora i za koji je 
- ako takav vrh
 ne postoji, tok je max, tj. algoritam završava
- u suprotnom, vrhu pridruži oznaku
 gdje je 
korak 2. - pretpostavimo da smo odabrali vrhove
- vrh
 biramo tako da (slučajevi)
a) za luk  vrijedi 
odnosno
b) za luk  vrijedi 
- vrhu pridružimo oznaku, u slučaju
a)  tako da 
b)  tako da je 
- ako takav vrh ne postoji, vraćamo se nazad koristeći oznake, dok ne dođemo do vrha
 iz kojeg možemo uočiti neoznačeni vrh sa svojstvom a) ili b)
- taj vrh uzmemo za 
- ako takav  ne postoji, tok je maximalan
korak 3. - korak 2. ponavljaj dok ne dođeš do ponora
 i tada prijeđi na dio B
dio B:korak 1.- pogledaj oznaku za , neka je ona
- povećaj tok na luku
 za 
korak 2. - pretpostavimo da smo došli do vrha
- nosi oznaku:
a) 
ili
b) 
- u slučaju
a) povećamo tok na luku  za
b) smanjimo tok na luku  za
korak 3. - korak 2. ponavljamo sve dok ne dođemo do izvora
- izbrišemo sve oznake i idemo na dio A
čvorovi moraju biti kirchoffovi 
to je vise-manje to, i prepisano sa mog salabahtera...
a sad, idemo na registraciju 
_________________
It's not who you love. It's how.
|
|
| [Vrh] |
|
Nesi
Inventar Foruma
(Moderator)
Pridružen/a: 14. 10. 2002. (14:27:35)
Postovi: (E68)16
Spol:
Sarma: -
|
|
| [Vrh] |
|
jaga
Forumaš(ica)
Pridružen/a: 23. 02. 2005. (15:28:07)
Postovi: (4)16
|
|
| [Vrh] |
|
Nesi
Inventar Foruma
(Moderator)
Pridružen/a: 14. 10. 2002. (14:27:35)
Postovi: (E68)16
Spol:
Sarma: -
|
|
| [Vrh] |
|
jaga
Forumaš(ica)
Pridružen/a: 23. 02. 2005. (15:28:07)
Postovi: (4)16
|
|
| [Vrh] |
|
vsego
Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (3562)16
Spol: 
Lokacija: /sbin/init
|
|
| [Vrh] |
|
|
biramo ih proizvoljno al t.d. svaki brid doticne t.mreze bude ukljucen bar u jedan, il nest drugo? 
(registracija vec prije obavljena 
upravo je to poanta 
