Acwing 378.骑士放置
题意
给定一个 N×M 的棋盘，有一些格子禁止放棋子。
问棋盘上最多能放多少个不能互相攻击的骑士（国际象棋的“骑士”，类似于中国象棋的“马”，按照“日”字攻击，但没有中国象棋“别马腿”的规则）。
思路
将棋盘划分为两类：坐标和奇数为一类 坐标和偶数为一类，
可以发现 当前格子能到达的格子与其本身奇偶性不同，所以根据坐标和的奇偶性将其抽象成一个二分图，把每个格子和它能到达的格子之间连一条边。
题目要求出最多能放置多少个不能互相攻击的骑士，也即求出最多能放置多少个骑士其两两之间不能到达，即最大独立集的定义：选出最多的点使得其两两之间没有边。
用匈牙利算法求出最大匹配res后，答案即为n * m - k - res。
代码
// Author：zzqwtcc // Problem: 骑士放置 // Contest: AcWing // Time：2021-10-07 15:16:37 // URL: https://www.acwing.com/problem/content/380/ // 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, k; bool g[N][N]; bool st[N][N]; PII match[N][N]; vector<int>vec[N]; int dx[] = {- 2,-1,1,2,2,1,-1,-2}, dy[] = {1,2,2,1,-1,-2,-2,-1}; bool find(int x,int y){ for(int i = 0 ;i < 8;++i){ int a = x + dx[i]; int b = y + dy[i]; if(a <= 0 || a > n || b <= 0 || b > m)continue; if(st[a][b] || g[a][b])continue; st[a][b] = true; auto 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 >> k; for( int i = 1; i <= k;++i){ int x,y;cin >> x >> y; g[x][y] = true; } int res = 0; for(int i = 1; i <= n;++i){ for(int j = 1; j <= m;++j){ if(!g[i][j] && (i + j & 1)){ memset(st,0,sizeof st); if(find(i,j)) res++; } } } cout << n * m - k - res << endl; } signed main() { //int _; cin >> _; //while (_--) solve(); return 0; }
