【BZOJ3144】【HNOI2013】切糕

听说这是个很经典的最小割模型。。

问题为,在一个矩阵中,每个变量的数值不同代价不同,求在相邻变量的差不超过\(D\)的情况下矩阵的最小代价。

从对于每一个格子,将它的所有取值从源点一直到汇点串起来,边权为取某个数的代价。那么显然对于一个格子,它的最小割即为最小权值。问题在于如何满足两个格子间的约束关系。

只需要从每个格子的每个\(k\)取值处向相邻格子的\(k-D\)取值处连边即可。

可以发现,这样做之后,若当前格子选择了\(k\),那么周围的格子不能选小于\(k-D\)的边,不然就会出现增广路。

说点什么

您将是第一位评论人!

提醒
wpDiscuz