A1344 | [COCI-2016_2017-contest3]#2 Kronican
来源COCI
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
Little Mislav owns N glasses of infinite volume, and each glass contains some water. Mislav wants to drink all the water, but he doesn’t want to drink from more than K glasses. What Mislav can do with the glasses is pour the total volume of water from one glass to another.
Unfortunately, it matters to Mislav what glass he picks, because not all glasses are equally distant to him. More precisely, the amount of effort it takes to pour water from glass labeled with i to glass labeled j is denoted with Cij..
Help Mislav and find the order of pouring the water from one glass to another such that the sum of effort is minimal.
Unfortunately, it matters to Mislav what glass he picks, because not all glasses are equally distant to him. More precisely, the amount of effort it takes to pour water from glass labeled with i to glass labeled j is denoted with Cij..
Help Mislav and find the order of pouring the water from one glass to another such that the sum of effort is minimal.
输入格式
The first line of input contains integers N, K (1 ≤ K ≤ N ≤ 20).
The following N lines contains N integers Cij (0 ≤ Cij ≤ 10^5 ). The i^th row and j^th column contains value Cij . It will hold that each Cii is equal to
0.
The following N lines contains N integers Cij (0 ≤ Cij ≤ 10^5 ). The i^th row and j^th column contains value Cij . It will hold that each Cii is equal to
0.
输出格式
Output the minimal effort needed for Mislav to achieve his goal.
输入输出样例
输入 #1
3 3 0 1 1 1 0 1 1 1 0
输出 #1
0
输入 #2
3 2 0 1 1 1 0 1 1 1 0
输出 #2
1
输入 #3
5 2 0 5 4 3 2 7 0 4 4 4 3 3 0 1 2 4 3 1 0 5 4 5 5 5 0
输出 #3
5
In test cases worth 40 points total, it will hold N ≤ 10.
Clarification of the first test case: Mislav doesn’t need to pour water in order to drink from at most 3
glasses.
Clarification of the second test case: Mislav must pour the water from precisely one (doesn’t matter
which) glass into any other glass in order to be left with only two glasses with water.
Clarification of the third test case: In order for Mislav to achieve the minimal solution of 5, he can
pour water from glass 4 to 3 (effort 1), then 3 -> 5 (effort 2), and finally, 1 -> 5 (effort 2). In total, 1 + 2 + 2
= 5 amount of effort.
Clarification of the first test case: Mislav doesn’t need to pour water in order to drink from at most 3
glasses.
Clarification of the second test case: Mislav must pour the water from precisely one (doesn’t matter
which) glass into any other glass in order to be left with only two glasses with water.
Clarification of the third test case: In order for Mislav to achieve the minimal solution of 5, he can
pour water from glass 4 to 3 (effort 1), then 3 -> 5 (effort 2), and finally, 1 -> 5 (effort 2). In total, 1 + 2 + 2
= 5 amount of effort.
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted