Simple Graphs
В тази секция ще разгледаме може би най-фундаменталната тема в състезателното програмиране - а именно теория на графите. Ще научим как да представяме графи в паметта по няколко различни начина. Ще разгледаме основните алгоритми за обхождане и търсене в графи: търсене в ширина, търсене в дълбочина, и алгоритъма на Дейкстра. Ще видим какво е минимално покриващо дърво, непресичащи се множества, топологично сортиране. Ще видим и една техника, която помага не само в графови задачи: разширяване на графа.Темите, които биха ви били полезни за тази секция са Графи и представяне на графи, Търсене в дълбочина, Търсене в ширина, и Алгоритъм на Дейкстра,
Откъм задачи това е една от най-дългите секции, като повечето алгоритми са покрити от поне две задачи (а по-основните - дори от повече). В повечето задачи се изисква директна имплементация или съвсем дребна модификация.
Castle
17
|
20
Roads
18
|
24
Speed
20
|
47
Amazing Race
8
|
50
Hidden Words
22
|
24
Chess Adventure
4
|
20
Lovers
29
|
40
White Horses
22
|
40
Cheating
45
|
35
Repairs
27
|
19
Expelliarmus
5
|
9
Maximal Shopping
37
|
26
Shortest Paths
31
|
9
Famous
19
|
23
DJ Krisa T
20
|
27
Snowy Roads
27
|
15
Square
9
|
21
Breakout
14
|
32
End-to-End
4
|
20