Задача 19.
Вводится N - количество домов и К - количество дорог. Дома пронумерованы от 1 до N. Каждая дорога определяется тройкой чисел - двумя номерами домов - концов дороги и длиной дороги. В каждом доме
живет по одному человеку. Найти точку - место встречи всех людей, от которой суммарное расстояние до всех домов будет минимальным.
Если точка лежит на доpоге, то указать номера домов - концов этой доpоги и расстояние от первого из этих домов. Если точка совпадает с домом, то указать номер этого дома.
Примечание: длины дорог - положительные целые числа.
|
Решение задачи 19.
Предположим, что мы нашли точку встречи z, и пусть она лежит на дороге (u,v) длины l на расстоянии d>0 от дома u и на расстоянии (l-d)>0 от дома v. Все множество домов разделим на два непересекающихся подмножества V и U. В подмножество U входят те дома, расстояние от которых до дома v меньше, чем расстояние до дома u. Все остальные дома отнесем к подмножеству U.
Пусть B подмножестве V домов Kv, а в U - Ku, и пусть Kv>Ku.
Обозначим суммарное расстояние от точки z (находящейся на расстоянии d от дома u) до всех N домов через R(z,d). Очевидно, что
R(z,d)= сумма расстояний от v до домов множества V + сумма расстояний от u до домов множества U + Ku*d + Kv*(L-d).
Если мы сдвинем z на расстояние p, p<(L-d) по направлению к дому v, то
R(z,d+p)=R(z,d)+Ku*p+Kv*(-p)=R(z,d)+(Ku-Kv)p<R(z,d) ?!
т.е. первоначальная установка точки z была неверной. Случай Kv<Ku рассматривается аналогично. Если же Kv=Ku, то точка z может быть на дороге в любом месте, в том числе и в концевых домах.
Итак, из всего выше сказанного следует, что искомая точка совпадает с одним из N домов, и что нам достаточно для каждого из домов i вычислить (например, по алгоритму Дейкстры) кратчайшее расстояние от него до каждого из оставшихся домов, затем найти сумму этих кратчайших расстояний (т.е. минимальное суммарное расстояние до всех домов от i). Минимальное из суммарных расстояний по всем i и даст решение задачи.
|
