Description: 算法实验作业 3-3 购物问题
问题描述：
由于换季，某商场推出优惠活动，以超低价格出售若干种商品。但是，商场为避免过分
亏本，规定某些商品不能同时购买，而且每种超低价商品只能买一件。身为顾客的你想获得
最大的实惠，也就是争取节省最多的钱。经过仔细研究过，我们发现，商场出售的超低价商
品中，不存在以下这种情况：
n(3≤n)种商品 c1, c2, c3,…, cn，其中 ci和 ci+1是不能同时购买的（i=1, 2, …,n-1），而
且 c1和 cn也不能同时购买。
编程任务：
请编程计算可以节省的最大金额数。
数据输入：
第 1 行两个整数 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。
结果输出
输出计算出的能节省的最大金额数
To Search:
File list (Check if you may need any files):
shop
....\shop.cpp
Download