Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 18.11.2010, 04:32
Новичок

Отправить личное сообщение для Jahangir Najafov Посмотреть профиль Найти все сообщения от Jahangir Najafov
 
Регистрация: 18.11.2010
Сообщений: 1

Подсчёт количества вершин, принадлежащих циклам
Добрый вечер!

Никак не могу решить задачу с уже окончившейся олимпиады.
Задача А . http://acmp.ru/asp/champ/index.asp?m...s&id_stage=288

Как мне кажется, надо находить циклы и увеличивать ответ на количество рёбер цикла. С оговоркой, что ребро, принадлежащее двум простым циклам учитывается один раз.

Придумал несколько алгоритмов, но ни один из них не удовлетворяет обоим тестам сразу.
  #2  
Старый 18.11.2010, 16:37
гость

 
Сообщений: n/a

По моему задача про мосты и компоненты двусвязности.

Очевидно, что ни один мост в графе нельзя заменить односторонней дорогой. Мосты разделяет граф на двусвязные компоненты, а в любой двусвязной компоненты всегда можно найти цикл через все вершины (вытекает практически из определение), что лучшее что можно сделать.
  #3  
Старый 18.11.2010, 16:38
гость

 
Сообщений: n/a

т.е. все ребра кроме ребер на цикле можно вообще удалить, а цикл как угодно ориентировать
  #4  
Старый 20.11.2010, 01:52
гость

 
Сообщений: n/a

ну, что, говорите, помогло? пожелания, предложения, замечания? а то блин как со стеной тут говоришь. так и уйду н*х с этого форума... в веб2.0 (стековерфлоу)
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Поиск количества делителей чисел на заданом отрезке kobra Математические алгоритмы 5 06.11.2010 01:22
уменьшение количества точек гость Вычислительная геометрия 4 16.07.2010 19:06
Ументшение количества цветов в рисунке гость Обработка изображений, звук, графика 7 03.06.2009 18:43
Округление до количества значащих чисел spoilt_child Реализация, исходники, языки 5 17.12.2008 16:37
Сложение большого количества рисунков гость Обработка изображений, звук, графика 5 01.10.2008 13:50