Задача на граф

[kopzone]

Задали решить задачку но чет туплю..а времени в обрез.. если кто поможет буду признателен..обязательные параметры (Delphi)з.ы. не силен.
Задачка:
Имеется n филиалов организации, связанных вычислительной сетью (см. рис.). Стоимость передачи информации по сети зависит от расстояния, на которое необ-ходимо переслать информацию. Определите филиал для размещения сервера ба-зы данных, который располагается на расстоянии, не превышающем L км от наи-большего количества филиалов.

Вот так выглядит граф
Формат входных данных:
Предусмотреть ввод L с клавиатуры, матрица смежности вводится из файла
Пример файла входных данных
0 70 0 0 0 80 0 0
70 0 50 0 0 0 0 0
0 50 0 40 0 0 0 0
0 0 40 0 10 0 0 0
0 0 0 10 0 20 0 0
80 0 0 0 20 0 30 0
0 0 0 0 0 30 0 110
0 0 0 0 0 0 110 0
Пример выходных данных при L=50км
5

к сведению эта задача была на облостной олимпиаде..в 1995 году(( жалко там не выложили решения

From Stilet: Тему нужно называть так чтоб было не стыдно ее читать. В следующий раз удалю

[zetrix]

Так это ж обычная матрица ценности. Типичная задачка. Решается рекурсивным методом для каждого узла. От него рассматриваются все маршруты. Переходим от одного узла к другому, исключая те узлы, через которые мы прошли. Условием прекращения рекурсии: нет узлов, через которые можно пройти.
В итоге для каждого узла находим длины путей удовлетворяющих исловию (меньше Л). Заносим в массив кол-во узлов удовлетворяющих условию. Затем находим максимальное значение в получившемся массиве.
Сейчас посмотрю... Подобную задачку делали на парах на 2 курсе...
------ спустя 40 минут ------
Надо же, нашёл)
В программе задача: найти кратчайший путь из одного города в другой. В самом начале задаются города и расстояния между ними. Как наработка сойдёт. Для вашей задачи придётся переделать.

Да кстати, задавать города лучше смотря на рисунок, иначе можно запутаться. Я старался сделать как можно подробнее программу.

[pu4koff]

а тут разве не просто пройти по строкам и для каждой строки подсчитать количество элементов > L и ищем среди этих значений максимум

[zetrix]

нет не проще.
Ведь возможна ситуация, когда допустим филиалы 1,2,3,4 образуют цепочку, суммарной длинной < L и в итоге вариант с этой цепочкой может быть оптимальным. По строкам вы вообще не выйдите на такой вариант.

[kopzone]

Я пробовал численнымми методами..Метод нахождения остова минимального веса в звешеном графе.. там по сути алгоритм схожий..но как то он не пошел.. Спасиб за помщь.. щаз гляну попробую разобораться

[pu4koff]

Сообщение от zetrix

нет не проще.
Ведь возможна ситуация, когда допустим филиалы 1,2,3,4 образуют цепочку, суммарной длинной < L и в итоге вариант с этой цепочкой может быть оптимальным. По строкам вы вообще не выйдите на такой вариант.

действительно. извиняюсь. об этом как-то не подумал я