3246. 引水入城
2026-08-13
题解
第一反应肯定是网络流,直接进行网络流建模后数据范围不允许,考虑转化。
我们发现,根据最大流最小割定理,求最大流相当于求最小割,考虑刻画最小割形状。
不难发现,一列中肯定存在一个位置 (i,j),使得其上面的格子都属于源点 S,下面的格子都属于汇点 T。
证明
注意到如果存在格子 (i,j) 在 T,且 (i+1,j) 在 S,那么它们之间的边容量为 +∞,会被算进最小割里,错误。
接下来考虑设计一个 DP:f[j][k] 表示当前处理到第 j 列,并且分割点为 (j,k)∈S,(j,k+1)∈T,所以纵向代价为 c[k][j],横向代价为 ∑i=min(kj,kj+1)max(kj,kj+1)r[i][j]。
所以 DP 转移为:
f[j+1][k]=c[k][j]+iminf[j][i]+x=min(i,k)∑max(i,k)r[x][j]
