Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Прочее";
Текущий архив: 2006.12.31;
Скачать: [xml.tar.bz2];

Вниз

задача нужны идеи   Найти похожие ветки 

 
sat ©   (2006-12-14 00:47) [0]

Путь в графе

Задан ориентированный граф с N вершинами и M дугами (2 ≤ N ≤ 1000000, 0 ≤ M ≤ 1000000). Вершины графа пронумерованы, начиная с единицы. Некоторые пары вершин могут быть соединены более чем одной дугой, допускаются петли. Требуется определить, существует ли путь из вершины A в вершину B (1 ≤ A, B ≤ N, A ≠ B) и в случае положительного ответа  найти один из таких путей. При решении задачи использовать самостоятельно разработанный класс «очередь».
Входные данные: текстовый файл PATH.IN содержит N+2 строки. Первая строка файла содержит значения N и M,  вторая строка – значения A и B. Каждая из последующих строк описывает дуги, выходящие из одной вершины, и содержит число таких дуг, а также номера вершин, в которые эти дуги входят. Числа в строке разделяются одним или несколькими пробелами.
Выходные данные помещаются в текстовый файл PATH.OUT. В случае, если искомого пути нет, единственная строка этого файла должна содержать текст ’No’.  Если путь найден, первая строка файла должна содержать текст ’Yes’, а вторая – номера всех вершин (включая начальную и конечную), через которые проходит найденный путь. Числа в этой строке должны разделяться одним или несколькими пробелами.
Ограничения на время выполнения: 20 секунд на тест (компьютер класса Celeron-315, 1 Gb RAM)
Примеры входных данных Примеры выходных данных


 
MBo ©   (2006-12-14 06:42) [1]

Человеку, который знаком с термином "граф", должны быть известны и фразы "поиск в ширину", "алгоритм Дейкстры", "алгоритм Флойда"


 
iZEN ©   (2006-12-14 07:49) [2]

шаблонное решение


 
boriskb ©   (2006-12-14 08:09) [3]

MBo ©   (14.12.06 6:42) [1]
Человеку, который знаком с термином "граф", должны быть известны и фразы "поиск в ширину", "алгоритм Дейкстры", "алгоритм Флойда"


:))
Мне вот известно слово "автомобиль". Известны так же слова "карбюратор", "коробка передач", но это ни коим образом не помогает мне в моем абсолютном неумении чинить автомобиль :)


 
Alx2 ©   (2006-12-14 08:39) [4]

>boriskb ©   (14.12.06 08:09)

Простительно, так как при всем этом не автослесарь. :)

"Аксакалы, в ваши времена душманы не минировали дорог" (с) анекдот.


 
MBo ©   (2006-12-14 09:46) [5]

>boriskb ©   (14.12.06 08:09) [3]
Есть ведь элементарные вещи, которые непосредственно связаны с каждым понятием.
Если кто-то хоть чуть знаком с автомобилем, то понимает, что если он не заводится, то нужно проыерить, есть ли бензин, проверить аккумулятор, дверками хлопнуть ;)
Любой, кто имеет дело с массивами, знает, что такое их индексация, умеет обойти массив в цикле
Вот и для графов есть базовые понятия - вершина, ребро(дуга), связанные вершины, и, конечно, обходы графа.


 
pasha_golub ©   (2006-12-14 10:12) [6]

Лабораторная задача. Решается влоб методом, описанным в методичке.


 
boriskb ©   (2006-12-14 10:20) [7]

MBo ©   (14.12.06 9:46) [5]
дверками хлопнуть ;)


Да хлопал я!!
И по балону пинал.
Не заводится :((



Страницы: 1 вся ветка

Форум: "Прочее";
Текущий архив: 2006.12.31;
Скачать: [xml.tar.bz2];

Наверх




Память: 0.46 MB
Время: 0.038 c
15-1165523519
XsID
2006-12-07 23:31
2006.12.31
Перфокарта


15-1165500303
Караед
2006-12-07 17:05
2006.12.31
ПОМОГИТЕ РАЗОБРАТЬСЯ С ЗАДАЧЕЙ


2-1166128855
Кролик
2006-12-14 23:40
2006.12.31
Поиск по dll


2-1165871607
MegaNop
2006-12-12 00:13
2006.12.31
ActionMainMenuBar


2-1165821434
makvell
2006-12-11 10:17
2006.12.31
справочная система





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский