                        ЗАДАЧИ НА ГРАФАХ.

                            Задача 1.
     Для более   удобного   хранения  информации  заведем  матрицу
C[1...n,1..n]  (так  называемую  матрицу  смежности)   в   которой
C[i,j]=1, если в наборе есть пара (Ai,Aj) и C[i,j]=0 иначе.
     Будем строить  все  возможные цепочки (по правилу,  данному в
условии) и искать среди них ту, которая имеет максимальную длину.
     В качестве начального символа цепочки можно взять любой  сим-
вол из A. Пусть это символ Ai. Ищем, просматривая строку i матрицы
C слева направо элемент C[i,j]=1 (другими  словами,  ищем  пару  с
первым элементом Ai). Если такого элемента не существует, то берем
в качестве начала строки другой элемент множества A.  Если элемент
C[i,j]=1  найден,  то ему соответствует пара (Ai,Aj).  Помечаем ее
как  уже  использованную  полагая,  например,   C[i,j]=-1.   Далее
просматриваем  слева  направо  строку j матрицы C в поисках еще не
использованной пары (Aj,Ak) (C[j,k]=1).  Присоединяем элемент Ak к
имеющейся  цепочке,  полагаем C[j,k]=-1,  ищем единичный элемент в
строке k и т.д. Предположим, на некотором шаге мы получили цепочку
       Ai Aj Ak ... As Al Ap
и в строке p матрицы больше нет ни одного единичного элемента. Это
означает,  что  при  таком  подборе  предыдущих элементов мы нашли
максимальную по длине строку.  Если ее длина больше длин всех най-
денных ранее строк,  запоминаем эту строку как рекорд. После этого
"отщепляем" от строки последний элемент Ap и смотрим,  есть ли еще
в строке l единичный элемент с индексом,  большим p.  Если да,  то
приписываем уже этот элемент к строке и пытаемся затем снова  уве-
личить  длину  полученной строки,  если же нет,  то "отщепляем" от
строки элемент Al,  в строке S ищем единичный элемент с  индексом,
большим l и т.д.
     Останов осуществляется тогда,  когда мы должны "отщепить"  от
строки Ai.
     Перебираем цепочки,  начинающиеся со всех возможных элементов
множества A. Находим строку максимальной длины:
     const M=10;      { максимально число элементов в A }
           { будем считать, что A состоит из чисел от 1 до N }
     var c:array[1..M,1..M] of integer;
         curstr, maxstr: array[0..M] of integer;
           { в этих переменных хранятся текущая цепочка и }
           { цепочка максимальной длины. }
           { В нулевом элементе хранится длина цепочки }
         N,E : integer;   { N - число элементов в A }
         i,j,k : integer; { E - число пар в наборе }
     procedure find;
     var l,j : integer;
     begin
       l:=curstr[curstr[0]]; { l = последний элемент цепочки }
       for j:=1 to N do      { просмотр строки l }
         if C[l,j]=1
         then begin
                curstr[0]:=curstr[0]+1;
                curstr[curstr[0]]:=j;   { j -> в цепочку }
                c[l,j]:=-1;             { пара использована }
                find;
                c[l,j]:=1;     { пару снова разрешено }
                               {      использовать    }
                curstr[0]:=curstr[0]-1;
         end;
       if curstr[0]>maxstr[0]   { если нашли более }
       then maxstr:=curstr      {  длинную строку  }
     end;
     begin
       readln(N); readln(E);
       for i:=1 to N do
         for j:=1 to N do
           C[i,j]:=0;
       for k:=1 to E do begin
         write('очередная пара: ',i,j);
         c[i,j]:=1
       end;
       for i:=1 to N do begin
         curr[0]:=1;          { поиск цепочки }
         curr[1]:=i;     { начинающейся элементом i }
         find;
       end;
       for i:=1 to maxstr[0] do
         write(maxstr[i]);      { печать максимальной строки }
     end.

                          Задача 2.
     Для решения  задачи  важно понять,  что встреча роботов может
