同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

2078_AL083最小重量机器设计问题

2022-5-16 18:18| 发布者: Hocassian| 查看: 55| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-3-89504305387300-Problem List-采集的数据-后羿采集器.html

Pro.ID

2078

Title

AL083 最小重量机器设计问题

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=2078

AC

Submit

Ratio

0.00%

时间&空间限制

Time Limit: 1000/500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

描述

设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。设 w_ij是从供应商j处购得的部件i的重量，c_ij是相应的价格。

对于给定的机器部件重量和机器部件价格，设计一个优先队列式分支限界法，计算总价格不超过d的最小重量机器设计。

输入

输入第一行有三个正整数n ，m和d。接下来的2n行，每行n个数。前n行是c，后n行是w。

输出

Description

设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。设 w_ij是从供应商j处购得的部件i的重量，c_ij是相应的价格。

对于给定的机器部件重量和机器部件价格，设计一个优先队列式分支限界法，计算总价格不超过d的最小重量机器设计。

Input

输入第一行有三个正整数n ，m和d。接下来的2n行，每行n个数。前n行是c，后n行是w。

Output

输出最小重量，以及每个部件的供应商。

Sample Input

3 3 4
1 2 3
3 2 1
2 2 2
1 2 3
3 2 1
2 2 2

Sample Output

4
1 3 1

Hint

要求用分支限界法

Author

John

样例输入