Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 25.03.2010, 17:24   #1
k1r1ch
ACM!
Форумчанин
 
Аватар для k1r1ch
 
Регистрация: 19.06.2009
Сообщений: 382
Вопрос Графы. Проблема.

Помогите с задачей - http://www.acmp.ru/index.asp?main=task&id_task=206
Меня смущает то, что вершина задается двумя величинами - номером станции и временем, причем время - до 10^9. Хотя бы например, как хранить кратчайшее расстояние для каждой вершины - array[100][1000000000]? Единственный способ, который я вижу - не разделять вершину на вершины по времени, а работать как с одной, но тогда вообще непонятно как искать кратчайший путь?
k1r1ch вне форума Ответить с цитированием
Старый 25.03.2010, 19:54   #2
Грымзик
Пользователь
 
Регистрация: 17.09.2009
Сообщений: 40
По умолчанию

Здесь не нужны никакие графы, это динамическое программирование. Строите массив из N элементов. Далее цикл из M шагов. На каждом j-ом шаге i-ый элемент матрицы показывает минимальное время, за которое можно добраться до i-ой станции, пользуясь только первыми j электричками. Чтобы заполнить i-й элемент на j+1 шаге, надо пройтись по всему массиву, найти все станции, на которых останавливается M-ая электричка, и не просто останавливается, а не раньше, чем значение этого элемента (т.е минимальное время прибытия на эту станцию). Смотрим останавливается ли после этого электричка на i-ой станции. Если останавливается, то смотрим во сколько, и из всех таких возможных времен прибытия на i-ую станцию выбираем минимальное. Т.е по времени получается
100(шагов)*100(станций прибытия)*100(станций отъезда на предыдущим шаге)*100(станций для проверки останавливается ли электричка на i-ой станции)=10^8 Не очень хорошо. Я эту задачу давно делала, тогда была тестирующая система с тестами с олимпиады, последний тест не прошла по времени. Но, поскольку индексы станций в расписании для каждой электрички расположены в возрастающем/убывающем порядке, то поиск останавливается ли электричка на i-ой станции можно сделать за log_2 100=7
Грымзик вне форума Ответить с цитированием
Старый 26.03.2010, 08:53   #3
k1r1ch
ACM!
Форумчанин
 
Аватар для k1r1ch
 
Регистрация: 19.06.2009
Сообщений: 382
Вопрос

Спасибо конечно огромное, но мне все равно еще не все понятно:
Цитата:
Здесь не нужны никакие графы (а почему тогда там тема графы?), это динамическое программирование. Строите массив из N элементов. Далее цикл из M шагов. На каждом j-ом шаге i-ый элемент матрицы показывает минимальное время, за которое можно добраться до i-ой станции, пользуясь только первыми j электричками. Чтобы заполнить i-й элемент на j+1 шаге, надо пройтись по всему массиву, найти все станции, на которых останавливается M-ая электричка (то есть j-ная, электричка с номером текущего шага?), и не просто останавливается, а не раньше, чем значение этого элемента (т.е минимальное время прибытия на эту станцию). Смотрим останавливается ли после этого электричка на i-ой станции. Если останавливается, то смотрим во сколько, и из всех таких возможных времен прибытия на i-ую станцию выбираем минимальное (как так, если возможное время прибытия только одно - то, когда j-ная электричка останавливается на станции i?). Т.е по времени получается
100(шагов)*100(станций прибытия)*100(станций отъезда на предыдущим шаге)*100(станций для проверки останавливается ли электричка на i-ой станции)=10^8 Не очень хорошо. Я эту задачу давно делала, тогда была тестирующая система с тестами с олимпиады, последний тест не прошла по времени. Но, поскольку индексы станций в расписании для каждой электрички расположены в возрастающем/убывающем порядке, то поиск останавливается ли электричка на i-ой станции можно сделать за log_2 100=7
k1r1ch вне форума Ответить с цитированием
Старый 26.03.2010, 20:01   #4
Грымзик
Пользователь
 
Регистрация: 17.09.2009
Сообщений: 40
По умолчанию

Да, похоже я что-то не так написала, ведь по такому алгоритму у меня получается, что он не может j+1-ой электричкой воспользоваться раньше, чем j-ой. Но это точно динамическое программирование, как можно графы сюда впихнуть не знаю.
Нашла в инете такое решение
Цитата:
Решение:
Эту задачу можно решать многими способами (как и любую другую), но я буду использовать далеко не самый эффективный, но укладывающийся в ограничения для этой задачи.
Заведем одномерный массив для станций - для каждой станции будем хранить текущее минимальное время, за которое на нее можно добраться. Сначала заполним все бесконечностью. Также заведем массив, в котором будем хранить информацию о поездах - во сколько на какую станцию прибывает, а также, в каком направлении идет.
Для определения направления достаточно сравнить две любые станции на пути электрички - если номера возрастают, то поезд идет от города, иначе - к городу.
Теперь начинается медленное и неэффективное решение:
Запустим цикл (i) от 1 до количества станций. Затем идем по всем станциям (j), начиная с первой. Затем идем по всем поездам и, если время отправления поезда с этой станции больше либо равно текущему времени, за которое можно добраться до этой станции, считаем что на этот поезд можно сесть - прогоняем цикл по всем станциям, на которых останавливается этот поезд, и, если текущее время на станции больше, чем время прибытия на эту станцию данного поезда, то заменяем его.
Если за весь шаг цикла по i не произошло ни одного обновления, то прерываем работу программы. Несмотря на крайнюю неэффективность алгоритма программа успевает пройти все тесты.
А здесь http://www.informatics.ru/viewproble...42&round_id=91 вообще вроде исходник скачать можно.

Последний раз редактировалось Грымзик; 26.03.2010 в 20:11.
Грымзик вне форума Ответить с цитированием
Старый 26.03.2010, 20:01   #5
Грымзик
Пользователь
 
Регистрация: 17.09.2009
Сообщений: 40
По умолчанию

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

Последний раз редактировалось Грымзик; 26.03.2010 в 20:12.
Грымзик вне форума Ответить с цитированием
Старый 27.03.2010, 10:57   #6
LeBron
Форумчанин
 
Регистрация: 10.10.2009
Сообщений: 680
По умолчанию

Самое тупое решение - это Беллмен-Форд. А вообще можно обходом в ширину написать, если ограничения повыше.
LeBron вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Графы Prisian Общие вопросы Delphi 11 02.05.2013 22:02
Графы Пaвeл Помощь студентам 0 14.03.2010 10:00
графы delete Общие вопросы C/C++ 2 28.10.2009 21:31
Графы на С++ corri Общие вопросы C/C++ 3 03.10.2009 01:42
графы paladinn Помощь студентам 1 07.06.2009 18:04