原作者：https://blog.csdn.net/KYJL888/article/details/106055942
1.二分图的基本知识点
二分图：简单来说图中的点可以被分为两组，并且使得所有边都跨越组的边界，这就是一个二分图。准确来说：把一个图的顶点划分为两个不相交集U和V，使得每一条边都分别连接U和V中的顶点。如果存在这样的划分，则此图为一个二分图。
图1是一个二分图，为了清晰我们都画成图2的形式。
匹配：$\color{blue} {在图论中，一个【匹配】是一个边都集合，其中任意两条边都没有公共顶点。} $例如，图3、图4中红色的边就是图2的匹配。
我们定义匹配点、匹配边、未匹配点、未匹配边，它们的含义非常显然。例如图3中1 4 5 7为匹配点，其他为未匹配点；1-5、4-7为匹配边，其他为非匹配边。
最大匹配：一个图中所有的匹配中，所含\(\color{green} {匹配边数最多的匹配，}\)称为这个图的最大匹配。图4是一个最大匹配，它包含4条匹配边。
求解最大匹配问题的一个算法是匈牙利算法，下面的概念都为这个算法服务。
交替路：从一个未匹配点出发（右），依次经过非匹配边、匹配边、非匹配边....形成的路径叫做交替路。
增广路：从一个未匹配点出发（右），走交替路，如果途径另一个未匹配点（出发的点不算），则这条交替路称为增广路（agumenting path）。例如，图5中的一条增广路如图6所示（图中的匹配点均用红色标出）：
增广路有一个重要特点：非匹配边比匹配边多一条。因此研究增广路的意义是改进匹配。只要把增广路中的匹配边和非匹配边的\(\color{green} {身份交换}\)即可。由于中间的匹配节点不存在与其他相连的匹配边，所以这样做不会破坏匹配的性质。交换后，图中的匹配边数目比原来多了1条。
我们可以通过不停找增广路来增加匹配中的匹配点和匹配边。找不到增广路时，达到最大匹配这就是（\(\color{red} {增广路定理}\)）。匈牙利算法便是这么做的
题目描述：
给定一个二分图 G，即分左右两部分，各部分之间的点没有边连接，要求选出一些边，使得这些边没有公共顶点，且边的数量最大。
学会怎么应用即可
模版
struct augment_path {
vector<vector<int> > g;
vector<int> pa; // 匹配
vector<int> pb;
vector<int> vis; // 访问
int n, m; // 两个点集中的顶点数量
int dfn; // 时间戳记
int res; // 匹配数
augment_path(int _n, int _m) : n(_n), m(_m) {
assert(0 <= n && 0 <= m);
pa = vector<int>(n, -1);
pb = vector<int>(m, -1);
vis = vector<int>(n);
g.resize(n);
res = 0;
dfn = 0;
}
void add(int from, int to) {
assert(0 <= from && from < n && 0 <= to && to < m);
g[from].push_back(to);
}
bool dfs(int v) {
vis[v] = dfn;
for (int u : g[v]) {
if (pb[u] == -1) {
pb[u] = v;
pa[v] = u;
return true;
}
}
for (int u : g[v]) {
if (vis[pb[u]] != dfn && dfs(pb[u])) {
pa[v] = u;
pb[u] = v;
return true;
}
}
return false;
}
int solve() {
while (true) {
dfn++;
int cnt = 0;
for (int i = 0; i < n; i++) {
if (pa[i] == -1 && dfs(i)) {
cnt++;
}
}
if (cnt == 0) {
break;
}
res += cnt;
}
return res;
}
};
来一个例题
C - 2D Plane 2N Points
1.用两重循环遍历所有的点，把合法的点放进去，相当于把这两个点连起来建立边，然后就是套上述点模版
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
int dx[]={0,1,-1,0};
int dy[]={-1,0,0,1};
struct augment_path {
vector<vector<int> > g;
vector<int> pa; // 匹配
vector<int> pb;
vector<int> vis; // 访问
int n, m; // 两个点集中的顶点数量
int dfn; // 时间戳记
int res; // 匹配数
augment_path(int _n, int _m) : n(_n), m(_m) {
assert(0 <= n && 0 <= m);
pa = vector<int>(n, -1);
pb = vector<int>(m, -1);
vis = vector<int>(n);
g.resize(n);
res = 0;
dfn = 0;
}
void add(int from, int to) {
assert(0 <= from && from < n && 0 <= to && to < m);
g[from].push_back(to);
}
bool dfs(int v) {
vis[v] = dfn;
for (int u : g[v]) {
if (pb[u] == -1) {
pb[u] = v;
pa[v] = u;
return true;
}
}
for (int u : g[v]) {
if (vis[pb[u]] != dfn && dfs(pb[u])) {
pa[v] = u;
pb[u] = v;
return true;
}
}
return false;
}
int solve() {
while (true) {
dfn++;
int cnt = 0;
for (int i = 0; i < n; i++) {
if (pa[i] == -1 && dfs(i)) {
cnt++;
}
}
if (cnt == 0) {
break;
}
res += cnt;
}
return res;
}
};
signed main()
{
ios::sync_with_stdio(0),cin.tie(0);
int n;cin>>n;
pii a[105],b[105];
for(int i=0;i<n;i++) cin>>a[i].x>>a[i].y;
for(int i=0;i<n;i++) cin>>b[i].x>>b[i].y;
augment_path ans(n,n);
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(a[i].x<b[j].x&&a[i].y<b[j].y) ans.add(i,j);
}
}
cout<<ans.solve()<<endl;
return 0;
}