Тема: 1277 timus

Разъясните задачу pls.
Мне кажется что в обоих примерах ответ должен быть ДА, потому что все вершины рядом либо с музеем (museum), либо с убежищем (refuge).

2

Re: 1277 timus

Только что ее решил:)

На самом деле под выражением "вершина рядом с музеем/убежищем" - имеется ввиду то, что музей / убежище находится в этой вершине.

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

Что важно помнить - граф неориентированный, поэтому каждое ребро нужно представить в виде 2-х ориентированных ребер.

Джеймс Гослинг с нами!