|
|
|
|
|
|
|
Вернуться
| 1 Нигматуллин Нияз Габдуллазянович [СПбГУ ИТМО], 12 октября 2009 г. 13:01:11 | |
о сделать нужно посчитать кол-во различных способов таких, что ни один цикл не лежит на пути из v -> i и v -> j.
Мы уже посчитали B(i) - это кол-во путей таких, что на пути v -> i, нет вершин через которые проходит цикл.
Давайте перемножим B(i) * B(j). Но теперь заметим что в B(i) мы посчитали такие способы, когда поддерево, в котором лежит j, это кактус, здесь мы посчитаем те случаи, когда есть цикл на пути из v -> j.
То же самое для B(j). Причем еще не только это, также для любых других e, когда есть ребро из v -> e и e не является предком v, когда поддерево с корнем в вершине e это кактус, мы также посчитали дважды в B(i) и B(j).
Тогда мы сделаем так, B(i) * B(j) / N(v). так как N(v) это произведение всех таких G(e) когда, то есть e это кактус. Тогда получится что G(i) и G(j) мы вообще не считали, а все остальные G(e) мы посчитали только один раз.
Добавляем это к ответу.
G(v) += B(i) * B(j) / N(v).
Так как ответ может быть большой, нужно было использовать длинную арифметику, и я не знаю, можно ли это сдать полностью на языке отличном от Java.
Ну чтобы ускорить алгоритм, разумно было хранить граф в списке смежности, так как всего V - 1 ребро.
Сложность алгоритма O(N ^ 3).
|
|
|
| 2 Нигматуллин Нияз Габдуллазянович [СПбГУ ИТМО], 12 октября 2009 г. 13:00:33 | |
Разбор задачи Кактусы:
Задача будет решаться методом динамического программирования на дереве.
Для начала в поиске в глубину для каждой вершины посчитаем и положим в массив его родителя и для каждой пары вершин посчитаем еще одно число.
Для пары вершин (u; v) где u является предком v, f(u, v) = i, где путь из u -> v начинается с ребра (u, i), а u не является предком v, f(u, v) = -1.
Следующая часть, это динамика: тоже обходом в глубину, и будет считаться рекурсивно.
Рекурсивная функция будет возвращать кол-во кактусов, которые можно построить в поддереве с корнем в вершине v, назовем эту функцию G(v).
Для начала посчитаем кол-во кактусов таких, что через v не проходит ни одного цикла, то есть к вершине v не добавляется ребер.
Это произведение всех G(u), таких что существует ребро из v -> u и u не предок v. Назовем это N(v).
Прибавим к G(v) += N(v).
Теперь посчитаем кол-во таких случаев когда добавляется ребро из вершины v к его потомку.
Для всех u таких, что u является потомком v (или f(v, u) != -1) пройдем все вершины i, которые принадлежат кратчайшему пути из v -> u (включая сами v и u) и найдем произведение всех G(j), j смежно с i, и j не принадлежит пути из v -> u. Назовем это B(u).
Почему именно так: Мы посчитаем кол-во различных кактусов, причем в этих случаях до этого подкактусами могли только быть все поддеревья которые не пересекаются с путем из v -> u, иначе через какую нибудь вершину проходило бы два цикла, один через новое ребро, а другой через то которое добавили до этого.
Все такие B(u) которые посчитали здесь, мы добавим к G(v), не учитывая те, когда u является смежным с v,(либо f(v, u) != u) так как между ними ребро уже есть с самого начала.
Теперь посчитаем кол-во кактусов, когда мы добавляем ребро не к вершине v, но появляется цикл через вершину v. очевидно, что это ребро будет перекрестным.
Переберем все пары (i, j) где i и j являются потомками v, причем f(v, i) != f(v, j), это значит что v является наиближайшим общим предком, и попытаемся между i и j добавить ребро.
Ну чтобы эт
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
