Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/3: Рейтинг темы: голосов - 3, средняя оценка - 5.00
Jahangir Najafo
0 / 0 / 0
Регистрация: 27.11.2009
Сообщений: 4
1

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

18.11.2010, 03:59. Просмотров 471. Ответов 4
Метки нет (Все метки)

Добрый вечер!

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

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

Придумал несколько алгоритмов, но ни один из них не удовлетворяет обоим тестам сразу.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.11.2010, 03:59
Ответы с готовыми решениями:

Подсчёт количества одинаковых строк в файлах папки
Здравствуйте. Пытаюсь написать программу на C# со следующим алгоритмом: 1. В указанной папке,...

Подсчёт количества символов и количества строк в файле
Нужно написать программу, которая запрашивает у пользователя имя (адрес) текстового файла, далее...

Подсчёт вершин на N-ом уровне не пустого бинарного дерева
Доброго времени суток! Пожалуйста прошу помочь решить задачку, подскажите хотя бы алгоритм,...

Определение количества элементов массива, принадлежащих интервалу a, b
Определить количество элементов, непринадлежащих промежутку (A,B) и расположенных в столбцах с...

Вычисления количества простых чисел, принадлежащих отрезку
Задание: Составить программу вычисления количества простых чисел, принадлежащих отрезку . Для...

4
Питекантроп
249 / 143 / 21
Регистрация: 14.06.2010
Сообщений: 340
23.11.2010, 18:30 2
Предлагаю следующий вариант для решения задачи:
1. Создать список всех существующих дорог прямого соединения. (два значения: начало и конец).
2. Каждой дороге в соответствие целочисленный вектор. Его возможные значения: 0 - дорога осталась двухсторонней. 2 - дорогу сделали односторонней из начала в конец. 3 - сделали односторонней в обратном направлении.
3. Перебор всех возможных изменений дорог. Всего 3^(k) состояний (k - количество дорог). Т.к. k у нас может быть разным, то перебор можно сделать или циклом от 1 до 3^(k), а из счетчика извлекать значения состояний; или рекурсией, как бы я и сделал. Рекурсивная функция по очереди рассматривает 3 состояния и вызывает себя же, но для следующей дороги.
4. В процессе перебора: если количество упраздненных двухсторонних дорог больше, чем предыдущее макс. значение, то ищем матрицу связности текущего состояния перебора. Если она совпадает с исходной, то запоминаем найденное макс. значение.

П.С. ИМХО, если искать циклы, как вы предложили, то можно легко ошибиться. Т.к. связность двух узлов может достигаться без циклов.
0
valeriikozlov
Эксперт С++
4691 / 2517 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
23.11.2010, 22:32 3
Цитата Сообщение от Питекантроп Посмотреть сообщение
Всего 3^(k) состояний (k - количество дорог)
А Вы представляете себе кол-во дорог при 100 точек городов (как сказано в условии).
Уточняю еще одно:
Время: 1 сек
Это время на один тест. Если даже суметь написать Ваш алгоритм, то наверное несколько суток придется ждать результата на максимальный тест. Есть более легкое решение, Jahangir Najafo немного до него не дошел.
0
Питекантроп
249 / 143 / 21
Регистрация: 14.06.2010
Сообщений: 340
26.11.2010, 23:05 4
valeriikozlov, согласен, при 100 городах расчет будет длиться долговато
0
Christopher M.
9 / 9 / 1
Регистрация: 02.07.2010
Сообщений: 28
27.11.2010, 21:50 5
Хм... поступило предположение, что можно просто матрицу смежности править... т.е. пройдя по главной диагонали сверху вниз и рассматривая пару из строки из столбца с одинаковым номером в них из всех пар симметричных единиц вынуть по одной, так, чтобы количество их в каждой строке и в каждом столбце оказалось не меньше, чем половина от первоначального. Т.е. если в строке (и столбце!) три единицы, можно вынуть только одну.... и если две, то одну... и если одна, то ни одной...
Как это доказать, и можно ли это доказать, не знаю, но по-моему если сие правильно, решение будет быстрее, чем при поиске циклов...

В общем, надо подумать. Жаль, для более сложных "городов" примеров нет))))
0
27.11.2010, 21:50
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.11.2010, 21:50

Подсчёт количества файлов
Доброго времени суток. Направьте, пожалуйста, на пусть истинный, имеется скрипт считающий...

Подсчёт максимума и количества
Привет. Есть проблема : выводит максимальное число как введенную последовательность и не работает...

Подсчёт количества записей
Есть таблица "Заезды" и столбец в ней "Кличка лошади", в нём записи повторяются. Уникальный...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru