Dec (k);
· Во-вторых, нам при формировании цепи не имеет смысла заходить в вершины, валентность которых равна 1. В <u,v>-цепях такие вершины являются лишними.
Решение: перед тем как пойти к какой-либо вершине, мы проверяем ее валентность. И если валентность вершины равна 1, то пропускаем ее.
If Val_V[i]<>1 then begin … end;
· В-третьих, например, идя из вершины 3 в вершину 5, нужно исключить возможность формирования вершинно-пересекающихся цепей 3-1-4-5 и 3-1-10-5.
Решение: как только была найдена нужная нам вершина, мы должны вернуться к исходной вершине и продолжить поиск, но уже по другому ребру. Для этого вводим специальную логическую переменную pp, которая будет отвечать за нахождение вершины.
Изначально pp:=false, как только нашли вершину v,
pp:=true. Далее идем назад, пока не встретим снова вершину u. Нашли ее, pp:=false, и снова продолжаем поиск и формирование <u,v>-цепи.
После внесенных изменений процедура Solve будет выглядеть так:
Procedure Solve;
var B:boolmas;
Num:mas;
u,v,t,ways:integer;
pp:boolean;
Procedure Search (i:integer; var k:integer);
var j:integer;
begin
Num[k]:=i;
B[i]:=True;
j:=0;
if A[i,v]=1 then begin
pp:=true;
Print(num,k);
inc(ways);
FillChar (Num,Sizeof(Num),0);
end
else
while (j<N) and not pp do begin
inc(j);
if (A[i,j]=1) and (B[j]=false) then
if Val_V[i]<>1 then begin
inc(k);
Search(j,k);
end;
end;
dec (k);
if k=1 then pp:=false;
end;
begin
for u:=1 to N-1 do
for v:=u+1 to N do begin
write (u,’ – ‘,v);
if A[u,v]=1 then writeln (‘ смежные’)
else if (Val_V[u]=1) or (Val_V[v]=1) then writeln (‘ 1′)
else begin
pp:=false; t:=1; ways:=0;
FillChar (B,Sizeof(B),0);
Search (u,t);
writeln (‘ways: ‘,ways);
end;
end;
end;
Loading ...