1154. 【GDOI2003】购物 (Standard IO)Time Limits: 1000 ms Memory Limits: 65536 KB Detailed Limits
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
分析：
对于没有与它有不可购买关系的物品，我们视它必取。对于有的有不可购买关系的点，我们可以以它为根，以不可购买的关系来建立一棵树，用f[i,1]表示不取这个点,f[i,2]取这个点，对于一棵树里的点都要标记一遍，不然可能会重复建树导致答案错误。那么便变成了很多颗树。对于一棵树，统计出它根节点的max(f[root,1],f[root,2]),再加入答案ans中即可。f[root,1]=f[root,1]+max(f[son1,1],f[son1,2]);f[root,2]:=f[root,2]:=f[root,2]+f[son1,1];注意枚举完儿子个数以后f[root,2]:=f[root,2]+a[root];并且要从底部开始做。
代码：
const maxn=1000; var list,son:array [0..maxn,0..maxn] of longint; f:array [0..maxn,1..2] of longint; flag:array [0..maxn] of boolean; a:array [0..maxn] of longint; ans,x,y,k,m:longint; procedure init; var i:longint; begin readln(k,m); for i:=1 to k do readln(a[i]); for i:=1 to m do begin readln(x,y); inc(list[x,0]); list[x,list[x,0]]:=y; inc(list[y,0]); list[y,list[y,0]]:=x; end; end; procedure buildtree(x:longint); var i:longint; begin flag[x]:=true; for i:=1 to list[x,0] do if flag[list[x,i]]=false then begin inc(son[x,0]); son[x,son[x,0]]:=list[x,i]; buildtree(list[x,i]); end; end; function max(x,y:longint):longint; begin if x>y then exit(x) else exit(y); end; procedure dp(x:longint); var i,j:longint; begin if son[x,0]>0 then begin for i:=1 to son[x,0] do dp(son[x,i]); for i:=1 to son[x,0] do begin j:=son[x,i]; f[x,1]:=f[x,1]+max(f[j,1],f[j,2]); f[x,2]:=f[x,2]+f[j,1]; end; f[x,2]:=f[x,2]+a[x]; end else begin f[x,1]:=0; f[x,2]:=a[x]; end; end; procedure main; var i:longint; begin for i:=1 to k do if list[i,0]=0 then inc(ans,a[i]) else if flag[i]=false then begin buildtree(i); dp(i); ans:=ans+max(f[i,1],f[i,2]); end; writeln(ans); end; begin assign(input,'shop.in');reset(input); assign(output,'shop.out');rewrite(output); init; main; close(input);close(output); end.
