Помогите, пожалуйста, решить задачу:
"По системе двусторонних дорог определить, можно ли, закрыв какие-нибудь три дороги, добиться того, чтобы из города A нельзя было попасть в город B."

1. Если из города А выходят всего три дороги можно перекрыть их.
2. Если в город Б приходят только три дороги можно перекрыть их.
3. А остальные наверное только перебором.
Хотя я могу и ошибаться

Похоже на правду но ещё нужно проверить :
под значимостью ребра будем понимать сумму степеней вершин, к-ые он соединяет.
находим путь из A в B и удаляем ребро с максимальной значимостью из этого пути, и так три раза, если после этого путь ещё найден - то нельзя.

Цитата(3 @ 25.10.2004, 18:17)

находим путь из A в B и удаляем ребро с максимальной значимостью из этого пути, и так три раза, если после этого путь ещё найден - то нельзя.

Посоветуйте, пожалуйста, каким алгоритмом находить путь из А и В. Говорят, что можно найти алгоритмом Форда-Белмана, но я его в глаза не видел.

i...
Поищи на форуме в алгоритмах, примеров куча!

Цитата(i @ 26.10.2004, 03:59)

Посоветуйте, пожалуйста, каким алгоритмом находить путь из А и В.

Алгоритм Дейкстры, тут про него уже говорилось очень много раз.
http://program.rin.ru/razdel/html/686.html

Цитата(Alex101 @ 26.10.2004, 09:52)

Цитата(i @ 26.10.2004, 03:59) Посоветуйте, пожалуйста, каким алгоритмом находить путь из А и В. Алгоритм Дейкстры, тут про него уже говорилось очень много раз. http://program.rin.ru/razdel/html/686.html

Собственно алгоритм Дейкстры здесь не очень нужен, потомучто он предназначен для поиска кратчайшего пути для графов с неотрицательными весами.
А нужно путь искать обычным перебором:
1) Помечаем вершину A
2) Смотрим в какую вершину можно попасть из A
3) Если вершина не помечена, то помечаем эту вершину и ищем путь из неё в B
4) Если из этой вершины в B попасть не удалось, то переходим к другой вершине, в к-ую можно попасть из A, помечаем её...

Мне кажется, что это классическая задача определения связности.
Лучше всего решение задачки описанио в книженции: "Фундаментальные алгоритмы на С" Роберта Седжевика.

что-то ничего кроме перебора в голову не приходит, но...
его можно немного пооптимизировать:
1. находим кратчайший путь A-B
2. удаляем одно из ребер на нем
3. ищем новый кратчайший путь (без удаленного ребра)
4. удаляем одно из его ребер
5. ищем еще один кратчайший путь
6. удаляем одно из его ребер

таким образом перебирать нужно не C из n по 3, а несколько меньше
перебор получается, когда мы решаем, какое ребро пути удалить

кратчайший путь нужен для того, чтобы сократить количество ребер из которого мы выбираем кандидата на удаление
к тому же поиск любого пути по сложности практически не отличается от поиска кратчайшего...

maxim1000
Чета я не понял....
Ну поудаляем мы ребра и что? Нам же нужно найти три такие дороги перекрыв которые мы полностью отризаем А от Б.
Объясни плз.....

ну рассмотрим простой перебор:
выбираем наугад три дороги, удаляем их, проверяем наличие пути
если путь есть, востанавливаем дороги, удаляем другую тройку, опять проверяем...
и так, пока не перепробуем все тройки дорог или не найдем нужную
а в вышеописанном варианте было предложено оптимизировать этот перебор:
использовался следующий факт:
если выбрать какой-нибудь путь А-В, то на нем обязательно должна лежать одна из дорог
значит, можно перебирать не все дороги, а только те, которые лежат на путях, соединяющих А и В
ну и для уменьшения вариантов выбирается кратчайший путь - меньше всего ребер...

А не связана ли эта задача с поиском остовного дерева?

maxim1000
АААААа, понял, спасибо!

3,14 То что ты описал есть не что иное, как поиск в ширину. Или волновой поиск.

Цитата(Morpheus @ 28.10.2004, 14:18)

3,14 То что ты описал есть не что иное, как поиск в ширину. Или волновой поиск.

Кто бы спорил, но как перебор не называй он им и останется