Дистанционные семинары




Скачать 0.69 Mb.
страница 5/7
Дата 31.08.2016
Размер 0.69 Mb.
1   2   3   4   5   6   7

Формат выходных данных
Вывести искомое максимальное кратчайшее расстояние.

Пример

input.txt

output.txt

4

0 5 9 -1


-1 0 2 8

-1 -1 0 7

4 -1 -1 0


16

Применим алгоритм Флойда...

Задача 07-3. Флойд - существование.




Имя входного файла

input.txt

Имя выходного файла

output.txt

Максимальное время работы на одном тесте:

5 секунд

Дан ориентированный взвешенный граф. По его матрице смежности нужно для каждой пары вершин определить, существует кратчайший путь между ними или нет.

Комментарий:
Кратчайший путь может не существовать по двум причинам:

  • Нет ни одного пути

  • Есть путь сколь угодно маленького веса

Формат входных данных
В первой строке входного файла записано единственное число N (1 <= N <= 100) - количество вершин графа. В следующих N строках по N чисел - матрица смежности графа (j-ое число в i-ой строке соответствует весу ребра из вершины i в вершину j), в которой число 0 обозначает отсутствие ребра, а любое другое число - наличие ребра соответствующего веса. Все числа по модулю не превышают 100.

Формат выходных данных
Выведите N строк по N чисел: j-ое число в i-ой строке должно быть равно 0, если путь из i в j не существует, 1 - если существует кратчайший путь, и 2 - если существует путь сколь угодно маленького веса.

Пример

input.txt

output.txt

5

0 1 2 0 0

1 0 3 0 0

2 3 0 0 0

0 0 0 0 -1

0 0 0 -1 0



1 1 1 0 0

1 1 1 0 0

1 1 1 0 0

0 0 0 2 2

0 0 0 2 2


Применим алгоритм Флойда...

В этой задаче есть ряд подводных камней.

Во-первых, в математике бесконечность обладает интереснным свойством - сколько к ней ни прибавляй (или отнимай) числа, она остается бесконечностью. Большие числа, которые мы используем в программе, этим свойством не обладают, поэтому его необходимо добавить искусственно. Просто будем считать все числа, больше либо равные половине "бесконечности", просто равными "бесконечности"

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



  • произойдет переполнение типа (при данных ограничения вес цикла может достигать -1040 (это легко проверить экспериментально))

  • вес цикла станет по абсолютной величине больше "бесконечности"

Всех этих проблем можно избежать, если использовать тип с плавающей точкой (double или extended), а в качестве бесконечности взять что-нибудь вроде 101000.
Занятие 8. Графы.

Поиск кратчайшего пути.

Алгоритм Форда-Беллмана.

Пусть дан взвешенный ориентированный граф с N вершинами и M ребрами. Требуется найти кратчайшие расстояния от данной вершины s до всех остальных. Эта задача может быть решена с помощью алгоритма Форда-Беллмана.

В основе алгоритма Форда-Беллмана лежит метод динамического программирования. Пусть wi,j - длина дуги из вершины i в вершину j или бесконечность, если такой дуги нет. Пусть An,m - длина кратчайшего пути из начальной вершины в вершину m, проходящего не более чем по n ребрам. Пусть k - предыдущая вершина в этом пути. Тогда An,m=An-1,k + wk,m. Значит An,m = min(An-1,m, min{1<=i<=N}(An-1,i+wi,m)) (*).

Значения A0,i равны бесконечности для всех i, отличных от s, A0,s=0.

Будем считать Ai,j в порядке неуменьшения i, а при равных i - в порядке увеличения j. Тогда для вычисления i-й строки матрицы A нам необходимо знать только i-1-ую ее строку. Ответом на нашу задачу является N-я строка, значит, на каждом шаге можно хранить только предыдущую строку матрицы.

При такой реализации алгоритм будет выполнять порядка N3 операций.

Заметим, что при вычислении следующей строки матрицы по предыдущей каждую дугу графа мы рассмотрели ровно 1 раз. Воспользуемся этим, чтобы немного ускорить наш алгоритм. Пусть у нас известна n-1 строка матрицы A. Скопируем ее в n-ую строку. Далее рассмотрим все дуги нашего графа (x,y) и изменим An,y согласно формуле: An,y = min(An,y,An-1,x+wx,y) (**). Теперь у нас посчитана n-я строка матрицы A.

При такой реализации алгоритм выполнит порядка NM действий.



Восстановление пути
Пусть в формуле (*) в ходе работы алгоритма Форда-Беллмана минимум достигается при i=k или в формуле (**) на дуге (m,k). Тогда запишем в dm значение k. В конце работы алгоритма мы получим, что для каждой вершины i в di хранится номер предыдущей вершины в кратчайшем пути от s до i. По массиву d легко восстановить путь.

Нахождение вершин, до которых существует сколь угодно короткий путь
Сравним an,i и a2n,i. Если an,i > a2n,i, то до вершины i существует сколь угодно короткий путь. Иначе - нет.
Задача 08-1. Форд-Беллман


Имя входного файла

input.txt

Имя выходного файла

output.txt

Максимальное время работы на одном тесте:

5 секунд

Дан ориентированный граф, в котором могут быть кратные ребра и петли. Каждое ребро имеет вес, выражающийся целым числом (возможно, отрицательным). Гарантируется, что циклы отрицательного веса отсутствуют.

Требуется посчитать длины кратчайших путей от вершины номер 1 до всех остальных вершин.



Формат входных данных
Во входном файле записано сначала число N (1 <= N <= 100) - количество вершин графа, далее идет число M (0 <= M <= 10000) - количество ребер. Далее идет M троек чисел, описывающих ребра: начало ребра, конец ребра и вес (вес - целое число от -100 до 100).

Формат выходных данных
В выходной файл выведите N чисел - расстояния от вершины номер 1 до всех вешин графа. Если пути до соответствующей вершины не существует, вместо длины пути выведите число 30000.

Пример

input.txt

output.txt

4 5

1 2 10


2 3 10

1 3 100


3 1 -10

2 3 1


0 10 11 30000

Задача 08-2. Лабиринт знаний



Имя входного файла

input.txt

Имя выходного файла

output.txt

Максимальное время работы на одном тесте:

5 секунд

В Летней Компьютерной Школе (ЛКШ) построили аттракцион "Лабиринт знаний". Лабиринт представляет собой N комнат, занумерованных от 1 до N, между некоторыми из которых есть двери. Когда человек проходит через дверь, показатель его знаний изменяется на определенную величину, фиксированную для данной двери. Вход в лабиринт находится в комнате 1, выход - в комнате N. Каждый ученик проходит лабиринт ровно один раз и попадает в ту или иную учебную группу в зависимости от количества набранных знаний (при входе в лабиринт этот показатель равен нулю). Ваша задача показать наилучший результат.

Формат входных данных
Первая строка входного файла содержит целые числа N (1 <= N <= 2000) - количество комнат и M (1 <= M <= 10000) - количество дверей. В каждой из следующих M строк содержится описание двери - номера комнат, из которой она ведет и в которую она ведет (через дверь можно ходить только в одном направлении), а также целое число, которое прибавляется к количеству знаний при прохождении через дверь (это число по модулю не превышает 10000). Двери могут вести из комнаты в нее саму, между двумя комнатами может быть более одной двери.

Формат выходных данных
В выходной файл выведите ":)" - если можно получить неограниченно большой запас знаний, ":(" - если лабиринт пройти нельзя, и максимальное количество набранных знаний в противном случае.

Пример

input.txt

output.txt

2 2

1 2 5


1 2 -5

5

Задача 08-3. Цикл



Имя входного файла

input.txt

Имя выходного файла

output.txt

Максимальное время работы на одном тесте:

5 секунд

Дан граф. Определить, есть ли в нем цикл отрицательного веса, и если да, то вывести его.

Формат входных данных
Во входном файле в первой строке записано число N (1 <= N <= 100) - количество вершин графа. В следующих N строках находится по N чисел - матрица смежности графа. Веса ребер не превышают по модулю 10000. Если ребра нет, соответствующее значение равно 100000.

Формат выходных данных
В первой строке выходного файла выведите "YES", если цикл существует, или "NO" в противном случае. При наличии цикла выведите во второй строке количество вершин в нем (считая одинаковые первую и последнюю) и в третьей строке - вершины, входящие в этот цикл в порядке обхода. Если циклов несколько - выведите любой.

Пример

input.txt

output.txt

2

0 -1


-1 0

YES

3

1 2 1



С помощью алгоритма Форда-Беллмана найдем n-ю и 2n-ю строки матрицы и массив d. Сравним an,i с a2n,i. Если они не равны, то выведем с помощью массива d цикл отрицательного веса (в d для вершин этого цикла будут записаны как раз предыдущие в нем). В этой задаче удобно считать, что бесконечности тоже уменьшаются.
Занятие 9. Графы.

Каркас.

Алгоритмы Прима и Краскала.

Пусть дан взвешенный неориентированный связный граф с N вершинами и M ребрами.

Введем несколько определений:
Остовное дерево или каркас графа - подграф графа, который:
  1) содержит все вершины графа,
  2) является деревом.

Компонента связности - это такой связный подграф нашего графа, что добавление любой вершины ведет к потере связности.

Требуется найти каркас минимального вес для заданного графа.



Алгоритм Краскала

Удалим все ребра из нашего графа. Теперь отсортируем их по неубыванию весов и будем по очереди пытаться добавить их в наш граф. Если в результате добавления ребра образуется цикл, то добавлять это ребро не будем, иначе добавим его. При добавлении ребра в граф цикл образуется тогда и только тогда, когда вершины, которые соединяет ребро, находятся в одной компоненте связности. В результате у нас получится минимальное остовное дерево.



Алгоритм Прима

На каждом шаге алгоритма Прима есть множество помеченных вершин. Вначале оно состоит из одной произвольной вершины. Шаг алгоритма представляет собой следующую последовательнность действий:



  • Среди всех ребер, соединяющих помеченную и непомеченную вершины, выберем ребро с минимальным весом.

  • Добавим это ребро в каркас; вершину, являющуюся непомеченным концом данного ребра, добавим в множество помеченных вершин.

В результате у нас получится минимальное остовное дерево.
Задача 09-1. Дерево?

Имя входного файла

input.txt

Имя выходного файла

output.txt

Максимальное время работы на одном тесте:

5 секунд

Неориентированный граф без петель и кратных ребер задан матрицей смежности. Определить, является ли этот граф деревом.

Формат входных данных
Во входном файле записано сначала число N - количество вершин графа (от 1 до 100). Далее записана матрица смежности размером N*N, в которой 1 обозначает наличие ребра, 0 - его отсутствие. Матрица симметрична относительно главной диагонали.

Формат выходных данных
В выходной файл выведите сообщение YES, если граф является деревом, и NO в противном случае

Пример

input.txt

output.txt

0 1 0

1 0 1


0 1 0

YES

Воспользуемся вспомогательным утверждением: связный граф является деревом тогда и только тогда, когда ребер в нем на одно меньше, чем вершин.

Задача 09-2. Получи дерево



Имя входного файла

input.txt

Имя выходного файла

output.txt

Максимальное время работы на одном тесте:

5 секунд

Дан связный неориентированный граф без петель и кратных ребер. Разрешается удалять из него ребра. Требуется получить дерево.

Формат входных данных
Во входном файле задады два числа - N (от 1 до 100) и M - количество вершин и ребер графа соответственно. Далее идет M пар чисел, задающих ребра. Гарантируется, что граф связный.

Формат выходных данных
В выходной файл выведите N-1 пару чисел - ребра, которые войдут в дерево. Ребра можно выводить в любом порядке.

Пример

input.txt

output.txt

4 4

1 2


2 3

3 4


4 1

1 2

2 3


3 4

Существует огромное количество способов решить эту задачу. Опишем один их наиболее быстрых. Обойдем наш граф в ширину из произвольной вершины. Далее для каждой вершины, кроме начальной выведем последнее ребро в кратчайшем пути от начальной вершины до нее. Полученное дерево называется деревом обхода в ширину.

Задача 09-3. Каркас-разминка 1



Имя входного файла

input.txt

Имя выходного файла

output.txt

Максимальное время работы на одном тесте:

5 секунд

Формат входных данных
Во входном файле записано сначала число N (1 <= N <= 100), а затем N чисел от 1 до 100 - элементы массива A[i]. Далее записаны два числа q и w (от 1 до N, не обязательно различные).

Требуется все элементы, которые равны A[q], сделать равными A[w]. Постарайтесь сначала считать данные, потом сделать то, что требуется, и только потом вывести результат (а не делать преобразование на этапе вывода). Постарайтесь не пользоваться допoлнительными массивами.



