里面所有点都有负数。。

也就是说。。

有些地方不挖更好

第三个点就是这种点。。

第三个点上有大量负数。。故一个都别挖。。。

虽然你可以挖M个。。。

把你所有的

return add

改为

return max( 0 , add)

谢谢。

program R30;

const maxn=1100;

maxm=200;

var f:array[0..maxn,0..maxm]of longint;

w:array[0..maxn]of longint;

fa:array[0..maxn]of longint;

q:array[0..maxn]of longint;

adj:array[0..maxn,0..maxn]of boolean;

mark:array[0..maxn]of boolean;

x,y:longint;

head,tail:longint;

i,j,k,m,n:longint;

ii,jj,kk:longint;

function max(a,b:longint):longint;

begin

if a>b then exit(a);

exit(b);

end;

{main}

begin

readln(n,m);

for i:=1 to n do read(w[i]);

for i:=1 to n do

begin

readln(x,y);

adj[x,y]:=true;

adj[y,x]:=true;

end;

mark[0]:=true;

fa[0]:=-1;

head:=0;

tail:=1;

q[1]:=0;

while true do

begin

inc(head);

i:=q[head];

for j:=1 to n do

if adj[i,j] and not mark[j] then

begin

inc(tail);

q[tail]:=j;

mark[j]:=true;

fa[j]:=i;

end;

if tail=n+1 then break;

end;

for j:=n+1 downto 2 do

begin

i:=q[j];

for ii:=m downto 1 do

f[i,ii]:=f[i,ii-1]+w[i];

k:=fa[i];

for ii:=m downto 0 do

begin

for jj:=m downto 1 do

begin

if ii+jj>m then continue;

f[k,ii+jj]:=max(f[k,ii+jj],f[k,ii]+f[i,jj]);

end;

end;

end;

writeln(f[0,m]);

end.