Acwing 372. 棋盘覆盖 (二分图求最大匹配)

简介: 笔记

棋盘覆盖


题意

给定一个 N 行 N 列的棋盘,已知某些格子禁止放置。


求最多能往棋盘上放多少块的长度为 2、宽度为 1 的骨牌,骨牌的边界与格线重合(骨牌占用两个格子),并且任意两张骨牌都不重叠。


思路

我们将棋盘上的方格看作点,骨牌看作两个点之间的边,那么问题就可以抽象成最多能选取多少条边,使得每条边没有公共顶点。如图:15.png


这时 棋盘还不能看作二分图,不能使用匈牙利算法。


接下来,我们可以将每个点染色,

将所有点分成两部分:坐标和为奇数的 和 坐标和为偶数的,可以发现,任意一个符合条件的骨牌占用的两个格子一定属于不同种类。


那么我们就可以将问题最终抽象成:在一个二分图中求最大匹配,直接使用匈牙利算法即可


代码

// 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;
}


目录
相关文章
|
3月前
没有给出二分图两个左右点集时的二分图最大匹配
没有给出二分图两个左右点集时的二分图最大匹配
12 0
|
4月前
|
机器学习/深度学习 存储 算法
【算法训练-回溯算法 一】【排列问题】全排列、全排列II
【算法训练-回溯算法 一】【排列问题】全排列、全排列II
49 0
|
8月前
|
存储 算法 调度
【喜闻乐见,包教包会】二分图最大匹配:匈牙利算法(洛谷P3386)
【喜闻乐见,包教包会】二分图最大匹配:匈牙利算法(洛谷P3386)
47 0
|
9月前
|
人工智能
线性DP——AcWing 898. 数字三角形、AcWing 895. 最长上升子序列
线性DP——AcWing 898. 数字三角形、AcWing 895. 最长上升子序列
54 0
|
11月前
|
算法 C++
每日算法系列【LeetCode 376】摆动序列
每日算法系列【LeetCode 376】摆动序列
|
算法
LeetCode:376. 摆动序列——说什么贪心和动规~
如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为 摆动序列 。第一个差(如果存在的话)可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。 例如, [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ,因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。 相反,[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列,第一个序列是因为它的前两个差值都是正数,第二个序列是因为它的最后一个差值为零。 子序列 可以通过从原始序列中删除一些(也可以不删除)元素来获得,剩下的元素保持其原始顺序。
|
人工智能 算法 搜索推荐
LeetCode 周赛 338,贪心 / 埃氏筛 / 欧氏线性筛 / 前缀和 / 二分查找 / 拓扑排序
大家好,我是小彭。 上周末是 LeetCode 第 338 场周赛,你参加了吗?这场周赛覆盖的知识点很多,第四题称得上是近期几场周赛的天花板。
80 0
HDU7018.Banzhuan(计算几何+贪心)
HDU7018.Banzhuan(计算几何+贪心)
81 0
HDU7018.Banzhuan(计算几何+贪心)