произойти либо в пункте,  либо на дороге.  В первом случае  задача
решается  просто:  необходимо  последовательно  строить  множества
пунктов для каждого робота,  в которых они могут  оказаться  через
время, равное 0.5,1,1.5,2,...Т. Это можно делать, используя очере-
ди.  В случае же встречи роботов на дороге легко понять,  что  не-
посредственно  перед встречей все они должны были находится в сле-
дующих пунктах:
     1. Либо в двух пунктах, связанных дорогой;
     2. Либо в пунктах,  из которых есть дороги в один  и  тот  же
пункт;
     3. Либо в трех пунктах, образующих треугольник.
     Поэтому, после каждого целого такта времени,  достаточно про-
верять,  находятся ли роботы в одной из описанных 3 ситуаций.  При
этом время подсчитывается очевидным способом.

                            Задача 3.
     Рассмотрим только  случай,  когда роботы двигаются только па-
раллельно координатным осям, в других случаях можно сделать преоб-
разование координат.
     Легко понять,  что если рассмотреть точку, имеющую наибольшую
координату  Y,  причем самую левую (т.е.  наименьшую координату Х,
если таких несколько),  то для нее существует только 2 возможность
быть пройденной роботом:  робот должен прийти из ближайшей точки А
снизу и пойти в ближайшую точку Б справа  или  наоборот.  В  любом
случае эти 2 отрезка фиксированы для робота.  Теперь те же рассуж-
дения можно провести и для точек Б и точки,  находящейся правее Б,
а также для самых нижних, левых и правых точек. Окончательно полу-
чается, что возможный проход робота строго фиксирован. Если упоря-
дочить  точки по горизонталям (вертикалям),  то первая точка гори-
зонтали (вертикали) должна соединятся со второй,  третья с четвер-
той и т.д. Понятно, что если получившаяся фигура связна (цикл), то
решение существует для случаев 2. и 3., а для случая 1. нужно про-
верить,  в  нужном  ли  направлении стоит робот.  Однако есть одна
трудность в случае,  когда существуют горизонталь и вертикаль, со-
держащие  нечетное число точек,  а обход существует.  Это возможно
только в случае,  когда это стартовая точка обхода, причем она на-
ходится  в  'нечетной' горизонтали и вертикали.  Удалив ее,  можно
воспользоваться предыдущей процедурой,  при этом фиксированные от-
резки не должны пересекаться в удаленной точке.

                          Задача 4.
     Для решения задачи достаточно воспользоваться алгоритмом  на-
хождения потока между двумя заданными вершинами, преобразуя в слу-
чае а) граф по следующему правилу:  каждую вершину исходного графа
превращаем в ребро с пропускной способностью 1.

                          Задача 5.
     Решается аналогично задаче 4.

                          Задача 6.
     Будем обозначать вращение по часовой стрелке нулем,  против -
единицей.  Сначала  припишем  шестерне с номером 1 число нуль.  На
следующем шаге всем шестерням, сцепленным с первой, будут приписа-
ны  числа 1 (они будут вращаться в противоположную шестерне 1 сто-
рону).  Далее всем шестерням, находящимся в зацеплении с занумеро-
ванными на предыдущем шаге, припишем значения 0 и и.т.д.
     Процесс будем повторять до тех пор,  пока либо  на  очередном
шаге ни одной шестерне не будет приписано новое значение,  и тогда
шестерню с номером 1  удастся  повернуть,  и  число  рассмотренных
шестеренок и есть искомое число пришедших в движение,  либо на ка-
ком-то шаге пометка шестерни изменяется с 1 на 0 или с 0 на  1,  и
тогда система в движение не придет.
     Перебирая сначала все возможные варианты выбрасывания по  од-
ной, затем, в случае неудачи по две, три, ... ,N-1 шестерни и про-
водя аналогичные рассуждения мы получаем максимальное число шесте-
рен,  которое  могло  бы прийти в движение.  О генерации вариантов
выбрасывания шестерен см. задачу 2 (перебор).

                            Задача 8.
     Можно сформировать  граф,  состоящий  из  2*N  вершин,  соот-
