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

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

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

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

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

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

Придумал несколько алгоритмов, но ни один из них не удовлетворяет обоим тестам сразу.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
18.11.2010, 03:59
Ответы с готовыми решениями:

Подсчет количества различных элементов одномерного массива не принадлежащих отрезку [R,P]
помогите пожалуйста задачку решить:) Составить программу подсчета количества различных элементов...

Подсчет количества вершин дерева
Добрый вечер. Возникла проблема в коде, не знаю как "соединить код" всей программы + самого...

Подсчет количества вершин бинарного дерева
#include "pch.h" #include <iostream> #include <ctime> #include <cstring> using namespace std;...

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

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
Эксперт С++
4703 / 2528 / 753
Регистрация: 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
9 / 9 / 1
Регистрация: 02.07.2010
Сообщений: 28
27.11.2010, 21:50 5
Хм... поступило предположение, что можно просто матрицу смежности править... т.е. пройдя по главной диагонали сверху вниз и рассматривая пару из строки из столбца с одинаковым номером в них из всех пар симметричных единиц вынуть по одной, так, чтобы количество их в каждой строке и в каждом столбце оказалось не меньше, чем половина от первоначального. Т.е. если в строке (и столбце!) три единицы, можно вынуть только одну.... и если две, то одну... и если одна, то ни одной...
Как это доказать, и можно ли это доказать, не знаю, но по-моему если сие правильно, решение будет быстрее, чем при поиске циклов...

В общем, надо подумать. Жаль, для более сложных "городов" примеров нет))))
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
27.11.2010, 21:50

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

Подсчет количества вершин на каждом уровне дерева
В общем я написал функцию, но что-то он считает неверно. Не могли бы вы мне помочь разобраться? ...

Функция: подсчет количества вершин на N-ом уровне бинарного дерева
Помогите пожалуйста написать функцию ,которая подсчитывает число вершин на N-ом уровне бинарного...

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

Подсчет различных элементов одномерного массива, не принадлежащих отрезку
Помогите, пожалуйста составить программу подсчета различных элементов одномерного массива, НЕ...

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

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


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

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

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