Задача: дан ориентированный граф. У каждой вершины есть некая величина H, нужно для каждой вершины посчитать H', равное минимуму из всех значений H вершин, до которых можно добраться из текущей. Количество вершин и ребер до 105.
Например, граф
1->2
2->3
2->5
3->4
5->6
H1 = 3, H2 = 30, H3 = 5, H4 = 1, H5 = 20, H6 = 10
Ответ:
H1' = 1, H2' = 1, H3' = 1, H4' = 1, H5' = 10, H6' = 10
И есть такое презабавное решение
G[N]; // список смежных вершин
H[N]; // те самые H
used[N] = {false}
dfs(v)
used[v] = true
suffle(G[v])
for to in G[v]
if used[to] = false
dfs(to)
H[v] = min(H[v], H[to])
main()
for step = 0..25
used = {false}
P[N] = {0,1,2...,N-1}
shuffle(P)
for v in P
dfs(v)
Завалить решение без shuffle довольно просто, а как быть с shuffle? Кто-нибудь умеет делать тесты для подобных решений? Или кто-нибудь может посчитать вероятность того, что решение выдаст правильный ответ? =)
А, не, показалось. Но если что, вот код того, что сверху написано.
Из каждой вершины будет запущен дфс и на первом же step'е уже в H будет правильный ответ.
можно пример, когда "Завалить решение без shuffle довольно просто"?
Я до компа доберусь очень не скоро, могу только описать тест, он такого вида: 1->2, 2->3, 2->0, 3->4, 4->1, 5->6, 6->7, 6->3, 7->8, 8->6... изначально минимум в нулевой вершине, если так цеплять циклы длины 4 друг за друга, то понадобится примерно N/4 step'ов.
Да, нет, почему? Первый же dfs из любой вершины доберётся до 0, если в неё можно добраться. На то он и dfs.
смотрите, дфс идет вглубь, если вершина не посещена. В меньшие номера вершин дфс не ходит.
Но если посещена, значит, для неё минимум уже посчитан правильно. На то он и dfs.
смотрите коммент ниже. Ваше утверждение верно для графов без циклов.
Опишу побробнее:
дфс 0 — сразц закончится
дфс 1 — дойдет до 4, обновит ответ для 1, 2
дфс 2 — вгубь не пойдет
дфс 3 — вглубь не пойдет, посмотри только значение в вершине 4, оно еще не минимальное
...
Зайдя в 1, мы перейдём в 2, а оттуда посмотрим в 0. После этого в 2 будет правильный минимум, а затем и в 1.
В 1 будет правильный, я это и написал, но в вершинах 4, 3 ответ не обновится
Из вершины 3 мы посмотрим в 4, а из 4 — в 1, где уже правильный минимум. А там — правильный минимум. Из-за этого в 4 станет правильный минимум, а из-за этого — в 3.
из 3 мы посмотрим в 4, но НЕ запустим дфс из 4, так как там уже были
Нет, ещё не были, судя по Вашему описанию, мы сначала пошли в 3.
А вообще-то, когда мы запускались из 2, мы уже посмотрели в 3, а оттуда — в 4, а оттуда — в 1.
дфс 1 ..дфс 2 ....дфс 0 ... дфс 3 ....дфс 4 дфс 2 дфс 3 лфс 4 дфс 5 ..дфс 6 .....
Можно по индукции доказать, что когда мы выходим из вершины v, в ней будет правильный ответ.
Конечно, для ациклического граафа)
Мне кажется, что мы с вами или о разных задачах, или о разных решениях)
О, кажется, Вы правы, да. Тогда есть вот такой пример. Берем 1000 циклов длины 10 на вершинах 0..9, 10..19, и так далее (направление 0->1->2 и так далее). И добавляем рёбра 10->1, 20->11, и так далее. Минимум только вершине 0. В вершине 1 будет правильный ответ, только если мы её запустим до остальных вершин цикла, с вероятностью 1/10. А эта вершина необходима для нахождения минимума в остальных циклах.
Обратите внимание на цикл
for step = 0..25. Он Вам все испортит.Нет, не портит. Только после того, как будет найдет правильный ответ в вершине 1, мы сможем попытаться найти минимум в вершине 11 и с ним будет такая же проблема. На прохождение каждого цикла потребуется около трёх итераций.
Если шафлу фартанет и мы начнем с вершины 1000, то все закончится в 1 дфс вообще.
Рассмотрим цикл длины 10 из Вашего примера. Рассмотрим событие "протащить минимум в m элементов из 10". Мат ожидание этого события будет равно 5. А теперь 25 раз запустите дфс и получите, что он все портит.
Учитывая то, что есть ребра 10->1, 20->11 и тд, мы получим правильный ответ в вершине с номером 1, если запустим дфс с любой из вершин c номером больше 9,и вероятность этого уж точно не 1/10
Ага, действительно(
Рассмотрим упрощенное решение, убрав
for step = 0..25и всеshuffle. Тогда на следующих входных данных:101 105 103 107 8 5 9 3
1 1
1 2
2 3 4
1 0
1 5
1 6
1 7
1 4
// H
// degree(0) G(0)
// degree(1) G(1)
// ...
shuffleс вероятностью 1/4 решение будет найдено верно (все значения = 3). Значит предложенные входные данные контрпример к упрощенному решению. И вопрос kvark161 состоит в том, как найти контрпример к указанному решению с 25 запусками dfs.Казалось бы, это же правильное решение и без шафла и с одной итерацией.
Далее КСС — это компонента сильной связности. Рассмотрим следующий пример.
2 2 2 2 2 2 2 2 2 2 2 1
1 1
1 2
1 3
2 4 0
1 5
1 6
1 7
1 8 4
1 9
1 10
1 11
1 8
// H
// degree(0) G(0)
// degree(1) G(1)
// ...
Рассмотрим более общий пример. Дано n — вершин, c — КСС и каждая КСС — это цикл длины l. Кроме того, циклы соединены аналогично предыдущему примеру, т.е. конденсация этого графа представляет собой один путь, а связи между КСС порождены соседними вершинами x и y так, что x<-y и в x входит друга из предшествующей КСС, а из y выходит в следующую КСС. Веса везде 2, кроме вершины с номером n-1. Рассмотрим мат ожидание следующего события: "dfs протащил минимум по компонентам". По определению мат ожидания (будем рассматривать вершины компонент начиная с последней) имеем:
M=1*l/n + 2*(l-2)/n + 3*(2+l-2)/n + 4*(2+l-2)/n + ... + (c-1)(2+l-2)/n + c*(2+l)/n = 1/2 + c/2 + 2/l - 4/n. Таким образом, основной вклад в среднее количество компонент по которым был протянут минимум вносит c. Следовательно, выбираемc=10^8>2^25, l=4.Эти выкладки требуют верификации, поэтому одобрение и критика приветствуются.