ветствующих открыткам и конвертам,  причем две  вершины  соединены
ребром, если одна соответствует открытке, а другая - конверту, при
этом соответствующая открытка входит  в  соответствующий  конверт.
Добавив в этом графе 2 новые вершины,  одна из которых смежна всем
вершинам,  соответствующим открыткам,  а другая -  всем  вершинам,
соответствующим  конвертам,  сведем  задачу  к  задаче  нахождения
максимального потока между этими вершинами.

                            Задача 9.
     Разбиение на группы осуществляется аналогично, как и в Задаче
10. за  тем исключением,  что в ситуации 3. организуются две новые
группы (пара групп,  одна из  них  может  оказаться  в  результате
пустой).  После  разбиения  всех  людей будем использовать принцип
формирования двух результирующих групп,  основываясь на идее реше-
ния Задачи 2 из главы "Сортировки", учитывая возможности об'едине-
ния двух пар групп в одну пару групп  произвольным  слиянием  двух
групп из различных пар.

                            Задача 10.
     Задача решается следующим  образом.  Выбирается  произвольный
человек  и помещается в первую группу.  Затем находятся люди,  ему
знакомые.  Понятно,  что они не могут находиться в первой  группе,
поэтому  их необходимо поместить во вторую.  Затем находятся люди,
знакомые людям из второй группы.  Понятно,  что они не могут нахо-
диться во второй группе, поэтому их необходимо поместить в первую.
Повторяя так поочередно для каждой из групп,  мы придем к одной из
ситуаций:
     1. Какой-то человек сначала был помещен в одну группу,  а по-
     том должен быть помещен в другую.  Понятно, что в этом случае
     задача не имеет решения.
     2. Каждый человек помещен в одну из групп.  В этом случае за-
     дача решена.
     3. Не  каждый человек помещен в одну из групп.  Это означает,
     что оставшиеся не помещенные в группы люди не знакомы людям в
     группах  (иначе  они были бы куда-нибудь помещены).  Следова-
     тельно,  одного из них безразлично куда помещать,  например в
     первую группу. Затем описанный выше процесс продолжается, по-
     ка не придем к ситуации 1. или 2.

                            Задача 11.
     Для решения задачи достаточно определить, является ли связным
граф,  определяемый матрицей смежности,  элементы  которой  а[i,j]
равны 1,  если люди с номерами i и j знакомы и равны 0 иначе. Граф
называется связным,  если существует путь между любыми парами  его
вершин.  Понятно,  что  путь между вершинами i и j в таком графе и
определяет  возможную  последовательность  знакомств,  позволяющих
познакомить людей с номерами i и j.
     Для определения связности графа можно воспользоваться методом
поиска в ширину, который состоит в следующем.
     На начальном этапе в очередь помещается  некоторая  начальная
вершина, например вершина с номером 1.
     На каждой из следующих итераций (пока очередь не  пуста)  вы-
полняются следующие действия:
   - извлекается вершина из очереди;
   - определяются  вершины,  ей смежные и которые в очереди еще не
были, и помещаются в очередь.
     Если в  результате таких действий все вершины побывали в оче-
реди (а для этого удобнее подсчитывать количество вершин,  там по-
бывавших), то граф связен, иначе не связен. Для маркировки вершин,
побывавших в очереди,  можно использовать массив размера N с  эле-
ментами 0 и 1.

                            Задача 12.
     Задача может быть сформулирована в графовой постановке следу-
ющим образом:  найти простой цикл в графе (т.е.  без повторяющихся
вершин), проходящий через все вершины графа. В общем случае не су-
ществует эффективного алгоритма решения этой задачи. Однако в дан-
ном случае задачу можно решить эффективно.
     Предположим, что  уже   построен   некоторый   простой   путь
(x[1],x[2],...x[k]) Множество вершин,  вошедших в путь, будем счи-
тать пройденными, остальные не пройденные. Возможны 3 ситуации.
     1. Одна из вершин x[1],x[k] смежна одной из не пройденных еще
