Описание
Компьютерная сеть Пентагона состоит из N компьютеров, некоторые из которых соединены прямыми двусторонними каналами связи. В целях повышения секретности при проектировании сети количество каналов связи было сокращено до минимума с тем условием, чтобы любые два компьютера имели возможность обмена информацией либо непосредственно, либо через другие компьютеры сети

КГБ хочет прослушивать все передаваемые в сети Пентагона сообщения. Для этого советскими программистами был разработан вирус, который, будучи установлен на какой-либо из компьютеров, передает КГБ всю информацию, проходящую через него. Оказалось, что материальные затраты, необходимые для установки вируса на различные компьютеры, различны

Задача
Требуется определить набор компьютеров, которые КГБ должно инфицировать, чтобы минимизировать общие материальные затраты


Входные данные
Первая строка входного файла содержит N - количество компьютеров в сети (1N500). В i-ой из последующих N строк содержатся номера компьютеров, с которыми непосредственно связан компьютер номер i. Далее следуют N целых чисел из диапазона [1,1000] - материальные затраты, связанные с установкой вируса на каждый из компьютеров

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


Например:

NETHACK.IN
5
5
4
4
2 3 5
4 1
1 5 5 2 10

NETHACK.OUT
3
1 4




Идеи
Динамическое программирование на дереве

Комментарии
Первый абзац условия задачи в результате формализации сводится к словам "задано дерево с N вершинами", второй - "найти доминирующее над ребрами множество вершин минимального веса". Выберем какую-нибудь вершину заданного дерева в качестве корня и подвесим дерево за эту вершину. Для каждого поддерева определим пару чисел (а,b), где а равняется ответу на нашу задачу для этого поддерева, а b - ответом на ту же задачу с дополнительным требованием включения корня рассматриваемого поддерева в искомое множество

Эти пары чисел (а,Ь) вычисляются динамически по высоте поддеревьев. Для дерева, состоящего из единственной вершины, а равно нулю, a b - весу этой вершины. Теперь покажем, как вычислить числа а,b для дерева, состоящего из большего числа вершин. Его корень имеет какое-то количество поддеревьев, для которых пары чисел (аi,bi) уже подсчитаны. Ясно, что число b равно сумме всех чисел аi увеличенной на вес корня рассматриваемого дерева. Число а, в свою очередь, равно минимуму из суммы чисел bi и числа b

Описанная процедура легко реализуется рекурсивным алгоритмом


Упражнение
Решите аналогичную задачу для случая, когда нужно контролировать не каналы связи, а деятельность компьютеров, причем контролировать деятельность компьютера вирус может либо находясь на этом компьютере, либо с любого из соседних компьютеров




Решение

{$A+,B-,D+,E+,F-,G-,I-,L+,N+,O-,P-,Q+,R+,S+,T-,V+,X+,Y+} 
{$M 65520,0,655360} 
 
Program Nethack; 
Const NMax=750; 
Type PKnot = ^TKnot; 
     TKnot = Record 
               N:Integer; 
               Next:PKnot; 
             End; 
Var A:Array[1..NMax] of PKnot; {Дерево}
    Weight:Array[1..NMax] of LongInt; {Веса}
    N:Integer; 
 
Procedure New(Var q:PKnot); 
Begin 
  System.New(q); 
  q^.N:=0; 
  q^.Next:=Nil; 
End; 
 
Procedure Init; 
Var i,k:Integer; 
    q:PKnot; 
Begin 
  Assign(Input,'Nethack.in'); 
  ReSet(Input); 
 
  ReadLn(N); 
  For i:=1 to N do A[i]:=Nil; 
 
  For i:=1 to N do Begin 
    While Not SeekEoLn do Begin 
      Read(K); 
      If A[i]=Nil then Begin 
        New(A[i]); 
        q:=A[i] 
      End 
      Else Begin 
        New(q^.next); 
        q:=q^.next; 
      End; 
 
      q^.N:=K; 
    End; 
 
    ReadLn; 
  End; 
 
  for i:=1 to N do Read(Weight[i]); 
  Close(Input); 
End; 
 
