|
Рыболовная сеть
(Время: 1 сек. Память: 16 Мб Сложность: 10%)
Данную задачу можно решить интуитивно. Несложно придумать такой процесс разрывов соединений между узлами, который оставляет рыболовную сеть нераспавшейся, а любой другой последующий развыв приводит к ее делению на две части. Примером такой процедуры является процесс развывов сети для каждого квадрата в одном и том же направлении соединений. Например, можно произвести разрвыв нижней части каждого квадрата. Понятно, что при таких действиях мы получим (N-1)*(M-1) разрывов (количество квадратов), в результате которых сеть не распадется и других подобных разрывов больше нельзя будет произвести.
Можно формально доказать, что число разрывов равно именно количеству клеток сети, т.е. значению (N-1)*(M-1). Рыболовную сеть можно рассматривать как граф, где в качестве вершин будут выступать узлы сети, а в качестве ребер – соединения между узлами. Если мы допустим максимальное число повреждений согласно условию, то в данном графе не останется циклов и он будет продолжать оставаться связным, это означает, что мы получим дерево (связный ациклический граф). Известно, что существует однозначная связь в дереве между количеством вершин и количеством ребер: ребер на одно меньше, чем вершин. В нашем дереве (в поврежденной рыболовной сети) ровно M*N вершин и R1 = M*N-1 ребер. В исходном графе мы имели R2 = N*(M-1)+M*(N-1) ребер. Поэтому искомое количество разрывов должно быть равно разнице последних величин: R2-R1 = N*(M-1) + M*(N-1) – (M*N-1) = (N-1)*(M-1), что и требовалось доказать.
| |
