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

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

Вернуться   Форум программистов > Delphi программирование > Паскаль, Turbo Pascal, PascalABC.NET
Регистрация

Восстановить пароль
Повторная активизация e-mail

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

Ответ
 
Опции темы Поиск в этой теме
Старый 23.04.2008, 23:16   #1
RebelderGirl
Новичок
Джуниор
 
Регистрация: 23.04.2008
Сообщений: 1
Счастье срочно требуется! стандартные олимпиадные задачи по графам

ни у кого не завалялось решение стандартных олимпиадых задач по графам?

Задача 04-4. Издевательство
Имя входного файла input.txt
Имя выходного файла output.txt
Максимальное время работы на одном тесте: 5 секунд
Штирлиц ехал на машине, увидел голосующего Бормана, и проехал мимо. Через некоторое время он снова увидел голосующего Бормана, и снова проехал мимо. Вскоре он опять увидел голосующего Бормана.
- Издевается! - подумал Борман.
- Кольцевая! - догадался Штирлиц.
В городе N площадей. Любые две площади соединены между собой ровно одной дорогой с двусторонним движением. В этом городе живет Штирлиц. У Штирлица есть хобби - он любит воскресным утром выйти из дома, сесть в машину, выбрать какой-нибудь кольцевой маршрут, проходящий ровно по трем площадям (то есть сначала он едет с какой-то площади на какую-то другую, потом - на третью, затем возвращается на начальную, и опять едет по этому маршруту). Он воображает, что где-то на этом пути стоит Борман. И так вот ездит Штирлиц все воскресенье, пока голова не закружится, и радуется...
Естественно, что Штирлицу хочется проезжать мимо точки, в которой, как он воображает, стоит Борман, как можно чаще. Для этого, естественно, выбранный Штирлицем маршрут должен быть как можно короче. Напишите программу, которая выберет оптимальный для Штирлица маршрут.
Формат входных данных
Во входном файле INPUT.TXT записано сначала число N (3 <= N <= 100), а затем матрица NxN расстояний между площадями (число в позиции i,j обозначает длину дороги, соединяющей i-ую и j-ую площади). Все числа в матрице (кроме стоящих на главной диагонали) - натуральные, не превышающие 1000. Матрица симметрична относительно главной диагонали, на главной диагонали стоят 0.
Формат выходных данных
В выходной файл OUTPUT.TXT выведите номера площадей в оптимальном маршруте. Если маршрутов несколько, выведите любой из них.
Пример
input.txt output.txt
5
0 20 10 30 40
20 0 30 1 2
10 30 0 40 1000
30 1 40 0 21
40 2 1000 21 0 4 5 2

(Разбор)
Нам требуется найти цикл длины 3 минимального веса в полном взвешенном графе. Переберем всевозможные тройки вершин (это можно сделать, например, тремя вложенными циклами - каждая из переменных цикла соответствует какой-то из трех искомых вершин). Любая тройка однозначно задает цикл длины три. Выберем тройку, для которой вес соответсвующего цикла минимален.

Задача 1. Разминка
Имя входного файла input.txt
Имя выходного файла output.txt
Максимальное время работы на одном тесте: 3 секунды
Формат входных данных
Во входном файле записано сначала число N (1<=N<=100), а затем N пар чисел. Первое число каждой пары - натуральное, не превышающее 30000. Второе число каждой пары - 0 или 1.
Формат выходных данных
Требуется найти и вывести в выходной файл номер пары, в которой второе число равно 1,

а из всех таких пар ту, в которой первое число максимально (если таких пар несколько, выведите любую из них).
Если пар, у которых второе число равно 1 нет, выведите в выходной файл -1.
Пример
input.txt output.txt
4
25 1
70 1
100 0
3 1 2
(Разбор)
Эта задача представляет собой небольшую часть реализации алгоритма Дейкстры, а именно поиск вершины v из второго множества, известное расстояние от начальной вершины до которой минимально


Задача 4. Автобусы
Имя входного файла input.txt
Имя выходного файла output.txt
Максимальное время работы на одном тесте: 5 секунд
Между некоторыми деревнями края Васюки ходят автобусы. Поскольку пассажиропотоки здесь не очень большие, то автобусы ходят всего несколько раз в день.
Марие Ивановне требуется добраться из деревни d в деревню v как можно быстрее (считается, что в момент времени 0 она находится в деревне d).
Формат входных данных
Во входном файле записано число N - общее число деревень (1 <= N <= 100), номера деревень d и v, затем количество автобусных рейсов R (0 <= R <= 10000). Затем идут описания автобусных рейсов. Каждый рейс задается номером деревни отправления, временем отправления, деревней назначения и временем прибытия (все времена - целые от 0 до 10000). Если в момент t пассажир приезжает в какую-то деревню, то уехать из нее он может в любой момент времени, начиная с t.
Формат выходных данных
В выходной файл вывести минимальное время, когда Мария Ивановна может оказаться в деревне v. Если он не сможет с помощью указанных автобусных рейсов добраться из d в v, вывести -1.
Пример
input.txt output.txt
3
1 3
4
1 0 2 5
1 1 2 3
2 3 3 5
1 1 3 10 5
(Разбор)
Построим граф, вершинами которого будут города, а ребрами - маршруты. Весом ребра назовем время прибытия автобуса в конечный пункт, а весом пути - вес последнего, самого тяжелого, ребра. Путем в нашем графе назовем последовательность ребер, такую что вес пути до любой промежуточной вершины v не превосходит времени отправления автобуса, соответствующего следующему ребру пути. В рамках введенных обозначений решение задачи сводится к реализации алгоритма Дейкстры на этом графе.
RebelderGirl вне форума Ответить с цитированием
Старый 24.04.2008, 13:23   #2
МаксимNEWProgramm
Пользователь
 
Аватар для МаксимNEWProgramm
 
Регистрация: 04.04.2008
Сообщений: 57
По умолчанию

После трудно дня за срочно никто не будет решать ...Если хотите за отдельную плату то
стучить в ICQ 459-466-346. там посмотрим.
Программированине-это не очередная пара, а искуство показать себя!!!
МаксимNEWProgramm вне форума Ответить с цитированием
Ответ


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

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

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Помогите решите олимпиадные задачи, пожалуйста!!! student523 Помощь студентам 1 17.12.2007 17:01
Срочно! Требуется разработчик Bin go Фриланс 2 13.03.2007 20:43