LGP7916 [CSP-S 2021] 交通规划 学习笔记

LGP7916 [CSP-S 2021] 交通规划 学习笔记

Luogu Link

前言

仔细读了十遍题面，硬是一个字都没和交通规划扯上关系，很有可能是出题人编了一个故事，发现编不下去了。——\(\texttt{OMG-WC}\)。

题意简述

有一个 \(n\times m\) 个点的网格图。对于这个网格图的最外侧，有些网格线会延伸一格到一个附加点上。所有边均有非负整数边权。

给定每个附加点的颜色（橙或蓝），你可以随意给网格内那 \(n\times m\) 个点染色，染色方案的代价为所有两端点异色的边的边权和。问最小的代价。

\(2\le n,m\le 500\)，\(T\le 50\)，\(k_i\) 均在合法范围内。

特别地，有 \(45\text{pts}\) 部分分满足 \(k_i\le 2\)。

做法解析

不妨从 \(k_i\le 2\) 的部分分考虑。显然，如果附加点颜色全部一致，那答案就是 \(0\)。那么，当 \(k_i=2\) 且两个附加点异色时，答案是一个最小割。参考 \(\texttt{LGP4001}\)、\(\texttt{LGP2604}\) 等。

那么 \(k_i>2\) 的时候呢？此时的答案形态……。

我们发现，如果两个相邻的附加点颜色一致，那它们之间肯定没有隔阂（就是必然处于一个同色连通块中）。

所以我们不妨把相同颜色的点“缩在一起”，然后再次从转化为对偶图最短路的视角来考虑。我们发现此时最小割之和在对偶图上表现为：若干个源汇点（被分为两种颜色，相邻则异色）需要和异色点完成两两的括号匹配，每一对匹配的代价为我们在对偶图上跑出来的最短路，这样的代价和。

你可能会问：括号匹配肯定是偶数个点做，为什么一定有偶数个对偶图上的源汇点呢？答：因为对于原图来说最外侧同色的连续段肯定为偶数。连续段如果是奇数等价于必有两段相邻且同色，那么它们应该被缩成一段。

所以原理就是这样。你求出这些对偶图上异色源汇点两两的最短路之后，跑一个 \(O(k^3)\) 的括号匹配 \(\texttt{DP}\) 即可。

代码实现