首页 > 题解 > bzoj 4108 [Wf2015]Catering

bzoj 4108 [Wf2015]Catering

Description

有一家装备出租公司收到了按照时间顺序排列的n个请求.

这家公司有k个搬运工.每个搬运工可以搬着一套装备按时间顺序去满足一些请求.一个搬运工从第i个请求的位置把东西搬到第j个请求的位置需要一些费用.公司的编号是1,请求的编号是2到n+1.所有搬运工必需从公司出发.
求满足所有请求所需的最小搬运费用.

Input

有可能有多组数据(我也不知道).

第一行两个正整数n,k.
接下来n行,第i行有n-i+1个数.第j个数表示把装备从i搬到i+j的花费.

Output

输出一行一个整数表示最小花费.

Sample Input

1 1

10

Sample Output

10

HINT

n, k <= 100;

花费 <= 1,000,000

题解

将2-n+1拆点xi,yi
s->1,[0,k],0
1->xi,[0,inf],0
yi->t,[0,inf],0
xi->yi,[1,1],0
对于给出的费用,若i->j的费用为c
yi->xj,[0,inf],c


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×