自动搬运

查看原文

来自洛谷，原作者为

	dspt その日まで 飛ばあげ 嵐がさわってゆくまで

搬运于2025-08-24 23:01:57，当前版本为作者最后更新于2024-08-11 21:36:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本题来源是 Gym 105139C，官方题解链接。这是本场的防 AK 题，当然也是道思路很巧妙的网络流建模问题。

我们考虑对多边形 $P$ 求出它最少不交矩形覆盖，那么答案就是图上所有多边形的最少不交矩形覆盖和。

约定：记 ∟ 表示直角，2∟表示平角，3∟ 表示凹角（270°的角）。

引理 1：分割线与原图形的边不重合。证明显然。

引理 2：每条分割线的两个端点至少有一个是 3∟，并且没有一个是 ∟。

如果端点是 ∟，那么必然与原图形的边重合，不符合结论 1。那么剩下两个端点的情况就是：两个 2∟、一个 3∟ 一个 2∟、两个 3∟。

如果两个端点均为 2∟，容易发现这条分割线没有意义。即对于任意一组包含这条分割线的合法划分，去掉这条分割线仍然合法。除掉这种情况，剩下的情况中至少有一个端点为 3∟。

引理 3：任意两条分割线，要么不交，要么交于端点。

考虑平行于垂直两种情况。平行必然不交，垂直的话，两条分割线构成了一个十字形，可以发现这个十字形的四边必然存在一边是毫无必要的，把那条边去掉，答案不会更劣。

假设我们已经得知了一组合法划分，我们怎么计算出划分了有多少个矩形呢？我们可以使用内角和计算。划分后图形的内角和除以 4∟ 就是矩形数量。

但是我们在划分的过程中会让原图形的内角和改变，具体而言：

1. 分割 2∟：内角和增大了 2∟
2. 分割 3∟ 一次：内角和减小了 2∟
3. 分割 3∟ 两次：内角和不变

考虑前面所说的分割线的两种情况：

1. 分割 2∟ 和 3∟，内角和不受影响。
2. 分割 3∟ 和 3∟，内角和减少了 4∟。

值得注意的是，3∟ 被分割后会变成 2∟。

我们称端点为 3∟ 的分割线是好分割线。

引理 4：任意合法分割内角和减少量等于不相交的好分割线条数乘以 4∟。

合法方案的必要条件：所有 3∟ 都至少被分割一次。

如果 3∟ 被好分割线分割，那么必然可以带来 2∟ 的贡献。那么这些不相交好分割线每条就会带来 4∟ 的贡献。对于其它没有被好分割线分割的 3∟，从它连出去的分割线必然无法分割另一个 3∟，只能分割 2∟。而这些分割线不会对答案产生影响。

于是做法就显而易见了：离散化，求出多边形的内角和。

对于每个 3∟，它在水平方向和竖直方向各至多有一个 3∟ 与其匹配，换言之，每个 3∟ 的水平 / 竖直好分割线都只有一条。我们把这些好分割线看作点，经过公共点的水平好分割线与竖直好分割线连边（只能选一条），可以建成一张二分图，不相交的好分割线条数 = 最大独立集 = 二分图总点数 - 最大匹配。

这张二分图的点数是原多边形的点数级别的，需要用最大流进行匹配。最后用原多边形内角和除以 4∟ 再减去最大独立集就是答案。