Написання програм CLOCK, POLICE і WATER (Задачі XI Всеукраїнської олімпіади з інформатики та рекомендації по їх розв’язанню), страница 2

Відстань до самого дальнього об’єкта – це максимум функцій y_ijk(x) по всім k: z_ij(x) = max {y_ijk(x)}. Для того, щоб знайти  оптимальне розташування підрозділу на дорозі між об’єктами i та j, треба знайти таке х, при якому досягається мінімальне значення функції z_ij(x). Після знаходження оптимального розташування на всіх дорогах, виберемо ту дорогу, на якій досягається мінімальна відстань до найвіддаленішого об’єкту.

Розглянемо алгоритм знаходження розв’язку.

Нехай P - матриця доріг між об’єктами (P_ij = ¥ коли між об’єктами i та j немає дороги).

1)  Знайти матрицю найкоротших шляхів. За умовою задачі між всіма об’єктами існує шлях, тому всі елементи цієї матриці будуть скінчені.

2) 

Для всіх i, j таких, що P_ij > 0 знайдемо мінімум функції z_ij(x). Графік функції у_ijk(x) являє собою “кут” (див. малюнок). Графік функції z_ij(x) є “ламана”, верхня огинаюча сімейства функцій у_ijk(x) (a_k = d_ik- відстань від об’єкта i до об’єкта k, b_k = d_jk - відстань від об’єкта j до об’єкта k). Знайдемо мінімум функції z_ij(x), перебираючи всі точки згину ламаної. Ці точки отримаємо наступним чином:

a)  Знаходимо максимальне нерозглянуте раніше a_k та відповідне  b_k. Отримаємо x: x = (d_ij-a_k+b_k)/2, z_ij(x) = y_ijk(x).

b)  Знаходимо максимальне після а_k а_l, що b_l > b_k. Отримаємо чергову точку:

dij

dij

x = (d_ij-a_l+b_k)/2, z_ij(x) = y_ijl(x). Якщо неможна знайти таке а_l , припиняємо пошук мінімуму.

c)  Наступна точка - перетин прямих x+a_l і d_ij+b_l-x: x = (d_ij-a_l+b_l)/2, z_ij(x) = y_ijl(x).

d)  k=l. Перехід до пункту b.

3)  В результаті перегляду всіх доріг виберемо ту дорогу, на якій значення функції z_ij(x) при оптимальному x буде мінімальним.

Водопровід

Місто складається з N районів (1 £ N £ 100). Кожен район має свердловину для отримання води. Кожні дві свердловини з’єднані між собою трубою. По кожній трубі вода може текти тільки в одному напрямку. Внаслідок енергетичної кризи в кожен момент часу працює тільки одна свердловина.  Оскільки система проектувалася без передбачення такого режиму роботи, деякі райони міста інколи залишаються без води.

Завдання. Напишіть програму WATER.*, яка визначить чи можна, змінивши напрямок проходження води по трубах, що приєднані до однієї із свердловин, добитись безперервного водопостачання в місті.

Вхідні дані. В першому рядку файлу WATER.DAT знаходиться число N – кількість районів (свердловин) в місті. В наступних N рядках для кожної свердловини вказуються кількість та номери свердловин, з яких до неї надходить вода. Свердловини мають номери від 1 до N.

Вихідні дані. В єдиному рядку файлу WATER.SOL має бути одне число – номер шуканої свердловини, якщо така існує, або 0 в іншому випадку.

Приклад введення і виведення.

WATER.DAT	WATER.SOL
4	2
0
1 1
2 1 2
3 1 2 3