PID188 / 购物问题
题目描述

由于换季,商场推出优惠活动,以超低价格出售若干种商品。但是商场为避免过分亏本,规定某些商品不能同时购买,而且每种超低价商品只能买一件。身为顾客的你想获得最大的实惠,也就是争取节省最多的钱。经过仔细研究,我们发现商场出售的超低价商品中,不存在以下这种情况:n(n>=3)种商品C1,C2,C3,……,Cn,其中Ci和Ci+1是不能同时购买的(i=1,2,……,n-1),而且C1和Cn也不能同时购买。

请编程计算可以接生的最大金额数。

输入格式

第一行两个整数K,M(1<=K<=1000),其中K表示超低价商品数,K种商品的编号依次为1,2,3,……,K;M表示不能同时购买的商品对数。

接下来K行,第i行有一个整数Xi表示购买编号为i的商品可以节省的金额(1<=Xi<=100)。

再接下来M行,每行两个数A,B,表示A和B不能同时购买,1<=A,B<=K,A≠B。

输出格式

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

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论