НачалоПодразделы
Другие разделы
| 1. Сортировка и поиск |
| 2. Комбинаторные объекты |
| 4. Поиск в ширину |
| 6. Динамическое программирование |
Дата и время
13/11/2024 06:09:37
3. Поиск в глубину
Применение поиска в глубину Разбор задачи 1309. Считая облака Разбор задачи 1269. Саванна Разбор задачи 1251. Шкатулки Разбор задачи 1384. Производство деталей Алгоритм топологической сортировки
Разбор задачи 1384. Производство деталей
Задача средней сложности на графы.
Для решения этой задачи можно использовать топологическую сортировку, т.е. размещение графа вдоль прямой таким образом, что все дуги были направлены слева направо. При этом достаточно упорядочить только вершины, достижимые из вершины 1.
Для хранения графа будем использовать два массива: массив d с номерами необходимых для производства деталей, записанных последовательно друг за другом, сначала для 1-й, затем для 2-й, и т.д., и массив f, в котором для i-й детали хранится номер начала последовательности номеров необходимых деталей в первом массиве, т.о. номера деталей, необходимых производства для i-й детали, хранятся в ячейках d[f[i]], d[f[i]+1], …, d[f[i+1]-1].
var
p:array[1..100000] of longint; { время на производство }
s:array[1..100000] of longint; { топологически упорядоченная последовательность }
d:array[1..200000] of longint; { необходимые детали для производства }
f:array[1..100001] of longint; { номера начал в массиве d }
u:array[1..100000] of boolean; { деталь уже произвели? }
n,i,j,k,m:longint;
t:int64; { общее время производства }
{ алгоритм топологической сортировки }
procedure topsort(i:longint);
var j:longint;
begin
if u[i] then exit;
for j:=f[i] to f[i+1]-1 do
topsort(d[j]);
u[i]:=true;
inc(m);
s[m]:=i;
end;
begin
{ ввод данных }
read(n);
for i:=1 to n do
read(p[i]);
m:=1;
for i:=1 to n do
begin
read(k);
f[i]:=m;
for j:=1 to k do
begin
read(d[m]);
inc(m);
end;
end;
f[n+1]:=m;
{ топологическая сортировка }
m:=0;
topsort(1);
{ расчет суммарного времени }
t:=0;
for i:=1 to m do
t:=t+p[s[i]];
{ вывод ответа }
writeln(t,' ',m);
for i:=1 to m do
write(' ',s[i]);
writeln;
end.
