Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: 212 Data Transmission  (Citit de 8689 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« : Iulie 25, 2007, 22:03:45 »

http://acm.sgu.ru/problem.php?contest=0&problem=212

Nu prea cred ca am inteles problema asta. Dupa parerea mea se poate face pur si simplu flux maxim in acea retea si ar trebui sa iasa din moment ce restrictiile problemei spun ca toate muchiile A-B respecta conditia nivel[A]+1=nivel[ B ] si ca toate nivelurile sunt mai mici sau egale decat L. Totusi n<1500 si cel mai bun flux care il stiu are complexitate n^3 si nu prea cred ca se va incadra in timp.  Deci in concluzie restrictia aia cu nivelurile poate micsora timpul de executie al fluxului sau exista alta abordare?
Memorat
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #1 : Iulie 25, 2007, 22:16:08 »

Problema asta nu cere flux maxim, ci doar o posibilitate de a bloca reteaua. Cred ca ideea e sa o rezolvi in O(N+M), desi nu-mi vine nici o idee mai buna de O(N*M).
« Ultima modificare: Iulie 25, 2007, 22:36:48 de către Paul-Dan Baltescu » Memorat

Am zis Mr. Green
domino
Echipa infoarena
Nu mai tace
*****

Karma: 281
Deconectat Deconectat

Mesaje: 1.340



Vezi Profilul WWW
« Răspunde #2 : Iulie 25, 2007, 23:17:07 »

Din cate tin minte, s-ar putea ca O(N*M) sa mearga. Problema este de fapt un pas intermediar in algoritmul lui Dinic de flux maxim care este prezentat aici: http://books.google.com/books?id=nvcK1HSXmOMC&pg=PA116&lpg=PA116&dq=blocking+flow+layered+network+dinic&source=web&ots=yfv-g8Z8Dm&sig=ERftsBuQu0iZZrAFLMdeURdpqAk
Memorat
devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« Răspunde #3 : Iulie 26, 2007, 09:36:46 »

da scuze. Nu am fost prea atent cand am citit propozitia "Note, that you need not find the maximal possible data flow, just any blocking one."
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #4 : Decembrie 12, 2007, 12:17:16 »

Nu stie nimeni mai bine de O(N*M)?

Stau si ma chinui la problema asta de 2 luni, tot incerc sa scot O(N+M). De abia acum am citit mai atent topicul Tongue.
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #5 : Decembrie 17, 2007, 13:59:43 »

Ai luat Ac cu O(N*M)?
Memorat

Am zis Mr. Green
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #6 : Decembrie 17, 2007, 14:39:50 »

Iau TLE, dar am implementat taraneste. Cred ca o sa bag Karzanov si fac cu liste de adiacenta & stuff.
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines