Архив категории ‘Алгоритмы’

Задача «Secret Pipes». Пояснения

    На этом шаге рассмотрим пояснения к задаче "Secret Pipes".     В данной задаче мы можем рассматривать насосные станции как вершины; трубы, соединяющие насосные станции — как ребра, а стоимость труб — как веса ребер. Тогда по условию задачи от нас требуется построить второе по весу остовное дерево. Прежде всего опишем ввод исходных данных. procedure […]

Задача «Secret Pipes». Программная реализация

    На этом шаге рассмотрим программную реализацию задачи "Secret Pipes".     program pr; const  maxn = 2000;  maxp = 20000;  free = 0;  used = 1; var n : 1..maxn; p : 1..maxp; i, j : integer; pred, rank : array [1..maxn] of integer; b, e : array [1..maxp] of boolean; Key : array [1..max-1] […]

Задача «Secret Pipes»

    На этом шаге рассмотрим постановку задачи "Secret Pipes".     Фермер Джон хочет как можно дешевле организовать свою систему распределения воды, но он не хочет, чтобы его конкурент фермер Плуто мог предсказать маршруты, которые он выбирает. ФД знает, что такая задача обычно требует самого дешевого способа прокладки труб поэтому он решил использовать второй по стоимости […]

Быстрая сортировка

    Быстрая сортировка участка массива R от p до rr происходит следующим образом: Элементы массива R переставляются так, что бы любой из элементов R[p], ..., R[q] был не больше любого из элементов R[q+1], ..., R[rr]. Эта операция называется разделением (partition). Здесь q — некоторое число в интервале p ≤ q ≤ rr; Процедура сортировки рекурсивно […]

Алгоритм Крускала. Окончание

    На этом шаге рассмотрим работу алгоритма Крускала.     Алгоритм Крускала работает следующим образом: for i:=1 to N do Makeset(i);     Вначале строятся N (по числу вершин) непересекающихся множеств, каждое из которых хранит номера вершин, в него входящих (вначале каждое такое множество хранит только одну вершину — с номером вершины, соответствующим номеру множества).     Далее […]

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

    На этом шаге рассмотрим метод Крускала и его применение для решения ранее рассмотренной олимпиадной задачи.     Для решения многих олимпиадных задач удобнее применять метод Крускала. Рассмотрим вначале его применение в для решения задачи "Веревочный телеграф&qot;.     В тело главной программы внесено существенное изменение: begin InputData; QuickSortR(1,N * (N - 1) div 2); MinTree_Kruskal; OutputData; […]

Реализация алгоритма Прима

    На этом шаге рассмотрим реализацию поставленной на преыдущих шагах задачи.     Архив с примером можно взять здесь. program pr; Const MaxN = 100; var N, i, j : 1..MaxN; X, Y : array [1..MaxN] of longint; D : array [1..MaxN,1..MaxN] of single; Pred : array [1..MaxN] of byte; procedure InputData; var i, j : […]

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

    На этом шаге рассмотрим алгоритм Прима для решения поставленной задачи.     Идея алгоритма Прима заключается в следующем: пусть А — это множество ребер части остова, растущей от пустого множества ребер к минимальному остовному дереву. Формирование множества A может начинаться с произвольной вершины, называемой корневой. Для определенности в реализации в качестве корневой выбирается вершина 1. […]

Решение задачи на минимальное остовное дерево

    На этом шаге рассмотрим решение олимпиадной задачи, которая сводится к нахождению минимального остовного дерева.     В данной задаче удобно представлять граф в виде матрицы весов ребер: D[i,j] — расстояние между вершинами i и j. Ввод данных, обеспечивающий вычисление D[i,j] по исходным данным задачи, представлен ниже: procedure InputData; begin assign (input,'input.txt'); reset(input); readln(N); for i […]

Пример задачи на минимальное остовное дерево

    На этом шаге рассмотрим формулировку олимпиадной задачи, которая сводится к нахождению минимального остовного дерева.     Веревочный телеграф    Тимур и его друзья, приехав летом на свои старые дачи, решили устроить на время своего отдыха игру. Они организовали команду, чтобы тайно помогать жителям дачного городка в их повседневных делах.    Дачный поселок довольно большой, и дома, в […]