вершин. В этом случае путь можно очевидным образом удлинить на од-
ну вершину.
     2. Ни одна из вершин x[1],x[k] не смежна одной из не пройден-
ных еще вершин, а вершины x[1] и x[k] смежны. В этом случае понят-
но,  что k>N/2,  так как вершины x[1] и x[k] смежны N/2  вершинам.
Следовательно количество не пройденных вершин не больше N/2.  Сле-
довательно любая вершина у из них смежна одной из пройденных  вер-
шин,  например  x[i].  Но  тогда можно получить более длинный путь
(у,x[i],x[i+1],...,x[k],x[1],x[2],...x[i-1]).
     3. В этом случае степеней вершин нетрудно показать, что в пу-
ти (x[1],x[2],...x[k]) существует такой индекс i,  что x[1] смежна
x[i],   а  x[i-1]  смежна  x[k].  Следовательно,  рассмотрев  путь
(x[i],x[i+1],...,x[k],x[i-1],x[i-2],...x[1]) мы имеем ситуацию 2.,
поэтому можно получить более длинный путь.
     Применяя описанный выше способ начиная с пути длины 1,  пост-
роим простой цикл, включающий все вершины.

                            Задача 13.
     В заданном  графе необходимо определить,  существует ли цикл,
проходящий по каждому ребру графа ровно один раз.
     Для существования  такого цикла необходимо и достаточно нали-
чия двух условий:
     1.  граф является связным;
     2. степень любой вершины графа четна.
Первое условие очевидно.  Второе следует из факта,  что если такой
цикл существует и заходит в некоторую вершину графа,  то он должен
и выйти из нее. Проверив эти условия (для проверки связности можно
воспользоваться алгоритмом для задачи 11).
     Предположим, что  некоторый цикл А (не обязательно проходящий
через все ребра графа) уже построен и  из  графа  выброшены  ребра
цикла  (их  можно просто отметить как пройденные).  Найдем вершину
(пусть это вершина к),  через которую этот цикл проходил, но кото-
рой инцидентны некоторые ребра (непройденные). Построим новый цикл
В, который начинается в вершине к, по следующему правилу.
     Находясь в  текущей  вершине  цикла ( вначале это вершина к),
находим непройденное еще ребро,  инцидентное текущей вершине.  Это
ребро и определяет новую текущую вершину цикла,  а ребро считается
пройденным.  Построение цикла В продолжается до тех пор,  пока это
возможно.  Легко понять, что это будет цикл, так как степень любой
вершины четна.  Предположим,  что построение  цикла  В  завершено.
Склеиваем теперь циклы А и В следующим образом.  Находим в цикле А
(последовательности вершин) вершину к и заменяем ее последователь-
ностью вершин цикла В.
     Такой процесс повторяется до тех пор, пока все ребра не будут
пройдены.  Описанный  процесс  можно  начинать  с  пустого цикла А
(пустой последовательности).

                            Задача 14.
     Так как сеть дорог определяет некоторый граф,  то определим в
этом графе множество вершин с нечетной степенью.  Понятно, что ко-
личество таких вершин четно (так как сумма степеней  вершин  графа
четна). Определим на этом множестве взвешенный граф (граф, на реб-
рах которого определены веса или расстояния) по следующему  прави-
лу.  Вес ребра (i,j) равен кратчайшему расстоянию между вершинами,
соответствующими i и j в исходном графе. Построим в этом графе со-
вершенное  сочетание минимального веса.  Паросочетанием называется
множество попарно несмежных ребер (не имеющих общих  вершин).  Па-
росочетание называется совершенным,  если оно покрывает все верши-
ны.  Весом паросочетания называется суммарный вес входящих в  него
ребер.  Существуют эффективные алгоритмы поиска совершенного соче-
тания минимального веса.  Однако они очень трудны. Поэтому при ма-
лом количестве вершин в графе можно воспользоваться перебором всех
возможных совершенных паросочетаний.  При добавлении  к  исходному
графу ребер совершенного паросочетания получится граф,  у которого
все степени вершин четны. Найдем в нем цикл, проходящий по каждому
ребру графа ровно один раз.  Этот цикл и является решением задачи.
Заметим при этом, что каждое ребро (i,j) паросочетания должно быть
заменено последовательностью дорог исходного графа,  которая опре-
деляет кратчайшее расстояние между вершинами i и j в исходном гра-
фе.

                            Задача 15.
     Производительность конвейера  определяется минимальной произ-
