AcWing 372的棋盘覆盖问题利用二分图和匈牙利算法解决
发布时间
阅读量：
阅读量
AcWing 372. 棋盘覆盖
匈牙利算法（亦称渣男算法）：将每一个格子视为图中的节点，并在各节点之间建立连接边，从而构成一张图。随后，对该图实施二分匹配操作，以确定其中所能形成的最大匹配点对数量。
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int, int>PII;
const int N = 105;
bool g[N][N]; //记录这条边能不能用
int n, m;
PII pei[N][N]; //记录这个点所匹配的点是什么
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
bool st[N][N];
bool find(int xx, int yy){ //给xx、yy找对象
for(int i = 0; i < 4; i ++ ){
int a = xx + dx[i]全部评论 (0)
还没有任何评论哟~