Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиКалендарьОблакоЗаметкиВсе проекты

Кто может разъяснить формулировку задачи простыми словами?

Viridi Знаток (497), закрыт 4 года назад
Надо написать программу, но не могу понять задачу. Задача о размещении бензоколонок. Дан взвешенный граф. Найти такое минимальное подмножество вершин S, чтобы любая вершина графа была бы на расстоянии, меньшем заданного числа, от ближайшей вершины из S. Что такое взвешенный граф я знаю.
Лучший ответ
Noname Гений (69519) 4 года назад
Для начала каким-нибудь образом выберем из графа некоторое количество вершин. Все вершины, что мы выбрали, назовем "набор вершин S" (ну или подмножество, мне удобнее набор).
Теперь рассмотрим все оставшиеся вершины, которые мы не выбрали.
Возьмем из всех не выбранных нами вершин первую. Назовем ее вершина A1. Теперь найдем из нашего набора S вершину, которая будет находится ближе всех к вершине А1. Найдем расстояние от этой самой близкой вершины до вершины А1. Запишем это расстояние в переменную M1.
Теперь возьмем из всех не выбранных нами вершин вторую. Проделаем с ней то же самое. Получим расстояние M2.
И так далее, для 3й, 4й вершины, пока не переберем все вершины, которые мы не выбрали.
Получили набор расстояний M1,M2,M3,М4....
По условию еще было задано кое-какое число. Поместим его в переменную L. Так вот, если мы из нашего графа выбрали вершины правильным образом, должно должно оказаться так, что M1<L и M2<L и M3<L и M4<L и т. д.
Уж не знаю, как проще. Разве что рисунок рисовать... Надеюсь понятно объяснил.
ViridiЗнаток (497) 4 года назад
Спасибо! Вроде понял.
Остальные ответы
Похожие вопросы