водительностью рабочего на конвейере.  Поэтому для решения  задачи
нам  достаточно определить максимальную производительность Р,  при
которой возможно распределить по станкам,  всех рабочих, когда для
каждого рабочего определен набор станков, на которые он может быть
поставлен (понятно, что это те станки, производительность на кото-
рых  у рабочего не ниже производительности Р).  Легко понять,  что
для выбранной производительности Х задача определения, возможно ли
распределение по станкам для каждого рабочего,  аналогична решению
задачи 4.  Для определения максимальной производительности Р,  при
которой  возможно  распределить  по  станкам  всех рабочих,  можно
воспользоваться методом дихотомии следующим образом. Отсортируем в
одномерном  A массиве размера N*N все элементы C[i,j],  1<=i,j<=N.
Определим левую границу ЛГ=1 и правую границу ПГ=N.
     Для элемента массива А с индексом СГ=(ЛГ+ПГ)/2, рассматривае-
мого в качестве возможной максимальной производительности Р, опре-
деляем, можно ли распределить по станкам всех рабочих. Если да, то
величина возможной максимальной  производительности  Р  увеличива-
ется.  Для этого пересчитывается значение левой границы по правилу
ЛГ:=СГ+1.  Если нет, то величина возможной максимальной производи-
тельности Р уменьшается. Для этого пересчитывается значение правой
границы по правилу ПГ:=СГ-1.
     Процесс заканчивается, когда ЛГ>=ПГ. Значение А[ПГ-1] и явля-
ется максимальной производительностью Р,  а конкретное распределе-
ние рабочих определяется структурой максимального потока.

                            Задача 17.
     Легко понять,  что сеть дорог будет  реализовывать  некоторый
связный (так как можно проехать из любого города в любой) граф без
циклов (так как одно ребро из цикла  можно  выбросить,  а  связный
граф  останется  связным).  Поэтому алгоритм построения сети дорог
минимальной суммарной стоимости очень прост.  На  каждой  итерации
необходимо находить дорогу минимальной стоимости, которая не обра-
зует цикла с уже  выбранными  дорогами  на  предыдущих  итерациях.
Основную трудность такого решения составляет проверка условия, об-
разуют ли ребра цикл.
     Однако решение  существенно  упрощается,  если  рассматривать
только минимальные ребра только между двумя множествами:  множест-
вом  помеченных вершин и множеством непомеченных вершин.  Понятно,
что эти множества должно соединять хотя бы одно ребро,  чтобы граф
был  связным.  Ясно,  что оно должно быть минимальным по длине.  В
описываемом ниже алгоритме это делается следующим образом.
     Для каждой  вершины  к из множества непомеченных вершин (а на
начальном этапе это все вершины,  кроме первой) определяется  бли-
жайшая  вершина из множества помеченных вершин БЛИЖ[к].  На каждой
итерации определяется кратчайшее ребро (i,j) между множеством  по-
меченных вершин и множеством непомеченных вершин, используя массив
БЛИЖ. Найденное ребро выбирается для системы дорог, а соответству-
ющая  вершина j считается помеченной.  После этого пересчитывается
массив БЛИЖ. При этом учитывается, что к изменение некоторой вели-
чины  БЛИЖ[k] может произойти только тогда,  когда расстояние от k
до j меньше, чем от k до БЛИЖ[k].
   Алгоритм
      для i от 1 до N выполнять
       нц
         флаг[i]:=0;
         БЛИЖ[i]:=1
       кц
      флаг[1]:=1;
      для k от 1 до N-1 выполнять
       нц
         минрас:=бесконечность;
         для i от 2 до N выполнять
           если флаг[i]=0 и минрас > C[БЛИЖ[i],i]
               то минрас:=C[БЛИЖ[i],i];
                  j:=i;
           все
         Вывод ребра (БЛИЖ[j],j)
         флаг[j]:=1;
         для i от 2 до N выполнять
           если флаг[i]=0 и C[БЛИЖ[i],i]>C[i,j]
               то БЛИЖ[i]:=j;
           все
       кц

                            Задача 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 и даст решение задачи.

                            Задача 20.
     Предполагаемый вариант решения использует полный перебор всех
