Вам бонус- начислено 1 монета за дневную активность. Сейчас у вас 1 монета

Network(решение через графы)

Лекция



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

NEERC, Северный четвертьфинал, 2001.

Задание

Андрей работает системным администратором и планирует создание новой сети в своей компании. Всего будет N хабов, они будут соединены друг с другом с помощью кабелей.

Поскольку каждый сотрудник компании должен иметь доступ ко всей сети, каждый хаб должен быть достижим от любого другого хаба — возможно, через несколько промежуточных хабов. Поскольку имеются кабели различных типов и короткие кабели дешевле, требуется сделать такой план сети (соединения хабов), чтобы максимальная длина одного кабеля была как можно меньшей. Есть еще одна проблема — не каждую пару хабов можно непосредственно соединять по причине проблем совместимости и геометрических ограничений здания. Андрей снабдит вас всей необходимой информацией о возможных соединениях хабов.

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

Ввод

Первая строка входного файла содержит два целых числа: N — количество хабов в сети ( 2 <= N <= 1000) и М — количество возможных соединений хабов (1 <= M <= 15 000).

Все хабы пронумерованы от 1 до N Следующие М строк содержат информацию о возможных соединениях — номера двух хабов, которые могут быть соединены, и длина кабеля, который требуется, чтобы соединить их. Об этом говорит сайт https://intellect.icu . Эта длина — натуральное число, не превышающее 106. Существует не более одного способа соединить каждую пару хабов. Хаб не может быть присоединен сам к себе. Всегда существует хотя бы один способ соединить все хабы.

Вывод

Сначала выведите максимальную длину одного кабеля в вашем плане соединений (это величина, которую вы должны минимизировать). Затем выведите свой план: сначала выведите Р — количество кабелей, которые вы использовали, затем выведите Р пар целых чисел — номера хабов, непосредственно соединенных в вашем плане кабелями.

Пример ввода         Пример вывода
4 6                   1
1 2 1                 3
1 3 1                 1 2
1 4 2                 1 3
2 3 1                 3 4
3 4 1                 
2 4 1

Решение    

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

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

Формальное описание      

Network()
1. Считать из файла список ребер графа.
2. Отсортировать ребра графа по возрастанию их веса (цены трубы).
3. Использовать алгоритм Крускаля для нахождения наименьшего остового 
   дерева (выполнить пп. 3.1-3.4):
   3.1. Инициализировать значение количества кабелей нулем.
   3.2. Выбрать первое ребро графа в списке.
   3.3. Пока не просмотрены все ребра графа, повторять пп. 3.3.1-3.3.3:
        3.3.1. Если вершины текущего ребра не лежат в одной компоненте 
               связности, то добавить ребро в наименьшее остовое дерево.
        3.3.2. Если ребро было добавлено, то увеличить количество 
               кабелей на 1.
        3.3.3. Перейти к сведущему ребру.
   3.4. Считать длину последнего добавленного ребра максимальной длиной
        кабеля.
4. Вывести количество использованных кабелей и максимальную длину кабеля.
5. Вывести все ребра, которые принадлежат минимальному остовому дереву.

 
Начальная сеть и полученное из нее остовое дерево наименьшей длины.
Последнее добавленное ребро ([8;9], длина 11) - это самое длинный кабель в построенной сети.

 

На этом все! Теперь вы знаете все про network решение через графы , Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое network решение через графы и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Алгоритмы и теория алгоритмов

Из статьи мы узнали кратко, но содержательно про network решение через графы
создано: 2014-10-13
обновлено: 2021-03-13
132566



Рейтиг 9 of 10. count vote: 2
Вы довольны ?:


Найди готовое или заработай

С нашими удобными сервисами без комиссии*

Как это работает? | Узнать цену?

Найти исполнителя
$0 / весь год.
  • У вас есть задание, но нет времени его делать
  • Вы хотите найти профессионала для выплнения задания
  • Возможно примерение функции гаранта на сделку
  • Приорететная поддержка
  • идеально подходит для студентов, у которых нет времени для решения заданий
Готовое решение
$0 / весь год.
  • Вы можите продать(исполнителем) или купить(заказчиком) готовое решение
  • Вам предоставят готовое решение
  • Будет предоставлено в минимальные сроки т.к. задание уже готовое
  • Вы получите базовую гарантию 8 дней
  • Вы можете заработать на материалах
  • подходит как для студентов так и для преподавателей
Я исполнитель
$0 / весь год.
  • Вы профессионал своего дела
  • У вас есть опыт и желание зарабатывать
  • Вы хотите помочь в решении задач или написании работ
  • Возможно примерение функции гаранта на сделку
  • подходит для опытных студентов так и для преподавателей



Комментарии


Оставить комментарий
Если у вас есть какое-либо предложение, идея, благодарность или комментарий, не стесняйтесь писать. Мы очень ценим отзывы и рады услышать ваше мнение.
To reply

Алгоритмы и теория алгоритмов

Термины: Алгоритмы и теория алгоритмов