题意：有一个n * n的棋盘，每个棋盘有某些矩形区域被染成了黑色（这些矩形区域有可能相交），问把所有黑色区域染成白色的最小花费是多少？你每次可以选择把一个矩形区域染成白色，花费是染色的矩形区域长和宽的最小值。
思路：容易发现，假设一个矩形的坐标是(l1, r1, l2, r2)，假设(l2 - l1 < r2 - r1), 那么我们把r1和r2变成1和n对答案不会有影响。那么，我们发现问题转化为了选最少的行和列使得所有的黑色区域被覆盖，换句话说，就是所有的点至少被一个行货列所覆盖。我们把行看成左边的点，列看成右边的点，黑色的点看成边，那么这个问题就变成了求二分图的最小点覆盖。但是直接用二分图做边数点数会很大，所有我们可以离散化之后变成求网络流的最大流。
代码：
#include <bits/stdc++.h>
#define pii pair<int, int>
#define LL long long
#define INF 1e18
using namespace std;
const int maxm = 100100;
const int maxn = 510;
bool v[310][310];
int head[maxn], Next[maxm * 6], ver[maxm * 6], tot = 1;
int d[maxn], s ,t;
LL edge[maxm * 6];
void add(int x, int y, LL z) {
ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot;
ver[++tot] = x, edge[tot] = 0, Next[tot] = head[y], head[y] = tot;
}
queue<int> q;
bool bfs() {
memset(d, 0, sizeof(d));
while(q.size()) q.pop();
q.push(s), d[s] = 1;
while(q.size()) {
int x = q.front();
q.pop();
for (int i = head[x]; i; i = Next[i]) {
if(edge[i] && !d[ver[i]]) {
q.push(ver[i]);
d[ver[i]] = d[x] + 1;
if(ver[i] == t) return 1;
}
}
}
return 0;
}
LL dinic(int x, LL flow) {
if(x == t) return flow;
LL rest = flow, k;
for (int i = head[x]; i && rest; i = Next[i]) {
if(edge[i] && d[ver[i]] == d[x] + 1) {
k = dinic(ver[i], min(rest, edge[i]));
if(!k) d[ver[i]] = 0;
edge[i] -= k;
edge[i ^ 1] += k;
rest -= k;
}
}
return flow - rest;
}
vector<int> X, Y;
vector<pii> L, R;
int main() {
int n, m, l1, r1, l2, r2, sz;
scanf("%d%d", &n, &m);
X.push_back(0), X.push_back(n);
Y.push_back(0), Y.push_back(n);
for (int i = 1; i <= m; i++) {
scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
l1--, r1--;
L.push_back(make_pair(l1, r1));
R.push_back(make_pair(l2, r2));
X.push_back(l1), X.push_back(l2);
Y.push_back(r1), Y.push_back(r2);
}
sort(X.begin(), X.end());
sort(Y.begin(), Y.end());
sz = unique(X.begin(), X.end()) - X.begin();
while(X.size() > sz) X.pop_back();
sz = unique(Y.begin(), Y.end()) - Y.begin();
while(Y.size() > sz) Y.pop_back();
s = 210, t = 211;
for (int i = 0; i < X.size() - 1; i++) {
add(s, i, X[i + 1] - X[i]);
}
for (int i = 0; i < Y.size() - 1; i++) {
add(i + X.size(), t, Y[i + 1] - Y[i]);
}
for (int i = 0; i < m; i++) {
l1 = lower_bound(X.begin(), X.end(), L[i].first) - X.begin();
r1 = lower_bound(Y.begin(), Y.end(), L[i].second) - Y.begin();
l2 = lower_bound(X.begin(), X.end(), R[i].first) - X.begin();
r2 = lower_bound(Y.begin(), Y.end(), R[i].second) - Y.begin();
for (int i = l1; i < l2; i++) {
for (int j = r1; j < r2; j++) {
v[i][j] = 1;
}
}
}
for (int i = 0; i < X.size() - 1; i++) {
for (int j = 0; j < Y.size() - 1; j++) {
if(v[i][j]) {
add(i, j + X.size(), INF);
}
}
}
LL flow = 0, maxflow = 0;
while(bfs())
while(flow = dinic(s, INF)) maxflow += flow;
printf("%lld
", maxflow);
}