100 #P1119. *【网络流(难度:S7)】牛挤奶

*【网络流(难度:S7)】牛挤奶

【题意】

FJ把 KK 个挤奶机搬进了住着 CC 头奶牛的牧场。

挤奶机的编号为 11KK ,奶牛的编号为 K+1K+1K+CK+C

每台挤奶机每天最多服务 MM 头奶牛。

求一种分配方案, 使得走得最远的奶牛走过的距离最小,输出此距离。

【输入格式】

第一行是三个整数 KCM1K30,1C200,1M15K,C,M(1≤K≤30,1≤C≤200,1≤M≤15)

接下来是一个 K+C×K+C(K+C)×(K+C) 的距离矩阵。矩阵元素为正并不超200。距离为0表示两个点之间无边存在。

【输出格式】

输出一个整数,即走得最远的奶牛走过的距离的最小化值。

【样例输入】

2 3 2
0 3 2 1 1
3 0 3 2 0
2 3 0 1 0
1 2 1 0 2
1 0 0 2 0

【样例输出】

2