Разбор задачи Тритон-почтальон

  • В этой теме 0 ответов, 1 участник, последнее обновление 2 месяца, 4 недели назад сделано Васильев Владимир Сергеевич.
Просмотр 0 веток ответов
  • Автор
    Сообщения
    • #6620
      @admin
      StudLance.ru

      Мудрый тритон работает почтальоном в Лукоморье. В перечень его обязанностей входит доставка корреспонденции птицам, разместившим свои гнезда на ветвях дуба.

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

      Каждое гнездо дуба обозначено уникальным номером, что соответствует номеру квартиры, который мы иногда указываем, отправляя письма родным и близким по обычной почте. Гнездо, расположенное на первой развилке ствола имеет номер один. Тритон может только ползти по веткам или стволу дуба, прыжки и перелеты полностью исключены. Никакие ветки не соприкасаются и не пересекаются. Тритон начинает свой путь и заканчивает у подножья дуба (ночевать на дереве ему строго воспрещается профсоюзом работников Лукоморья).

      Требуется написать программу, которая по описанию мест обитания птиц и списку корреспонденции определяет, сколько раз придется извиняться мудрому тритону.

      Входные данные

      В первой строке входного файла находится число M – количество гнезд на дубе (0<M≤1000).

      В следующих M строках находится информация о размещении гнезд и количестве писем для каждого из возможных адресатов. Первые два числа ni и li – количество соседей гнезда с номером i и количество направленных по этому адресу писем соответственно (0≤ li ≤1000). Далее в строке приводится ni чисел – номера гнезд, являющихся соседними с гнездом c номером i.

      Выходные данные

      В единственной строке выходного файла должно содержаться единственное число – минимальное количество извинений, которые придется приносить мудрому тритону, для того чтобы доставить все письма.

      Примеры

      INPUT.TXT OUTPUT.TXT
      1 5
      3 2 2 5 4
      1 1 1
      1 1 4
      2 2 3 1
      1 3 1
      2

      Разбор решения задачи

      Чтобы понять суть задачи — стоит нарисовать пару деревьев и попробовать разнести письма по узлам.

      Во-первых, тритон не должен проходить по всему дереву — не только из соображений оптимальности кода, но и для корректности — заход в узел может провести к увеличению счетчика извинений. Это хорошо иллюстрирует следующее дерево:

      Красным цветом помечены узлы, в которые не нужно входить, а зеленым — в которые нужно. Ветка 5, 6, 7 могла бы быть очень длинной — заходить в нее тритон не должен. Однако, если добавить в нее хоть один зеленый узел — необходимо будет пройти по множеству красных.

      Вывод: Нужен какой-то эффективный механизм для определения необходимости перехода по ветке.

      Во-вторых, тритон не должен отдавать все письма разом. Это хорошо видно на следующем примере:

      Внутри узла записан номер, а на зеленых дугах — количество писем, которые нужно доставить. В узел 1 надо доставить 2 письма, если их отдать при первом заходе — то придется извиниться трижды — при возврате (показаны красным цветом) из узла 2, узла 3 и узла 4. Однако, если при первом заходе отдать лишь одно письмо — то достаточно будет двух извинений.

      Отсюда вырисовывается такой алгоритм раздачи писем: если в узел нужно будет вернуться еще раз — то выдать одно письмо (чтобы не приносить лишний извинений), если же мы в узел больше никогда не вернемся — то выдать все оставшиеся письма.

      Отсюда следует, что нужно многократно выполнять проверку «нужно ли передавать письма в поддерево, корнем которого является текцщий узел».

      Решение:

      Опишем структуру узла:

      struct Nest {
        int nest_letters;
        int branch_letters;
        vector<size_t> neighbourhood;
        bool visited;
      };

      Поле nest_letters хранит количество писем, которые осталось доставить в это гнездо, а переменная branch_letters — количество писем, которые нужно передать в поддереве, корнем которого является текущий узел. Такой подход называется динамическим программированием, так как вместо того, чтобы вычислять каждый раз необходимоть перехода по дуге (наличие писем в поддереве) — это значение вычисляется один раз и затем многократно используется.

      Функция calc_letters обходит поддерево с корнем с заданной вершине и для каждого его узла подсчитывает branch_letters. Для этого функция проходит по всем соседям узла и расчитывает этот параметр для них, ведь branch_letters узла K равен nest_letters(K) + branch_letters всех его дочерних узлов. Эта функция имет оценку сложности O(N), так как по каждому узлу мы пройдем лишь один раз:

      void calc_letters(vector<Nest> &nests, size_t nest_number) {
        auto& nest = nests[nest_number];
      
        nest.visited = true;
      
        nest.branch_letters = nest.nest_letters;
      
        for(size_t j = 0; j < nest.neighbourhood.size(); ++j) {
          auto neighbour_id = nest.neighbourhood[j];
      
          if (nests[neighbour_id].visited == false) {
            calc_letters(nests, neighbour_id);
            nest.branch_letters += nests[neighbour_id].branch_letters;
          }
        }
      }

      Теперь можно без труда и очень эффективно — также за O(N) определить количество необходимых извинений:
      Для этого — обойдем дерево по вершинам, в которых branch_letters не равен нулю, и при каждом посещении узла будем уменьшать счетчик писем nest_letters на единицу, если он <= нуля - увеличивать счетчик извинений:

      int pardon_count(vector<Nest> &nests, size_t nest_number) {
        auto& nest = nests[nest_number];
      
        int pardons = 0;
      
        nest.visited = true;
      
        if (nest.nest_letters <= 0)
          pardons++;
        else
          nest.nest_letters--;
      
        for (size_t j = 0; j < nest.neighbourhood.size(); ++j) {
          auto neighbour_id = nest.neighbourhood[j];
      
          if (nests[neighbour_id].branch_letters <= 0)
            continue;
      
          if (nests[neighbour_id].visited == false) {
            pardons += pardon_count(nests, nest.neighbourhood[j]);
      
            if (nest.nest_letters <= 0)
              pardons++;
            else
              nest.nest_letters--;
          }
        }
      
        return pardons;
      }
      Программа целиком:
      #include <fstream>
      #include <vector>
      
      using namespace std;
      
      struct Nest {
        int nest_letters;
        int branch_letters;
        vector<size_t> neighbourhood;
        bool visited;
      };
      
      void calc_letters(vector<Nest> &nests, size_t nest_number) {
        auto& nest = nests[nest_number];
      
        nest.visited = true;
      
        nest.branch_letters = nest.nest_letters;
      
        for(size_t j = 0; j < nest.neighbourhood.size(); ++j) {
          auto neighbour_id = nest.neighbourhood[j];
      
          if (nests[neighbour_id].visited == false) {
            calc_letters(nests, neighbour_id);
            nest.branch_letters += nests[neighbour_id].branch_letters;
          }
        }
      }
      
      int pardon_count(vector<Nest> &nests, size_t nest_number) {
        auto& nest = nests[nest_number];
      
        int pardons = 0;
      
        nest.visited = true;
      
        if (nest.nest_letters <= 0)
          pardons++;
        else
          nest.nest_letters--;
      
        for (size_t j = 0; j < nest.neighbourhood.size(); ++j) {
          auto neighbour_id = nest.neighbourhood[j];
      
          if (nests[neighbour_id].branch_letters <= 0)
            continue;
      
          if (nests[neighbour_id].visited == false) {
            pardons += pardon_count(nests, nest.neighbourhood[j]);
      
            if (nest.nest_letters <= 0)
              pardons++;
            else
              nest.nest_letters--;
          }
        }
      
        return pardons;
      }
      
      
      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
      
        size_t n;
        ifst >> n;
      
        vector<Nest> nests(n);
      
        for (size_t i = 0; i < n; ++i) {
          size_t neighbourhood_count;
          ifst >> neighbourhood_count >> nests[i].nest_letters;
          nests[i].neighbourhood.resize(neighbourhood_count);
          nests[i].visited = false;
          nests[i].branch_letters = 0;
      
          for (size_t j = 0; j < neighbourhood_count; ++j) {
            size_t number;
            ifst >> number;
            nests[i].neighbourhood[j] = number-1;
          }
        }
      
        calc_letters(nests, 0);
      
        for (auto& nest : nests) {
          nest.visited = false;
        }
      
        ofst << pardon_count(nests, 0);
      }

      StudLance.ru

Просмотр 0 веток ответов
  • Для ответа в этой теме необходимо авторизоваться.
×