Форум: "Прочее";
Текущий архив: 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