212 Data Transmission

[•devilkind]

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?

[•pauldb]

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).

[•domino]

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

[•devilkind]

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."

[•wefgef]

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 .

[•pauldb]

Ai luat Ac cu O(N*M)?

[•wefgef]

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