这题的我用的是树状DP,有不能同时购买关系的所有物品放在一个树中,先把所有的树分离出来,不在树中的物品价值直接加起来,再对所有分离出的树求最大价值。但很莫名其妙的不对……
program p188(input, output);
var
p, t, Sum, n, m, count, i, a, b: longint;
tmps: array [1..10000, 1..2] of longint;
ufs: array [1..1000] of record
treeid, up, size: longint
end;
has: array [1..1000] of boolean;
value: array [1..1000] of longint;
treesize: array [1..1000] of longint;
q: array [1..1000, 1..1000] of record
a, b: longint
end;
tree: array [1..1000, 0..1000] of longint;
node: array [1..1000] of boolean;
procedure dotree(treeid: longint);
var
aa, bb, c, d, i: longint;
procedure search(nodeid: longint; var f1, f2: longint);
var
i, v: longint;
begin
node[nodeid] := true;
inc(f1, value[nodeid]);
for i := 1 to tree[nodeid, 0] do
begin
v := tree[nodeid, i];
if not node[v] then
search(v, f2, f1)
end
end;
begin
fillchar(tree, sizeof(tree), 0);
fillchar(node, sizeof(node), 0);
for i := 1 to treesize[treeid] do
begin
with q[treeid, i] do
begin
aa := a;
bb := b
end;
inc(tree[aa, 0]);
tree[aa, tree[aa, 0]] := bb;
inc(tree[bb, 0]);
tree[bb, tree[bb, 0]] := aa
end;
c := 0;
d := 0;
search(aa, c, d);
if c > d then
inc(Sum, c)
else
inc(Sum, d)
end;
function findset(a: longint): longint;
begin
if ufs[a].up = 0 then
exit(a)
else
begin
ufs[a].up := findset(ufs[a].up);
exit(ufs[a].up)
end
end;
procedure union(a, b: longint);
var
x, y: longint;
begin
x := findset(a);
y := findset(b);
if ufs[x].size > ufs[y].size then
ufs[y].up := x
else if ufs[x].size < ufs[y].size then
ufs[x].up := y
else
begin
ufs[y].up := x;
inc(ufs[x].size)
end
end;
begin
fillchar(has, sizeof(has), 0);
fillchar(ufs, sizeof(ufs), 0);
fillchar(treesize, sizeof(treesize), 0);
readln(n, m);
for i := 1 to n do
begin
readln(value[i]);
ufs[i].size := 1
end;
for i := 1 to m do
begin
readln(a, b);
union(a, b);
tmps[i, 1] := a;
tmps[i, 2] := b;
has[a] := true;
has[b] := true
end;
count := 0;
for i := 1 to m do
begin
t := findset(tmps[i, 1]);
if ufs[t].treeid = 0 then
begin
inc(count);
ufs[t].treeid := count;
p := count
end
else
p := ufs[t].treeid;
inc(treesize[p]);
with q[p, treesize[p]] do
begin
a := tmps[i, 1];
b := tmps[i, 2]
end
end;
Sum := 0;
for i := 1 to n do
if not has[i] then
inc(Sum, value[i]);
for i := 1 to count do
dotree(i);
writeln(Sum)
end.
不用这么麻烦,两个数组(买,不买)。
递归解决伪代码:
max{当前点,买}=max{儿子,不买}+value{当前点};
max{当前点,不买}=max{max{儿子,买},max{儿子,不买}}。