棋盘覆盖
题意
给定一个 N 行 N 列的棋盘，已知某些格子禁止放置。
求最多能往棋盘上放多少块的长度为 2、宽度为 1 的骨牌，骨牌的边界与格线重合（骨牌占用两个格子），并且任意两张骨牌都不重叠。
思路
我们将棋盘上的方格看作点，骨牌看作两个点之间的边，那么问题就可以抽象成最多能选取多少条边，使得每条边没有公共顶点。如图：
这时 棋盘还不能看作二分图，不能使用匈牙利算法。
接下来，我们可以将每个点染色，
将所有点分成两部分：坐标和为奇数的 和 坐标和为偶数的，可以发现，任意一个符合条件的骨牌占用的两个格子一定属于不同种类。
那么我们就可以将问题最终抽象成：在一个二分图中求最大匹配，直接使用匈牙利算法即可
代码
// Author：zzqwtcc // Problem: 棋盘覆盖 // Contest: AcWing // Time：2021-10-06 22:52:50 // URL: https://www.acwing.com/problem/content/374/ // Memory Limit: 64 MB // Time Limit: 1000 ms #include<bits/stdc++.h> #include<unordered_map> // #define int long long #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3f #define mod 1000000007 #define MOD 998244353 #define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i)) #define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i)) #define debug(x,y) cerr << (x) << " == " << (y) << endl; using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; } template<typename T> inline T lowbit(T x) { return x & -x; } // template<typename T> T qmi(T a, T b = mod - 2, T p = mod) { T res = 1; b %= (p - 1 == 0 ? p : p - 1); while (b) { if (b & 1) { res = (LL)res * a % p; }b >>= 1; a = (LL)a * a % p; }return res % mod; } const int N = 110; int n,m; vector<int>vec[N]; PII match[N][N]; bool st[N][N]; bool vis[N][N]; int dx[] = {0,1,0,-1},dy[] = {1,0,-1,0}; bool find(int x,int y){ for(int i =0 ; i < 4;++i){ int a = x + dx[i]; int b = y + dy[i]; if(a <= 0 || a > n || b <= 0 || b > n)continue; if(st[a][b] || vis[a][b])continue; st[a][b] = true; PII t = match[a][b]; if(t.first == 0 || find(t.first,t.second)){ match[a][b] = {x,y}; return true; } } return false; } void solve() { cin >> n >> m; for(int i = 1; i <= m;++i){ int a,b;cin >> a >> b; vis[a][b] = true; } int res = 0; for(int i = 1 ;i <= n;++i){ for(int j = 1; j <= n;++j){ // 对其中一个点集进行匹配 if(!vis[i][j] && (i + j & 1)){ memset(st,0,sizeof st); if(find(i,j))res++; } } } cout << res << endl; } signed main() { // int _; cin >> _; // while (_--) solve(); return 0; }
