|
Titlul: 212 Data Transmission Scris de: Savin Tiberiu din 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? Titlul: Răspuns: 212 Data Transmission Scris de: Paul-Dan Baltescu din 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).
Titlul: Răspuns: 212 Data Transmission Scris de: Mircea Pasoi din 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
Titlul: Răspuns: 212 Data Transmission Scris de: Savin Tiberiu din 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."
Titlul: Răspuns: 212 Data Transmission Scris de: Andrei Grigorean din 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 :P. Titlul: Răspuns: 212 Data Transmission Scris de: Paul-Dan Baltescu din Decembrie 17, 2007, 13:59:43 Ai luat Ac cu O(N*M)?
Titlul: Răspuns: 212 Data Transmission Scris de: Andrei Grigorean din 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.
|