Why I get WA? Pelase, help me!!!!!!! And what should I do if the branch contain 0 apples?(+) My program:
Program t1018;
Const MaxN=100;
Var N,Q,i,j,k : integer;
B : array[1..MaxN-1,1..3]of integer;
W,L,P : array[1..MaxN]of integer;
D : array[1..MaxN,0..MaxN,1..2]of integer;
{1 - preserved;2 - delete}
Ex : boolean;
maxl,t1,t2 : integer;
a1,a2,b1,b2 : integer;
Procedure GetT(Num : integer; Var Num1,Num2 : integer);
Var i,j : integer;
begin
j:=0;
for i:=1 to N-1 do
if (B[i,1]=Num)and(L[Num]<L[B[i,2]]) then begin
if j=0 then Num1:=B[i,2] else Num2:=B[i,2];
j:=j+1;
end else
if (B[i,2]=Num)and(L[Num]<L[B[i,1]]) then begin
if j=0 then Num1:=B[i,1] else Num2:=B[i,1];
j:=j+1;
end;
end;
begin
Read(N,Q);
for i:=1 to N-1 do Read(B[i,1],B[i,2],B[i,3]);
fillchar(L,SizeOf(L),0);
L[1]:=1;
j:=0;
Repeat
Ex:=true;
j:=j+1;
for i:=1 to N-1 do
if (L[B[i,1]]=j)and(L[B[i,2]]=0) then begin
L[B[i,2]]:=j+1;
Ex:=false;
end else if (L[B[i,1]]=0)and(L[B[i,2]]=j) then begin
L[B[i,1]]:=j+1;
Ex:=false;
end;
Until Ex;
maxl:=j;
for i:=1 to N-1 do
if L[B[i,1]]>L[B[i,2]] then W[B[i,1]]:=B[i,3] else W[B[i,2]]:=B
[i,3];
for i:=1 to MaxN do
for j:=0 to MaxN do
for k:=1 to 2 do
D[i,j,k]:=-1;
fillchar(P,SizeOf(P),0);
for i:=1 to N-1 do
if L[B[i,1]]<L[B[i,2]] then P[B[i,1]]:=P[B[i,1]]+1 else P[B[i,2]]:=P
[B[i,2]]+1;
for i:=1 to N do
if P[i]=0 then begin
D[i,1,1]:=W[i];
end;
for j:=maxl-1 downto 1 do
for i:=1 to N do
if (L[i]=j)and(P[i]>0) then begin
GetT(i,t1,t2);
D[i,0,2]:=0;
if P[i]=2 then
for a1:=0 to MaxN do
for b1:=1 to 2 do if D[t1,a1,b1]<>-1 then
for a2:=0 to MaxN do
for b2:=1 to 2 do if D[t2,a2,b2]<>-1 then
if D[i,a1+a2+1,1]<D[t1,a1,b1]+D[t2,a2,b2]+W[i] then
D[i,a1+a2+1,1]:=D[t1,a1,b1]+D[t2,a2,b2]+W[i];
if P[i]=1 then
for a1:=0 to MaxN do
for b1:=1 to 2 do if D[t1,a1,b1]<>-1 then
if D[i,a1+1,1]<D[t1,a1,b1]+W[i] then
D[i,a1+1,1]:=D[t1,a1,b1]+W[i];
end;
Writeln(D[1,Q+1,1]);
end. Re: You should just ignore it.
For example this test:
7 4
1 2 10
1 4 30
2 3 50
2 6 0
4 5 40
4 7 0
The answer seems to be 130, but it is not, because we keep the 0
apple branches -- it is 70; just assume the 0 branches do not exist
and solve the problem for q - number of 0 branches;
for example the test case above should be considered this way:
4 2
1 2 10
1 4 30
2 3 50
4 5 40
Good luck. I ignore it,but I get WA. Can you say me that I should do if branch with 0 apples have sub-branch(+) Program t1018;
Const MaxN=100;
Var N,Q,i,j,k : integer;
B : array[1..MaxN-1,1..3]of integer;
W,L,P : array[1..MaxN]of integer;
D : array[1..MaxN,0..MaxN,1..2]of integer;
{1 - preserved;2 - delete}
Ex : boolean;
maxl,t1,t2 : integer;
a1,a2,b1,b2 : integer;
Procedure GetT(Num : integer; Var Num1,Num2 : integer);
Var i,j : integer;
begin
j:=0;
for i:=1 to N-1 do
if (B[i,1]=Num)and(L[Num]<L[B[i,2]]) then begin
if j=0 then Num1:=B[i,2] else Num2:=B[i,2];
j:=j+1;
end else
if (B[i,2]=Num)and(L[Num]<L[B[i,1]]) then begin
if j=0 then Num1:=B[i,1] else Num2:=B[i,1];
j:=j+1;
end;
end;
begin
Read(N,Q);
for i:=1 to N-1 do Read(B[i,1],B[i,2],B[i,3]);
i:=0;
while i<=N-1 do begin
i:=i+1;
if B[i,3]=0 then begin
N:=N-1;
Q:=Q-1;
if i=N then break;
B[i]:=B[N];
i:=i-1;
end;
end;
fillchar(L,SizeOf(L),0);
L[1]:=1;
j:=0;
Repeat
Ex:=true;
j:=j+1;
for i:=1 to N-1 do
if (L[B[i,1]]=j)and(L[B[i,2]]=0) then begin
L[B[i,2]]:=j+1;
Ex:=false;
end else if (L[B[i,1]]=0)and(L[B[i,2]]=j) then begin
L[B[i,1]]:=j+1;
Ex:=false;
end;
Until Ex;
maxl:=j;
for i:=1 to N-1 do
if L[B[i,1]]>L[B[i,2]] then W[B[i,1]]:=B[i,3] else W[B[i,2]]:=B
[i,3];
for i:=1 to MaxN do
for j:=0 to MaxN do
for k:=1 to 2 do
D[i,j,k]:=-1;
fillchar(P,SizeOf(P),0);
for i:=1 to N-1 do
if L[B[i,1]]<L[B[i,2]] then P[B[i,1]]:=P[B[i,1]]+1 else P[B[i,2]]:=P
[B[i,2]]+1;
for i:=1 to N do
if P[i]=0 then
D[i,1,1]:=W[i];
for j:=maxl-1 downto 1 do
for i:=1 to N do
if (L[i]=j)and(P[i]>0) then begin
GetT(i,t1,t2);
D[i,0,2]:=0;
if P[i]=2 then
for a1:=0 to MaxN do
for b1:=1 to 2 do if D[t1,a1,b1]<>-1 then
for a2:=0 to MaxN do
for b2:=1 to 2 do if D[t2,a2,b2]<>-1 then
if D[i,a1+a2+1,1]<D[t1,a1,b1]+D[t2,a2,b2]+W[i] then
D[i,a1+a2+1,1]:=D[t1,a1,b1]+D[t2,a2,b2]+W[i];
if P[i]=1 then
for a1:=0 to MaxN do
for b1:=1 to 2 do if D[t1,a1,b1]<>-1 then
if D[i,a1+1,1]<D[t1,a1,b1]+W[i] then
D[i,a1+1,1]:=D[t1,a1,b1]+W[i];
end;
Writeln(D[1,Q+1,1]);
end. Sorry for my last message. I misunderstood you. Now I get AC. Thank you very much ! ! ! > You should just ignore it.
> For example this test:
>
> 7 4
> 1 2 10
> 1 4 30
> 2 3 50
> 2 6 0
> 4 5 40
> 4 7 0
>
> The answer seems to be 130, but it is not, because we keep the 0
> apple branches -- it is 70; just assume the 0 branches do not exist
> and solve the problem for q - number of 0 branches;
> for example the test case above should be considered this way:
> 4 2
> 1 2 10
> 1 4 30
> 2 3 50
> 4 5 40
>
> Good luck.
> |