Формат выходных данных
В выходной файл выведите N чисел - элементы массива A[i] после преобразования.

Пример

input.txt

output.txt

5

1 4 2 2 5

3 2


1 4 4 4 5

В алгоритме Краскала компоненты связности удобно обозначать числами, а для каждой вершины писать, к какой компоненте связности она относится. Таким образом, данная задача представляет собой перепометку компонент связности после добавления очередного ребра.

Задача 09-4. Каркас-разминка 2



Имя входного файла

input.txt

Имя выходного файла

output.txt

Максимальное время работы на одном тесте:

5 секунд

Формат входных данных
Во входном файле задано число N (от 2 до 100) и матрица смежности полного неориентированного взвешенного графа (полный граф - граф, в котором есть ребра между всеми парами вершин). Все веса ребер - натуральные числа от 1 до 1000. Далее дано N чисел, каждое из которых либо 0, либо 1 - считается, что эти числа записаны в вершинах. Гарантируется, что есть хотя бы один 0 и хотя бы одна 1.

Формат выходных данных
Найдите и выведите в выходной файл такие две вершины, что:

  • в первой из них стоит 0

  • во второй из них стоит 1

  • вес ребра между этими вершинами минимально возможный.

Если таких пар несколько, выведите любую из них.

Пример

input.txt

output.txt

3

0 1 2


1 0 4

2 4 0


1 0 0

2 1

Решение задачи представляет собой реализацию первой части шага алгоритма Прима
Задача 09-5. Минимальный каркас

Имя входного файла

input.txt

Имя выходного файла

output.txt

Максимальное время работы на одном тесте:

5 секунд

От вас требуется определить вес минимального остовного дерева для неориентированного взвешенного связного графа.

Формат входных данных
В первой строке входного файла находятся числа N и M (1 <= N <= 100; 1 <= M <= 6000), где N - количество вершин в графе, а M - количество рёбер. В каждой из последующих M строк записано по тройке чисел A, B, C, где A и B - номера вершин, соединённых ребром, а C - вес ребра (натуральное число, не превышающее 30000)

Формат выходных данных
Вывести одно число - искомый вес.

Пример

input.txt

output.txt

3 3

1 2 1


2 3 2

3 1 3


3

Воспользуемся алгоритмом Прима или алгоритмом Краскала.
Занятие 10. Длинная арифметика.
В задачах, рассмотренных на предыдущих занятиях, для хранения чисел мы использовали стандартные типы данных, такие как integer и longint. С помощью этих типов данных можно хранить только относительно небольшие числа. Тем не менее компьютер предназначен для проведения громоздких вычислений. Что же делать, если в задаче необходимо оперировать, к примеру, 100-значными числами?

Во-первых, "большие" числа нужно как-то хранить в памяти компьютера. Вспомним, как мы записываем числа на бумаге. Мы ведь не пишем специальный символ для каждого числа, а представляем его в виде последовательности цифр. Этот способ можно использовать и в программе: запишем число в виде массива его цифр. Так как в результате арифметических операций "длина" числа может измениться, удобно записать цифры в обратном порядке. Например, чтобы представить число 1024, первому элементу массива присвоим 4, второму - 2, третьему - 0, четвертому - 1, а остальным - ноль. Таким образом, мы получили число с некоторым количеством незначащих лидируюущих нулей, записанное в перевернутом виде .

Операции сложения, умножения, вычитания и деления тоже производятся как на бумаге: "в столбик".

Приведем несколько идей, как ускорить работу арифметических операций с длинными числами:



  • нам совершенно не обязательно каждый раз просматривать массив целиком, ведь с некоторого момента там будут идти одни нули. Чтобы учесть это, для каждого числа будем хранить его "длину". Тогда, например, при сложении двух n-значных чисел, длина результата не может быть больше (n+1).

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

Задача 10-1. A+B



Имя входного файла

input.txt

Имя выходного файла

output.txt

Максимальное время работы на одном тесте:

1 секунда

Даны два целых неотрицательных числа A и B. Требуется найти их сумму.

Формат входных данных
Во входном файле записаны целые неотрицательные числа A и B по одному в строке (A,B < 10100).
1   2   3   4   5   6   7


База данных защищена авторским правом ©infoeto.ru 2022
обратиться к администрации
Как написать курсовую работу | Как написать хороший реферат
    Главная страница