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

Найпростіший метод розв’язку – послідовно змінювати напрямок проходження води біля кожної з свердловин і перевіряти, чи досяжні всі райони з усіх свердловин.

Перевірку можна виконувати двома методами:

1)  Безпосередньо перевірити (пошуком в глибину чи ширину) досяжність з кожної свердловини всіх інших. Перевірка має складність O(N³), а весь алгоритм - O(N⁴).

2)  Перевірити досяжність всіх вершин з деякої довільної та досяжність цієї вершини з усіх інших. Другу дію можна виконати пошуком по зворотнім ребрам. Цей метод краще і має складність O(N²), алгоритм - O(N³).

Однак існує метод розв’язку, що потребує тільки O(N²) часу.

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

Якщо компонент сильної зв’язності три або більше, то розв’язком задачі, в цьому не важко переконатись, буде довільна вершина передостанньої компоненти.

Якщо компоненти дві – підійде довільна вершина, з якої виходять та входять хоча б по дві вершини.

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

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

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

Задачі до олімпіади розроблялись невеликим колективом, з якого хотілось би виділити Павла Аксьонова, студента Київського Університету імені Тараса Шевченка, який підготував задачу “Охорона” та працював над задачею “Годинник”.

З питаннями, що стосуються XI Всеукраїнської олімпіади з інформатики, олімпіад минулих років, звертайтеся за адресою uoi@issep.freenet.kiev.ua (список розсилки українських олімпіад з інформатики) або безпосередньо до автора за адресою vitaly@tk.cyb.univ.kiev.ua.