Разбор олимпиадной задачи — Светофорчики

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

      Условие задачи взято с сайта acmp.ru (Время: 1 сек. Память: 16 Мб Сложность: 25%):

      В подземелье M тоннелей и N перекрестков, каждый тоннель соединяет какие-то два перекрестка. Мышиный король решил поставить по светофору в каждом тоннеле перед каждым перекрестком. Напишите программу, которая посчитает, сколько светофоров должно быть установлено на каждом из перекрестков. Перекрестки пронумерованы числами от 1 до N.

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

      Во входном файле INPUT.TXT записано два числа N и M (0 < N ≤ 100, 0 ≤ M ≤ N*(N-1)/2). В следующих M строках записаны по два числа i и j (1 ≤ i,j ≤ N), которые означают, что перекрестки i и j соединены тоннелем. Можно считать, что любые два перекрестка соединены не более, чем одним тоннелем. Нет тоннелей от перекрестка i до него самого.

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

      В выходной файл OUTPUT.TXT вывести N чисел: k-ое число означает количество светофоров на k-ом перекрестке.

      Примеры

      INPUT.TXT OUTPUT.TXT
      1 7 10
      5 1
      3 2
      7 1
      5 2
      7 4
      6 5
      6 4
      7 5
      2 1
      5 3
      3 3 2 2 5 2 3

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

      Это простейшая задача на графы — именно с таких задач стоит начать знакомство с этой темой. Прочитать про графы и про способы их представления в программе можно в соседней теме. Граф например может выглядть так:

      Итак, нам дан лабиринт из N точек и M переходов между точками. В программе удобно хранить такие структуры в виде графов. В качестве формата можно взять любой, но ниже приведен пример с матрицей смежности — мы создадим матрицу из N строк и N столбцов. В ячейку [i, j] матрицы помещаем единицу если существует переход (тоннель) между i-той и j-той вершиной. Для приведенного графа матрица смежности будет выглядеть так:

      Так как граф в задаче неориентированный (наличие тоннеля из узла A в узел B означает наличие тоннеля из B в A) — то для каждой пары чисел из файла будем добавлять две дуги. В конце концов, от нас требуют посчитать количество светофоров на каждом каждом перекрестке X, которое равно количеству дуг, инцидентных вершине X — обойдем матрицу и для каждой строки (задающей номер узла) проссумируем количество ненулевых элементов:

      #include <fstream>
      #include <vector>
      
      using namespace std;
      
      struct Graph {
        vector<vector<int>> matrix;
      
        Graph(int n) {
          matrix.resize(n, vector<int>(n, 0));
        }
      
        void addEdge(int a, int b) {
          matrix[a][b] = true;;
          matrix[b][a] = true;
        }
      
        int edgeCount(int node) const {
          int counter = 0;
          for(auto elem : matrix[node]) {
            if (elem == true)
              ++counter;
          }
          return counter;
        }
      };
      
      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
      
        int n, m;
        ifst >> n >> m;
      
        Graph graph(n);
      
        for(int i = 0; i < m; ++i) {
          int a, b;
          ifst >> a >> b;
      
          graph.addEdge(a-1, b-1);
        }
      
        for (size_t i = 0; i < graph.matrix.size(); ++i) {
          ofst << graph.edgeCount(i) << ' ';
        }
      
        return 0;
      }

      Приведенный подход к решению является более универсальным, однако часто он слишком сложен. Вот в этой задаче нужно посчитать сколько ребер входит в вершину — значит достаточно завести массив целых чисел (для хранения количества инцидентных ребер) размера N:

      #include <fstream>
      #include <vector>
      
      using namespace std;
      
      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
      
        int n, m;
        ifst >> n >> m;
      
        vector<int> crosses(n);
      
        for (int i = 0; i < m; ++i) {
          int from, to;
          ifst >> from >> to;
          crosses[from-1]++;
          crosses[to-1]++;
        }
      
        for (int cross : crosses) {
          ofst << cross << " ";
        }
      }
      

      А еще, можно заметить, что задача эквивалентна следующей: дано M*2 чисел — посчитать «сколько раз использовалось каждое из чисел».

      StudLance.ru

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