P5169: 买鱼方案 -训练套题T7T1
传统题
1.000s
时间限制
128MB
内存限制
4 提交
4 解决
【题目描述】
1.买鱼方案(fish.pas)
【问题描述】
对于每种鱼，每个人最多买一条，并且有些鱼不能一起买，因为他们之间会互相争斗吞食。现在资金有限，希望买最多的鱼，如果有多个方案都能买最多的鱼，输出花费资金最多的方案。
【输入格式】
第一行两个正整数M（M<=1000）和N(N<=30)，分别表示资金和鱼的种类数。
以下N行，每行两个正整数，S（1<=S<=N）和T(T<=1000)，分别表示某种鱼的编号和价格。
接下来每行有两个整数数P和Q。当P，Q均大于0时，表示P，Q不能共处，当P，Q均等于0时，表示输入文件的结束。
【输出格式】
第一行两个正整数X,Y，分别表示所买鱼的条数和总花费。接下来X行，每行一个正整数，表示所买鱼的编号，编号按升序排列输出。若存在多解，只需要输出其中的一种。
【输入样例】
170 7
1 70
2 50
3 30
4 40
5 40
6 30
7 20
1 4
1 7
3 4
3 5
5 7
6 7
0 0
【输出样例】
4
160
2
4
5
6
【输入】
【提示】
HJF:
可以把鱼看成一个定点，把每个定点所代表的鱼的价值作为他的权，鱼和鱼之间如果不能共处则在他们之间连一条边，构成了一个图，题目要求其实就是一个顶点的子集，该子集中任意两个定点之间不存在边相连，而且他在所有满足这个要求的子集中在顶点数最多的前提下权最大。
由于不能通过数学关系求出这样一个子集，因此采用搜索策略。在一个图上搜索一个顶点的子集其实只要尝试每个顶点是否属于该子集。