1154. 【GDOI2003】购物 (Standard IO)

Description

GDOI商场推出优惠活动，以超低价出售若干种商品。但是，商场为避免过分亏本，规定某些商品不能同时购买，而且每种超低价商品只能买一件。身为顾客的你想获得最大的实惠，也就是争取节省最多的钱。经过仔细研究，发现商场出售的超低价商品中，不存在以下情况：n(n>=3)种商品C1,C2,…..,Cn,其中Ci,Ci+1是不能同时购买的(i=1,2…,n-1)并且C1, Cn也不能同时购买。编程计算可以节省的最大金额数。

Input

第一行两个整数K,M(1<=K<=1000).其中K表示超低价商品数。K种商品的编号依次为1,2,…,K。M表示不能同时购买的商品对数.接下来K行，第i行有一个整数Xi表示购买编号为i的商品可以节省的金额(1<=Xi<=100).再接下来M行，每行两个数A ,B,表示A和B不能同时购买，1<=A<=K,1<=B<=K,A<>B

Output

仅一个整数，表示能节省的最大金额数。

Sample Input

3 1 1 1 1 1 2

Sample Output

2

思路

把不能同时购买的物品相连，形成许多可树，对于每个点，如果选择这个点，那么最大金额为自身金额和每个子节点不选时的和，如果不选这个点，最大金额为每个子节点选和不选的最大值。
选择点i：f[i,1]:=f[i,1]+f[son1,0]+...+f[sonx,0];
不选择点i:f[i,0]:=f[i,0]+max(f[son1,0],f[son1,1])+...

vars:array[1..1000,1..2] of longint;f:array[1..1000,1..1000] of boolean;a:array[1..1000] of boolean;n,m:longint;
function max(x,y:longint):longint;
beginif x>y then exit(x)else exit(y);
end;
procedure xxoo(x:longint);
vari:longint;
beginfor i:=1 to n dobeginif (f[x,i])and(a[i]) thenbegina[i]:=false;xxoo(i);s[x,1]:=s[x,1]+s[i,0];s[x,0]:=s[x,0]+max(s[i,1],s[i,0]);end;end;
end;
vari,ans,x,y:longint;
beginreadln(n,m);for i:=1 to n dobeginreadln(s[i,1]);end;for i:=1 to m dobeginreadln(x,y);f[x,y]:=true;f[y,x]:=true;end;fillchar(a,sizeof(a),true);for i:=1 to n doif a[i] thenbegina[i]:=false;xxoo(i);ans:=ans+max(s[i,1],s[i,0]);end;writeln(ans);
end.