Var Best:Array[1..NMax] of LongInt;    {Лучший вес} 
    Take:Array[1..NMax] of Boolean;    {Берем или нет} 
    Hand:Array[1..NMax] of PKnot;      {Подвешенное дерево} 
    St:Array[1..NMax] of Integer;      {Очередь}
    Edge:Array[1..NMax] of Integer;    {Количество необработанных соседей}
    NotWas:Array[1..NMax] of Boolean;  {Признак обработанности} 
    hSt,lSt:Integer; 
 
Procedure Push(i:Integer); 
Begin 
  Inc(hSt); 
  St[hSt]:=i; 
End; 
 
Procedure Solve; 
Var i:Integer; 
    q,p:PKnot; 
    j:LongInt; 
Begin 
  for i:=1 to N do begin 
    Hand[i]:=Nil; 
    Best[i]:=-1; 
  end; 
  FillChar(NotWas,SizeOf(NotWas), True); 
 
  hSt:=0; lSt:=1; 
  for i:=1 to N do begin 
    Edge[i]:=0; 
    q:=A[i]; 
    while q<>Nil do begin 
      inc(Edge[i]); 
      q:=q^.Next; 
    end; 
 
    if Edge[i]=1 then begin 
      Push(i); 
      Best[i]:=0; 
      Take[i]:=False; 
    end; 
  end; 
 
  while (lst<=hSt) do begin 
    i:=St[lSt]; Inc(lSt); 
    NotWas[i]:=False; 
 
    {Подвесить в дерево и обработать соседей}
    q:=A[i]; 
    while q<>Nil do begin 
      dec(Edge[q^.N]); 
      if NotWas[q^.N] then begin 
        new(p); 
        p^.next:=Hand[q^.N]; 
        Hand[q^.N]:=p; 
        p^.N:=i; 
      end; 
 
      if Edge[q^.N]=1 then Push(q^.N); 
      q:=q^.Next; 
    end; 
 
    {Нахождение решения для данного поддерева
     Берем вершину}
    if Best[i]<0 then begin 
      q:=Hand[i]; 
      Best[i]:=Weight[i]; 
      while q<>Nil do begin 
        Inc(Best[i], Best[q^.N]); 
        q:=q^.next; 
      end; 
 
      {Не берем вершину}
      j:=0; 
      q:=Hand[i]; 
      while q<>Nil do begin 
        Inc(j, Weight[q^.N]); 
        p:=Hand[q^.N]; 
        while p<>Nil do begin 
          Inc(j, Best[p^.N]); 
          p:=p^.next; 
        end; 
 
        q:=q^.Next; 
      end; 
 
      if Best[i] then  Take[i]:=True 
      else begin 
        Take[i]:=False; 
        Best[i]:=j; 
      end; 
    end; 
  end; 
End; 
 
Procedure Print; 
Var List:Array[1..NMax] of Boolean; 
    i:Integer; 
    q,p:PKnot; 
begin 
  Assign(Output,'Nethack.out'); 
  ReWrite(Output); 
 
  if N=2 then begin 
    if Weight[1] then WriteLn(Weight[1],' ',1) 
    else WriteLn(Weight[2],' ',2); 
 
    exit; 
  end; 
 
  Writeln(Best[St[N]]); 
 
  FillChar(List, SizeOf(List), 0); 
  hSt:=1; St[1]:=St[N]; 
  while hSt<>0 do begin 
    i:=St[hSt]; Dec(hSt); 
 
    {Берем}
    if Take[i] then begin 
      List[i]:=True; 
 
      q:=Hand[i]; 
      while q<>Nil do begin 
        Push(q^.N); 
        q:=q^.Next; 
      end; 
    end 
    {Не берем}
    else begin 
      q:=Hand[i]; 
      while q<>Nil do begin 
        List[q^.N]:=True; 
 
        p:=Hand[q^.N]; 
        while p<>Nil do begin 
          Push(p^.N); 
          p:=p^.Next; 
        end; 
 
        q:=q^.Next; 
      end; 
    end; 
  end; 
 
  for i:=1 to N do 
    if List[i] then Write(i,' '); 
 
  Close(Output); 
end; 
 
Begin 
  Init; 
  if N<>2 then 
    Solve; 
  Print;
End.
 

© Особенности национальных задач по информатике