Код:
USES crt;
const
MAX_SIZE = 8;
MIN_VALUE = -3600; { -5e4; }
ds : array [1..Max_Size, 1..Max_Size] of integer = ((0,19,0,0,0,0,0,0),
(19,0,12,13,0,0,0,0),
(0,12,0,0,0,11,0,7),
(0,13,0,0,0,0,0,0),
(0,0,0,0,0,0,0,10),
(0,0,11,0,0,0,0,0),
(0,0,0,0,0,0,0,8),
(0,0,17,0,10,0,8,0));
type
edge = record
num, weight: integer;
end;
vertex = record
left, right: edge;
end;
var
n, i,jk, totalEdges: integer;
adjMatrix: array [1 .. MAX_SIZE, 1 .. MAX_SIZE] of integer;
{ матрица смежности }
adj: array [1 .. MAX_SIZE ] of vertex; { двоичное дерево }
edgesAmount: array [1 .. MAX_SIZE ] of integer;
mem: array [1 .. MAX_SIZE , 1 .. MAX_SIZE ] of integer;
procedure dfs(num: integer);
var
isLeft: boolean;
i: integer;
begin
isLeft := true;
for i := 1 to n do
begin
if (adjMatrix[num][i] <> 0) then
begin
if (isLeft) then
begin
adj[num].left.num := i;
adj[num].left.weight := adjMatrix[num, i];
end
else
begin
adj[num].right.num := i;
adj[num].right.weight := adjMatrix[num, i];
end;
isLeft := false;
adjMatrix[num][i] := 0;
adjMatrix[i][num] := 0;
dfs(i);
edgesAmount[num] := edgesAmount[num] + edgesAmount[i] + 1;
end;
end; { FOR }
end; { Procedure }
procedure input;
var
f, s, w: integer;
begin
read(n);
read(totalEdges);
{for i := 1 to n do
begin
read(f);
read(s);
read(w);
adjMatrix[f, s] := w;
adjMatrix[s, f] := w;}
For i:=1 to n do
For jk:=1 to n do
adjMatrix[i,jk]:=ds[i,jk];
dfs(1);
end;
function max(a, b: integer): integer;
begin
if (a > b) then
max := a
else
max := b;
end;
function f(num, edges: integer): integer;
var
left, right: edge;
res, rightEdges, leftEdges, leftValue, rightValue, cur: integer;
begin
left := adj[num].left;
right := adj[num].right;
if (mem[num, edges] <> 0) then
f := mem[num, edges]
else if (edges = 0) then
f := 0
else if (edges > edgesAmount[num]) then
f := MIN_VALUE
else if (edges = 1) then
f := max(left.weight, right.weight);
res := 0;
for i := 0 to edges do
begin
leftEdges := i;
rightEdges := edges - i;
leftValue := 0;
rightValue := 0;
if (leftEdges <> 0) then
leftValue := left.weight + f(left.num, leftEdges - 1);
if (rightEdges <> 0) then
rightValue := right.weight + f(right.num, rightEdges - 1);
cur := leftValue + rightValue;
res := max(res, cur);
end;
mem[num][edges] := res;
f := res;
end;
procedure solve;
var
res: integer;
begin
res := f(1, totalEdges);
write(res, ' ');
end;
BEGIN
input;
solve;
END.