P83835

Kroničan

难度 6 级 初三 动态规划入门 状态压缩
讨论 统计 2通过 3提交 66.7%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

Mislav 有 N 个玻璃杯,从 1\sim N 编号,每个玻璃杯中都有一定的水。你需要通过倒水(将某个杯子中的水倒入另一个杯子),使这些杯子中只有 K 个有水。

已知将第 i 号玻璃杯中的水倒入第 j 号,需要消耗 Cij 的代价。Mislav 想知道,经过倒水后满足只有 K 个(或更少)玻璃杯中有水时,消耗的代价总和的最小值。

输入

第一行包含两个正整数,N,K。

接下来 N 行,每行包含 N 个非负整数 Cij。第 i 行 j 列的数表示从玻璃杯 i 倒水到玻璃杯 j 需要付出的代价。保证 Cii 一定是 0。

输出

输出 Mislav 达成目标需要付出的最小代价和。

样例

样例 1
输入
3 3
0 1 1
1 0 1
1 1 0
输出
0
样例 2
输入
3 2
0 1 1
1 0 1
1 1 0
输出
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
输出
5

提示

说明/提示

样例 1 解释

Mislav 不需要倒水。代价和是 0。

样例 2 解释

Mislav 需要将任意一个玻璃杯中的水倒入任何其他玻璃杯中,使其满足只有两个玻璃杯中有水。代价和为 1。

样例 3 解释

Mislav 可以将水从玻璃杯 4 倒入玻璃杯 3,然后将玻璃杯 3 中的水倒入玻璃杯 5,最后将玻璃杯 1 中的水倒入玻璃杯 5。总共付出代价和为 1+2+2=5。

数据规模与约定

对于 40\% 的数据,满足 N\le 10。

对于 100\% 的数据,满足 1\le K\le N\le 20,C_{i,j}\le10^5

来源

COCI

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交