4501
правка
Прямолинейное дерево Штейнера: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 39: | Строка 39: | ||
'''for''' (каждой дуги <math>(u, v) \in G \;</math> по порядку неубывания длины) { | '''for''' (каждой дуги <math>(u, v) \in G \;</math> по порядку неубывания длины) { | ||
s1 = find_set(u); s2 = find_set(v); | s1 = find_set(u); s2 = find_set(v); | ||
'''if''' (s1!=s2){ | '''if''' (s1 != s2) { | ||
добавить (u, v) в дерево T; | добавить (u, v) в дерево T; | ||
'''for''' (каждого соседа w точек u, v в G) | '''for''' (каждого соседа w точек u, v в G) | ||
| Строка 50: | Строка 50: | ||
} | } | ||
} | } | ||
сгенерировать пары «точка-ребро» | сгенерировать пары «точка-ребро» при помощи lca_answer_queries; | ||
'''for''' (каждой пары (p, (a, b), (c, d)) в порядке невозрастания положительного прироста) | '''for''' (каждой пары (p, (a, b), (c, d)) в порядке невозрастания положительного прироста) | ||
'''if''' (ребро (a, b), (c ,d) не было удалено из T) { | '''if''' (ребро (a, b), (c ,d) не было удалено из T) { | ||