题目大意

有 $n$ 顶帐篷，第 $i$个帐篷位于点 $(x_i, y_i)$ 上，权值为 $w_i$。当且仅当 $x_i$ 和 $y_i$ 都是偶数时，帐篷 $i$ 才是重要的。除一些帐篷，使得对于每个剩余的重要帐篷 $(x, y)$，不存在另外 $3$ 个帐篷 $(x' _ 1, y' _ 1),(x' _ 2, y' _ 2)$ 和 $(x' _ 3, y' _ 3)$，使得以下两个条件都成立：

• $|x'_j-x|,|y'_j-y|\le 1$，对于所有 $j\in\{1,2,3\}$。

• 这四个帐篷形成一个平行四边形（或矩形），它的一条边平行于 $x$ 轴。

请将未移走的帐篷重量之和最大化，输出最大值。

其中数据范围满足，$1\le n\le 1000,-10^9\le x_i,y_i\le 10^9$。

思路

将节点的 $x_i,y_i$ 的奇偶性划分成 $A,B,C,D$ 四个集合，注意相邻集合在图中需要时可以满足 $\operatorname{dist}$ 为 $1$ 的。

容易发现对于一个不合法的四边形，一定满足四个帐篷之间的切比雪夫距离均为 $1$ 而且四个点分别属于 $A,B,C,D$ 四个集合。

每一种帐篷只有选择或者不选择，考虑使用最小割进行求解。

因为帐篷 $u$ 无法在最小割中被删除，考虑将 $u$ 拆为两个节点 $u_1,u_2$ 并用权值为 $w_u$ 的边链接 $u_1,u_2$，如果将边 $u_1\to u_2$ 删除，那么就意味着帐篷 $u$ 被放弃掉了。

考虑将集合编号相邻且在图上曼哈顿距离为 $1$ 的节点之间连边，具体的要将编号小的 $x_2$ 向集合编号较大的 $y_1$ 连边边权为 $inf$ 的边。

最后将 $A$ 集合内的所有点与 $S$ 连边，将 $D$ 集合内所有的点与 $T$ 连边，边权都是 $inf$。

显然，如果节点 $a,b,c,d$ 是不合法的帐篷，那么它们显然会被边权为 $inf$ 的边全部连接起来，那么只有割掉任意一条边权不为 $inf$ 的边才可以使 $S,T$ 不连通。根据上面的解释，这也就是放弃了一个帐篷。

时间复杂度为 $O(n^3)$，但是是网络流。

Submission #278324197 - Codeforces