算法
(拆点、最大流) $O(E\sqrt{V})$
初看题面会以为可以把每个卡片对应的 $x$ 和 $y$ 单独处理,但 $(x, y)$ 必须在矩形内。
- 记网格内的点的坐标为 $(R_i, C_i)$
- 可以把每个待处理的卡片拆分为两个点 $u$ 和 $v$,这两个点之间连一条边,权值为 $1$,这样就保证了一个卡片不会被放在网格内的多个点上。然后对于每个矩形内的点的横坐标,都和卡片第一个点连边,以及卡片第二个点分别和每个矩形内部点的纵坐标连边。然后引入一个超级源点 $S$,把他与网格的每行的横坐标连边,再引入一个超级汇点 $T$,把他与网格的每列的纵坐标连边。
- 边的方向为 $S \to R_u \to u \to v \to C_v \to T$,容量全都为 $1$
- 如图所示,每个 $S \to T$ 的路径都表示一张卡片放入网格中的方案
- 所以,只要计算该图中的最大流即可。
- 类题: Dining
C++ 代码
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
int main() {
int h, w, n;
cin >> h >> w >> n;
int sv = h + w + n * 2, tv = sv + 1;
mf_graph<int> g(tv + 1);
rep(i, h) g.add_edge(sv, i, 1);
rep(i, w) g.add_edge(h + i, tv, 1);
rep(i, n) {
int a, b, c, d;
cin >> a >> b >> c >> d;
--a; --b;
int v = h + w + i;
g.add_edge(v, n + v, 1);
for (int j = a; j < c; ++j) g.add_edge(j, v, 1);
for (int j = b; j < d; ++j) g.add_edge(n + v, h + j, 1);
}
int ans = g.flow(sv, tv);
cout << ans << '\n';
return 0;
}