题意

给一个矩阵增加高度\(x\)的代价是\(x\),每个矩阵位置可以向四个相邻位置切高度小于等于当前位置的地方移动,求最小的代价,使得起点到终点不联通。

分析

一看就是最小割模型,于是考虑建图。

考虑把每一个点拆成若干个点:

  • 四相邻的位置按照需要花费的代价排序后加边,例如下面

  • 源点\(S\)连起点
  • 连向汇点\(T\)的就不是终点了,因为要求终点不能修改,所以我们需要将能够走到终点的点直接连向汇点\(T\),防止终点的高度发生更改

另外就是处理\(-1\)的情况,如果直接进图去跑,可能会死循环

显然\(-1\)只有两种情况:

  • 起点与终点重合
  • 起点与终点相邻,且起点能够达到终点

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注