|
Titlul: 839. Optimal Marks Scris de: Marius Stroe din Decembrie 12, 2007, 16:00:39 http://www.spoj.pl/problems/OPTM/
Ce se cere e mark[x1] ^ mark[y1] + mark[x2] ^ mark[y2] + ... minima. Cum ^ se face la nivel de bit, rezolvand suma anterioara pentru fiecare bit obtin rezultatul optim. Ce nu stiu e cum sa rezolv mark[x1'] ^ mark[y1'] + mark[x2'] ^ mark[y2'] + ... unde elementele pot lua valorile 0, 1, unele fiind fixate, si suma sa fie minima ? Titlul: Răspuns: 839. Optimal Marks Scris de: Mircea Pasoi din Decembrie 12, 2007, 18:08:54 Problema la care ai redus-o se poate rezolva determinand o taietura minima (http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem) intr-un graf. Sper sa-ti fie de folos acest hint :)
Titlul: Răspuns: 839. Optimal Marks Scris de: Marius Stroe din Decembrie 13, 2007, 19:24:05 Ai zis prea mult. :P
Titlul: Răspuns: 839. Optimal Marks Scris de: dragus marius din Februarie 10, 2009, 18:32:09 A implementat cineva solutia aceasta la problema(flux)? Implementarea mea ia tle... si pe calculatorul meu nu merge decat pana la vreo 200 de noduri in 6 secunde... deci diferenta e destul de mare.
Titlul: Răspuns: 839. Optimal Marks Scris de: Marius Stroe din Februarie 10, 2009, 22:30:26 Mie îmi merge în 0.31s.
Titlul: Răspuns: 839. Optimal Marks Scris de: dragus marius din Februarie 10, 2009, 22:32:46 Cu flux normal .. adica nimic special ?adica cu edmonds karp? :shock:.. Mersi fain , am sa mai incerc atunci si maine sa mai implementez o data.
Titlul: Răspuns: 839. Optimal Marks Scris de: Marius Stroe din Februarie 11, 2009, 12:17:40 Da, cu algoritmul lui Edmonds Karp.
|