Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Производство деталей

(Время: 2 сек. Память: 64 Мб Сложность: 48%)

Данная задача сводится к реализации топологической сортировки в ациклическом ориентированном графе. Речь идет об упорядочивании вершин в одномерном массиве таким образом, чтобы не существовало пути из вершины с большим номером в вершину с меньшим номером. В нашем случае мы хотим получить такой список номеров деталей, в котором позиция любой детали правее (индекс массива больше) всех деталей, предназначенных для изготовления заданной.

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

Безусловно, эта задача может быть отнесена к темам "Теория графов", "Рекурсия" и "Структуры данных". Поэтому нужно сказать о том, как следует представить данные в программе. Очевидно, что в качестве вершин графа будут выступать номера деталей, а в качестве ребер - связи с информацией о том, какая деталь необходима для изготовления заданной детали. Иными словами, будем считать ребро (u,v) принадлежащим графу, если деталь с номером u необходима для изготовления детали с номером v. При заданных ограничениях мы не можем использовать матрицу смежности (не хватит памяти, т.к. матрица может быть размером 105 x 105) или простой неупорядоченный список ребер (обработка потомков определенной вершины может занять 2*105 операций, что вызовет превышение временного лимита). Наиболее приемлемым представлением графа здесь является одномерный массив векторов v[i], где в v[i] содержится список номеров деталей, необходимых для производства детали с номером i. Такое решение является оптимальным как по памяти, так и по времени. Здесь наиболее удобным решением является использование типа данных vector из библиотеки STL в языке C++, т.к. необходимые функции обработки элементов в динамическом массиве в нем уже реализованы. В случае использования Delphi возникает необходимость реализации механизмов для работы с динамическим массивом, что требует некоторых затрат.

Опишем функцию dfs(k), которая будет осуществлять обход графа в глубину и добавлять справа в некоторый вектор (массив) d список из номеров деталей, необходимых для изготовления детали k, включая саму эту деталь. Последовательность деталей при этом будет соответствовать хронологии изготовления детали k. Во избегании повтора деталей будем использовать некоторый массив w[1..n] для запоминания уже изготовленных деталей. В процессе обхода мы сразу можем вычислять время, необходимое для изготовления детали k, именно это значение и будет возвращать dfs(k):

  int64 dfs(k){
    sum=p[k]; w[k]=1
    for i=1..v[k].size()
      if(w[v[k][i]]==0) sum = sum + dfs(v[k][i])
    d.push(k)  
    return sum
  }

Для построения необходимого нам списка и вычисления общего времени работы достаточно вызывать dfs(1). Заметим, что несмотря на то, что время, необходимое на изготовление любой детали при наличии необходимых деталей не превосходит 109, общее время может значительно превосходить ограничения 4-байтового целого типа, поэтому здесь возникает необходимость использования 8-байтового типа (int64 в Delphi или __int64 в Си), либо большого вещественного типа (например, extended в Delphi).

Используя реализацию вышеописанной функции dfs(k), несложно реализовать основную алгоритмическую часть:

  read(n)
  for i=1..n read(p[i])
  for i=1..n {
    read(k)
    for j=1..k {
      read(x)
      v[i].push(x)
    }	
  }
  writeln(dfs(1), ' ', d.size())
  for i=1..d.size() write(d[i], ' ')

[Обсуждение] [Все попытки] [Задача]


Красноярский краевой Дворец пионеров, (c)2006 - 2025, ИНН 246305493507, E-mail: admin@acmp.ru