题意
有一张 $2 \times n$ 的网格图，你要从左上角 $\left(1, 1\right)$ 走到右下角 $\left(2, n\right)$。每条边有边权，并且有额外的 $m$ 条限制。每条限制形如：给定 $i, j, c$，如果同时走了 $\left(1, i\right)$ 到 $\left(1, i + 1\right)$ 和 $\left(2, j\right)$ 到 $\left(2, j + 1\right)$ 这两条边，那么你就需要额外 $c$ 的代价。求走过的边权和加上代价的最小值。
题解
考虑网络流。
相当于对每个 $i$，我们需要在 $\left(1, i\right)$ 到 $\left(1, i + 1\right)$ 与 $\left(2, i\right)$ 到 $\left(2, i + 1\right)$ 之间选择⼀个。选每⼀种需要⼀个代价，如果 $i$ 和 $i + 1$ 选择了不同的⾏，那么就需要额外付出 $\left(1, i + 1\right)$ 到 $\left(2, i + 1\right)$ 之间边的代价。这是一个最小割模型。而对于限制，在 $i, j$ 之间连一条边权为 $c$ 的边，表示如果同时走了 $\left(1, i\right)$ 到 $\left(1, i + 1\right)$ 和 $\left(2, j\right)$ 到 $\left(2, j + 1\right)$ 这两条边，那么就需要额外付出 $c$ 的代价把这条新边也割掉。