1 Тема от MSDN

  • MSDN
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-03-09
  • Сообщений: 40

Тема: timus 1557

http://acm.timus.ru/problem.aspx?space=1&num=1557

Здравствуйте!
Собственно решаю так - строю остовное дерево, затем пытаюсь удалить каждое ребро из остовного дерева и в получившемся графе ищу все мосты... Ну также понятно что если мы в остовном дереве нашли мост то он с любым ребром может быть в паре. Вот, но в результате получаю ТЛ на 15 тесте....
Вообще идея решения правильная?

2 Ответ от aropan Отредактировано aropan (2010-03-19 03:37:19)

  • aropan
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-02-22
  • Сообщений: 15

Re: timus 1557

да, идея правильная, и по времени должно пройти <количество ребер в остовном> * <поиск всех мостов> получается O(N * (N + M)) ~ 200 000 000, вроде нормально для двух секунд.

3 Ответ от winger

  • winger
  • Участник
  • Неактивен
  • Откуда: Санкт-Петербург
  • Зарегистрирован: 2009-06-17
  • Сообщений: 25

Re: timus 1557

У этой задачи есть решение за O(V^2+E)

4 Ответ от MSDN

  • MSDN
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-03-09
  • Сообщений: 40

Re: timus 1557

Вы не могли бы по подробнее рассказать о решении за O(V^2+E) ?

5 Ответ от Oleg

  • Oleg
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-09-22
  • Сообщений: 86

Re: timus 1557

Определенно с N*M не пройдет.
Получил accepted используя алгоритм с http://wenku.baidu.com/view/cde30c22590 … 09c25.html
Выглядит как китайская грамота wink но разобраться можно.