如果不是从费用流区做这个题几乎不会想到用费用流
点有权值很容易想到拆点
问题是求最大sum ... 把权值取负 这样最小费用流的相反数就是最大sum
源点S汇点T k为移动次数
矩阵中的点拆成入点出点 入点到出点连： 一个1容量，-1*点权费用； 一个k容量，0费用 两条边。
这样能保证只在第一次经过点时获得点的权值，并且可以多次经过一个点
矩阵中的点：出点连向下面和右面的点 容量k，费用0
S连1，1的点 容量k费用0 n，n的点连T，容量k费用0
虽然费用是负的 但是没有成负圈 经测试费用流成功ac...
int main(){// 1, n*n in, 1+n*n, n*n+n*n out
int t;
//scanf("%d", &t);
t = ;
while(t--){
memset(head, -, sizeof head);
tot = ;
int n, k;
scanf("%d%d", &n, &k);
for(int i = ; i <= n; i++){
for(int j = ; j <= n; j++){
int tmp;
scanf("%d", &tmp);
addedge(n*(i-)+j, n*(i-)+j+n*n, , -tmp);
addedge(n*(i-)+j, n*(i-)+j+n*n, k, );
if(i != n)
addedge(n*(i-)+j+n*n, n*(i-)+j+n, k, ); //down
if(j != n)
addedge(n*(i-)+j+n*n, n*(i-)+j+, k, ); //right
}
}
addedge(, , k, );
addedge(*n*n, *n*n+, k, );
MCMF(, *n*n+);
printf("%d\n", -ans);
}
return ;
}