二分图的最大匹配：匈牙利算法

int n1, n2;
int h[N], next_pos[N], e[N], idx;
int match[N];
bool st[N];
bool find(int x){
	for (int i = h[x]; i; i = next_pos[i]){
		int j = e[i];
		if (!st[j]){
			st[j] = true;
			if (!match[j] || find(match[j])){
				match[j] = x;
				return true;
			}
		}
	}
	return false;
}
int ans = 0;
for (int i = 1; i <= n1; i++){
	memset(st, false, sizeof st);
	if (find(i)){ ans++; }
}

（1）将集合视为点集，求点集的二分图最大匹配（只保存单向）

#include<iostream>
#include<cstring>
using namespace std;
const int N = 110;
int n, m;
int g[N][N];//存放棋盘的删除点
bool st[N][N];
typedef pair<int, int>PII;
PII ret[N][N];
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
bool find(PII x){//判断点x作为未被匹配的点出发是否存在增广路径
	for (int i = 0; i < 4; i++){
		int a = x.first + dx[i]; int b = x.second + dy[i];
		if (a <= 0 || a>n || b <= 0 || b > n || g[a][b] || st[a][b]){
			continue;
		}
		st[a][b] = true;
		if (ret[a][b].first == 0 || fin...