Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Algo » Сумма по всем достижимым вершинам
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Решаю тут одну задачу и не могу придумать такой вот алгоритм:
дан ориентированный ациклический граф, в каждой вершине записано число. Хочется для каждой вершины посчитать сумму чисел по всем вершинам, которые достижимы из данной.
Естественно, надо что-нибудь быстрее O(N^3) (N - количество вершин).
Ну вот у меня только такая мысль.... Найти для каждой вершины множество достижимых из нее вершин. Но! Хранить это можно эффективно - в виде битовой карты. То есть скажем множество из 1000 вершин можно представить не больше чем 20 числами типа long long.
Все это можно сделать за один проход в глубину. Обновление тоже очень быстро как битовая операция "или" для массива в 20 чисел.....
Глупый глупый я. Если вершинам приписать веса, равные разным степеням двойки, сконденсировать граф и заюзать этот алгоритм, то получится в точности флойд, а его быстрее, чем за куб не сделать 
Почему? Мы же каждую вершину обходим ровно 1 раз. То есть как бы обход запускаем много раз - но обойдет он в сумме ровно N вершин.
Асимптотика O(N+M*P(n)) где P(n) - время сливания двух битовых карт.
Не ну как бы да если без карт битовых то P(n) = N
тогда время кубическое..... 
Наверно я не понял условие как всегда, но что мешает брать вершину, запускать поиск в глубину, суммировать все вершины достижимые из неё?
Сложность получается O(V*E) ~= O(V^3).
Мы тут про такой алгоритм и говорили... Просто его можно ускорить (немного) - Чтобы по каждой вершине не ходить по 100 раз, можно замемоизировать - то есть хранить список достижимых вершин из данной. Как это сделать эффективнее чем в лоб написано выше
Ааа Я просто прочитал типо что бы было N^3, а надо быстрее ^_^
Так а можно точные размеры кол-ва рёбер и вершин? Не понимаю как можно решать задачу, вам нужно оптимальнео решение? о_о Или которое только даёт Accepted!!! ~_~
Я уже решил ту задачу, там N было не больше 500 и даже три вложенных цикла прошли по времени.
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Algo » Сумма по всем достижимым вершинам