HDU8082 老猫下山

· · 个人记录

我是出题人。

Fun fact：这题由 ZJCPC 2025 热身赛 C 题改编，它是本题在 k=2,a_{i,j}=0 下的构造方案版本。

我们先不管这个成本，先来看有解性问题。假设我们最终想要所有数都等于 $x$，由此我们可以直接求出每个位置（在模 $k$ 意义下）需要被经过的次数 $t_{i,j}=x-s_{i,j}$。我们接下来证明一个引理。 #### 引理：在所有 $x\in[0,k-1]$ 中，最多只有一个 $x$ 能够导出一个解。 证明：我们考虑 $t_{1,1},t_{1,2},t_{2,1}$ 这三个数。 显然，格子 $(1,2)$ 和 $(2,1)$ 被经过的唯一来源是从 $(1,1)$ 走向它们。因此经过 $(1,1)$ 的次数一定等于 经过 $(1,2)$ 和 $(2,1)$ 的次数之和。换言之，$t_{1,1}\equiv t_{1,2}+t_{2,1} \pmod k$。由于我们刚刚是在模 $k$ 意义下定义的 $t$，我们最好还是用同余表示这个关系。 也就是说，有解的一个必要条件是 $t_{1,1}\equiv t_{1,2}+t_{2,1} \pmod k$，也即 $x-s_{1,1}\equiv x-s_{1,2}+x-s_{2,1} \pmod k$。由此可以解出一个唯一的 $x$。 此时我们获得了模意义下每个格子应该被经过多少次，现在考虑如何判断这个 $x$ 是否合法。把网格图转化为一张 DAG，其中边只能向下或向右走。我们现在开始关注一条往右或往下的 **边** 被经过的次数。以下的计算均在模 $k$ 意义下进行。 首先观察第一行。每个格子如果被经过，一定只能从其左边一个格子过来。因此第一行所有向右的边需要被经过的次数是能够直接确定的。又由于第一行的所有格子除了向右走（次数已经确定）只能向下走了，因此向下走的次数也已经能够确定。 向下走的次数又间接确定了第二行中所有向右的边的次数，因为这些格子被经过的来源要么是从上面来（次数已知），要么从左边来。重复这个过程我们就可以地推确定所有向右走和向下走的边所需要经过的次数。 递推的过程中检查是否合法即可。 现在我们已经能够确定每条边（在模意义下）会被经过多少次，接下来求解答案。走一条路径这种操作很像带费用的流量行进，我们建立费用流模型，尝试使用最小费用流解决。 整理一下我们现在有的限制： - 每条边被经过的次数是 $pk+q$，其中 $q$ 已经由递推确定。 - 除了 $(1,1),(n,m)$，其余点需满足流量平衡。 如何处理呢？对于一个点，假设它的入边（从左边和上面过来的边）的次数分别是 $ak+p,bk+q$，出边（向右和向下走的边）的次数是 $ck+r,dk+s$，那么此时流量平衡就能被写成： $$(a+b)k+p+q=(c+d)k+r+s$$ 其中 $p,q,r,s$ 应该满足 $p+q\equiv r+s \pmod k$ ，这是由递推决定的。将上面的等式右侧的 $r+s$ 移到左边并除整体以 $k$，我们能够重写流量平衡为 $a+b+\delta=c+d$，其中 $\delta=(p+q-r-s)/k\in\{-1,0,1\}$（边界上的点可能会缺少入边/出边，但是不影响 $\delta$ 的计算）。 建立源汇点 $S,T$，$S$ 连向 $(1,1)$，流量无限，费用为 $a_{1,1}$；$(n,m)$ 连向 $T$，流量无限，费用为 $0$。网格图中的所有边流量无限，费用为这条边指向的格子的成本。这张图足以处理所有 $\delta=0$ 的情况。如果某个点 $\delta>0$，说明这个点会凭空吃掉 1 的流量，在这个点和 $T$ 之间连边并强制流量必须为 $\delta$，费用为 $0$；如果某个点 $\delta<0$，说明这个点会凭空产生 1 的流量，在 $S$ 和这个点之间连边并强制流量必须为 $-\delta$，费用为 $0$。这样就能描述每个点的流量平衡了。 “强制”这一条件可以看作上下界。跑上下界有源汇最小费用可行流即可。注意这一遍跑出来的费用需要乘以 $k$。这里其实只处理了 $pk+q$ 中的 $p$ 的平衡问题，还需要加上所有的 $q$ 带来的费用，这是平凡的。