P1646 [国家集训队] happiness 最后更新于 2025-05-01 17:29:40

有点神的流题。 根据题面，第一反应是 dp，但是你发现这个额外贡献四面八方都有，而且怎么看怎么有后效性，那不炸完了！既然 dp 不行，贪心也贪不动，还没有什么神秘的性质，那这种题就只有考虑建模成流了。 你发现直接构建最大流等于答案的图是比较困难的，那就考虑转化成总和减去最小割。 先将 $s \to (i, j) \to t$ 的基本路径构建出来，就是 $s$ 向 $(i, j)$ 连流量为 $w_{文}$ 的边，然后 $(i, j)$ 向 $t$ 连 $w_{理}$ 的边。那么总流量就是 $\min(w_{文}, w_{理})$，也就是我们要抛弃的贡献。 接下来是额外贡献。以 $(i, j), (i + 1, j)$ 都选文为例。考虑建一个新的点 $x$，然后 $s$ 向 $x$ 连 $w$ 的边，$x$ 分别向 $(i, j), (i + 1, j)$ 连 $\infin$ 的边。 此时如果 $(i, j)$ 都 $(i + 1, j)$ 选了文科，意味着 $(i, j)$ 或者 $(i + 1, j)$ 到 $t$ 的那条路满流了，我们就会把 $(i, j) \to t$ 和 $(i + 1, j) \to t$ 的边都割掉。 求最小割直接上 dinic 即可。 总复杂度是 $\mathcal O(n ^ 3 m ^ 3)$。