вариантов.  В качестве первого звена цепочки берем последовательно
каждое из N колец.  Ищем сцепленные с этим кольцом, выбираем среди
них  одно  (все остальные кольца будут считаться удаленными - т.е.
строки и столбцы с номерами этих колец должны обнуляться).  С этим
изменением задача сводится к задаче 1 (Графы). Действительно, если
мы найдем максимальный путь в графе (в данном случае -  максималь-
ную длину цепочки в начальной конструкции), то мы минимизируем ко-
личество выброшенных колец.

                            Задача 21.
     Можно сформировать  граф,  состоящий  из  2*N  вершин,  соот-
ветствующих К-гранникам и типу наклеек,  причем две вершины соеди-
нены ребром,  если одна соответствует наклейке, а другая - К-гран-
нику,  при этом наклейка соответствующего типа находится на  соот-
ветствующем К-граннике. Добавив в этом графе 2 новые вершины, одна
из которых смежна всем вершинам,  соответствующим типам наклеек, а
другая - всем вершинам, соответствующим К-гранникам, сведем задачу
к задаче нахождения максимального потока между этими вершинами.

                            Задача 22.
     Показывается, что точное решение есть  максимум  из  двух
решений, полученных при помощи следующих эвристик:
     1) Вершину 1 соединяем последовательно с вершинами 2, 3,
..., N.
     Вершину 2 соединяем последовательно с вершинами 3,4,...,N.
                         ......
     Вершину i соединяем последовательно с вершинами i+1, i+2,
...,N.
                         ......
     и так до тех пор, пока хватит проводков.
     2) Вершину 2 соединяем с вершиной 1.
     Вершину 3 соединяем последовательно с вершинами 1,2.
                         ......
     Вершину i соединяем последовательно с вершинами i-1, i-2,
...,1.
                         ......
     и так до тех пор, пока хватит проводков.

                            Задача 23.
     Алгоритм нахождения  второго  минимального  расстояния  между
двумя  вершинами:
     По алгоритму Дейкстры находим кратчайший путь между начальной
вершиной N и конечной K,  состоящий из дуг a1,  ..., as. Во втором
по длине кратчайшем пути из N в K не будет по крайней мере  одного
из ребер ai.  Поэтому алгоритм нахождения этого второго пути будет
следующим:
     Для i от 1 до s повторять
         удалить из графа ребро (дорогу) ai;
         найти кратчайший путь из N в K в новом графе;
         если его длина меньше рекордной минимальной длины,
              полученной ранее,
         то запомнить текущий путь и его длину как рекорд;
         восстановить в графе ребро (дорогу) ai;
     конец_для;
Этот алгоритм можно найти в книге Кристофидеса "Теория графов. Ал-
горитмический подход".  Но в нем не рассматривается следующий слу-
чай:
       D_____E
        \   /
         \ /
     ----->----->
    A     B     C

     Кратчайший путь -- ABC, второй -- ABDEBC.
     Для того,  чтобы его обработать,  достаточно найти кратчайший
нетривиальный путь из каждой вершины в нее же.  Для этого в  алго-
ритме  Дейкстры  достаточно  на нулевом шаге не выставлять пометку
"Просмотрено" на начальной вершине.

                            Задача 24.
     Задача для произвольного графа является переборной, для дере-
ва решается за линейное время.  Основная проблема  -  организовать
полный перебор на графе,  моделируя движение полицейских по ребрам
графа.
     
