Advanced Graphs
В тази секция ще наблегнем на няколко от по-сложните алгоритми в графи - намиране на оптимално двойкосъчетание ("matching"), потоци ("maximum flows"), удовлетворяване на булев израз ("2-SAT"), така наречения Унгарски Алгоритъм, който се справя със задачата за разпределението ("assignment problem"), и дори ще зачекнем максимални потоци с минимална цена ("Min-cost Max-flow"). Идеята (а и имплементацията, в някои случаи) на тези алгоритми не е тривиална, и всъщност броят програмисти, които могат да ги напишат без помощта на интернет или книга е много малък (под 1%). Както ще видите, с тях обаче могат да се зададат доста интересни задачи, в които самото досещане, че може да се ползва някой от тези алгоритми е относително сложно.Теми, които биха ви помогнали за тази секция, са Оптимално двойкосъчетание, Максимални потоци, Удовлетворяване на булеви изрази, Унгарски алгоритъм, и Потоци с минимална цена.
Голяма част от задачите в секцията се решават с мачинг или поток, но има и няколко, които са с някои от другите.
Knights
13
|
28
Towers
3
|
21
Pranka
4
|
13
Browse
7
|
14
Ditchers
4
|
50
Streets
2
|
12
Earrings
7
|
37
Stara Zagora
3
|
7
Movie Seating
6
|
29
Snow Cleaning
14
|
13
DotA
7
|
41
Gifts
4
|
9
Deathstars
27
|
21
Lights
2
|
29
Ransom
2
|
67