【二分图】【二分图最大匹配】LCP 04. 覆盖

作者推荐

视频算法专题

本文涉及知识点

二分图 二分图最大匹配

LeetCode LCP 04. 覆盖

你有一块棋盘，棋盘上有一些格子已经坏掉了。你还有无穷块大小为1 * 2的多米诺骨牌，你想把这些骨牌不重叠地覆盖在完好的格子上，请找出你最多能在棋盘上放多少块骨牌？这些骨牌可以横着或者竖着放。
输入：n, m代表棋盘的大小；broken是一个b * 2的二维数组，其中每个元素代表棋盘上每一个坏掉的格子的位置。
输出：一个整数，代表最多能在棋盘上放的骨牌数。
示例 1：
输入：n = 2, m = 3, broken = [[1, 0], [1, 1]]
输出：2
解释：我们最多可以放两块骨牌：[[0, 0], [0, 1]]以及[[0, 2], [1, 2]]。（见下图）
在这里插入图片描述

示例 2：
输入：n = 3, m = 3, broken = []
输出：4
解释：下图是其中一种可行的摆放方式

在这里插入图片描述

限制：
1 <= n <= 8
1 <= m <= 8
0 <= b <= n * m

二分图

图G所有点可以分为两个子集X,Y。子集合X内部的点没有边相连,子集Y内部也是。X ∈ \in ∈[0,n)
二分图的判断方法：
染色法，任何一点开始染成红色，邻接点染成黑色，看是否冲突。
可以用： 深度优先或广度优先或并集查找

二分图的最大匹配

保证任何点最多选取一次的情况下，选取最多的边。
典型用例：一组老师，一组学生，如果老师x和学生y互相有好感，则可以组队教学。任何老师只能参加一个队伍，学生也是。
交叉路径：选取边和未选取边交叉出现。
增广路径：以非选取边开始，非选取边结束的交叉路径。由于边数是奇数，所以一定x起点，y终点或y起点,x终点。不失一般性，我们以x为起点。
增广路径的选择边和非选择边互换，选择边增加。
用匈牙利算法来实现Find：
枚举x in X，如果x是一个增广路径的起点，则x匹配此路径的第二个节点。
枚举y， y 是x的临接点，且不在此路径中。如果y没有匹配，则x → \rightarrow →y 是增广路径，vMath[y]=x。
如果已经匹配，看Find(vMath[y]) 是否成功 ，如果成功，也是增广路径。vMath[y] = x。
如果所有临接点都匹配失败，则x匹配失败。
性质一：无论是手动调用，还是递归调用。都只会Find(子集X的节点)。
性质二：用变量used记录，那些Y节点在本次路径。我们从小到大枚举x，则Find(x)开始事，vMath[y] ∈ \in ∈ [0,x) ;Find(x)结束后，vMath[y] ∈ \in ∈ [0,x]。所有无需记录那些x已经使用。
长度为3的增广路径：x1->y1 同时 x2和y1连通 x1和y2连通
则find(x2)调用find(x1)时： x1->y2连通,且y2没有匹配，于是vMath[y2]=x1
find(x2)本体中：vMath[y1]=x2 x 2 → y 1 ‾ → x 1 → y 2 ‾ \underline{ x2 \rightarrow y1} \rightarrow \underline{ x1 \rightarrow y2 } x2→y1​→x1→y2​

证明：
如果找不到以x为起点的增广路径，则选择几条边，就需要删除几条边。边数不变。

代码

核心代码

class CNeiBo
{
public:	
	static vector<vector<int>> Two(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0) 
	{
		vector<vector<int>>  vNeiBo(n);
		for (const auto& v : edges)
		{
			vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase);
			if (!bDirect)
			{
				vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase);
			}
		}
		return vNeiBo;
	}	
	static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0)
	{
		vector<vector<std::pair<int, int>>> vNeiBo(n);
		for (const auto& v : edges)
		{
			vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase, v[2]);
			if (!bDirect)
			{
				vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase, v[2]);
			}
		}
		return vNeiBo;
	}
	static vector<vector<int>> Grid(int rCount, int cCount, std::function<bool(int, int)> funVilidCur, std::function<bool(int, int)> funVilidNext)
	{
		vector<vector<int>> vNeiBo(rCount * cCount);
		auto Move = [&](int preR, int preC, int r, int c)
		{
			if ((r < 0) || (r >= rCount))
			{
				return;
			}
			if ((c < 0) || (c >= cCount))

			{
				return;
			}
			if (funVilidCur(preR, preC) && funVilidNext(r, c))
			{
				vNeiBo[cCount * preR + preC].emplace_back(r * cCount + c);
			}
		};

		for (int r = 0; r < rCount; r++)
		{
			for (int c = 0; c < cCount; c++)
			{
				Move(r, c, r + 1, c);
				Move(r, c, r - 1, c);
				Move(r, c, r, c + 1);
				Move(r, c, r, c - 1);
			}
		}
		return vNeiBo;
	}
	static vector<vector<int>> Mat(vector<vector<int>>& neiBoMat)
	{
		vector<vector<int>> neiBo(neiBoMat.size());
		for (int i = 0; i < neiBoMat.size(); i++)
		{
			for (int j = i + 1; j < neiBoMat.size(); j++)
			{
				if (neiBoMat[i][j])
				{
					neiBo[i].emplace_back(j);
					neiBo[j].emplace_back(i);
				}
			}
		}
		return neiBo;
	}
};

class CBipartiteGraph
{
public:
	int MaxMatch()
	{
		m_vYToX.assign(m_vY.size() + m_vX.size(),-1);
		int ans = 0;
		for (const auto& x : m_vX)
		{
			m_vUsed.assign(m_vY.size() + m_vX.size(),false);
			ans += Find(x);
		}
		return ans;
	}
	bool Find(int x)
	{		
		for (const auto& y : m_vNeiBo[x])
		{
			if (m_vUsed[y])
			{
				continue;
			}
			m_vUsed[y] = true;
			if ((-1 == m_vYToX[y]) || (Find(m_vYToX[y])))
			{
				m_vYToX[y] = x;
				return true;
			}
		}
		return false;
	}
	vector<int> m_vX, m_vY;
	vector<vector<int>> m_vNeiBo;
	vector<int> m_vYToX;
	vector<bool> m_vUsed;
};
class Solution {
public:
	int domino(int n, int m, vector<vector<int>>& broken) {
		vector<vector<int>> grid(n, vector<int>(m));
		for (const auto& v : broken)
		{
			grid[v[0]][v[1]] = 1;
		}
		auto vilidFun = [&grid](int r, int c) {return 0 == grid[r][c]; };
		CBipartiteGraph bg;
		for (int r = 0; r < n; r++)
		{
			for (int c = 0; c < m; c++)
			{
				const int mask = m * r + c;
				if ((r + c) & 1)
				{
					bg.m_vY.emplace_back(mask);
				}
				else
				{
					bg.m_vX.emplace_back(mask);
				}
			}
		}
		bg.m_vNeiBo = CNeiBo::Grid(n, m, vilidFun, vilidFun);		
		return bg.MaxMatch();
	}
};

测试用例

template<class T, class T2>
void Assert(const T& t1, const T2& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}

}

int main()
{
	int m, n;
	vector<vector<int>> broken;
	{
		Solution sln;
		n = 3, m = 3, broken = {  };
		auto res = sln.domino(n, m, broken);
		Assert(4, res);
	}
	{
		Solution sln;
		n = 2, m = 3, broken = { {0, 0},{0, 1} };
		auto res = sln.domino(n, m, broken);
		Assert(2, res);
	}
	{
		Solution sln;
		n = 2, m = 3, broken = { {1, 0},{1, 1} };
		auto res = sln.domino(n, m, broken);
		Assert(2, res);
	}
	
	{
		Solution sln;
		n = 4, m = 3, broken = { {1,0},{1,1} };
		auto res = sln.domino(n, m, broken);
		Assert(5, res);
	}
	{
		Solution sln;
		n = 3, m = 4, broken = { {2,2},{2,3} };
		auto res = sln.domino(n, m, broken);
		Assert(5, res);
	}

}

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/504004.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Logback日志框架(超详细)

Logback日志框架(超详细)

logback-classic-1.2.3.jarhttp://链接: https://pan.baidu.com/s/1cA3gVB_6DEA-cSFJN6MDGw 提取码: sn8i 复制这段内容后打开百度网盘手机App&#xff0c;操作更方便哦 logback-core-1.2.3.jarhttp://链接: https://pan.baidu.com/s/19eCsvsO72a9PTqpXvXxrgg 提取码: 5yp…
阅读更多...
二维码门楼牌管理应用平台建设：引领现代化小区管理新篇章

二维码门楼牌管理应用平台建设：引领现代化小区管理新篇章

文章目录 前言一、二维码门楼牌管理应用平台概述二、三维动态单体化技术的优势三、二维码门楼牌管理应用平台的应用场景四、展望未来 前言 随着城市化的快速推进&#xff0c;现代化小区如雨后春笋般涌现&#xff0c;对小区管理的效率和智能化提出了更高要求。二维码门楼牌管理…
阅读更多...
代码随想录笔记|C++数据结构与算法学习笔记-动态规划(〇)|

代码随想录笔记|C++数据结构与算法学习笔记-动态规划(〇)|

本文是简单的视频总结&#xff1a;从此再也不怕动态规划了&#xff0c;动态规划解题方法论大曝光 &#xff01;详细信息还请看代码随想录讲解视频 文章目录 动态规划的常见类型动态规划的误区动规五步曲DP数组以及下标的含义递推公式DP数组如何初始化DP数组遍历顺序打印DP数组…
阅读更多...
WebViz可视化

WebViz可视化

WebViz可视化 Webviz是一个基于Web的可视化工具&#xff0c;意味着您可以通过浏览器/APP访问它&#xff0c;而不需要安装额外的软件。这对于远程访问和团队协作非常方便。 Foxglove是一个开源的工具包&#xff0c;包括线上和线下版。旨在简化机器人系统的开发和调试。它提供了…
阅读更多...
弧形导轨在自动化设备中的传动原理

弧形导轨在自动化设备中的传动原理

在自动化机械系统中&#xff0c;弧形导轨是一种常见的轨道结构&#xff0c;用于支撑和引导物体沿着指定的弧线运动。其工作原理基于几何学和物理学的原理。 弧形导轨通常由一个弧形的轨道和一个移动部件组成。轨道一般呈弧形&#xff0c;其几何形状可以是圆弧、椭圆弧等&#x…
阅读更多...
Java作业3-字符串

Java作业3-字符串

题目一 代码 import java.util.*; public class Main {public static void main(String[] args) {Scanner input new Scanner( System.in );String str input.nextLine();int len str.length();StringBuilder s new StringBuilder(len);//StringBuilder类参考菜鸟教程for…
阅读更多...
Unicode编码解码的全面介绍

Unicode编码解码的全面介绍

title: Unicode编码解码的全面介绍 date: 2024/3/30 18:30:48 updated: 2024/3/30 18:30:48 tags: Unicode起源编码演变UTF编码编码表详解编码解码实践Unicode挑战未来发展 1. Unicode的起源和发展 Unicode是一个国际标准&#xff0c;旨在统一世界上所有文字的表示方式。它最…
阅读更多...
Leetcode刷题记录面试基础题day1（备战秋招）

Leetcode刷题记录面试基础题day1（备战秋招）

hello&#xff0c;你好鸭&#xff0c;我是康康&#xff0c;很高兴你能来阅读&#xff0c;昵称是希望自己能不断精进&#xff0c;向着优秀程序员前行!&#x1f4aa;&#x1f4aa;&#x1f4aa; 目前博客主要更新Java系列、数据库、项目案例、计算机基础等知识点。感谢你的阅读和…
阅读更多...
redis学习-redis配置文件解读

redis学习-redis配置文件解读

目录 1.单位说明 2. include配置 3. network网络配置 3.1 bind绑定ip配置 3.2保护模式protected-mode配置 3.3端口号port配置​编辑 3.4超时断开连接timeout配置 4. general通用配置 4.1守护进程模式daemonize配置 4.2进程id存放文件pidfile配置 4.3日志级别loglevel配置 4.…
阅读更多...
音视频基础 （九）---FFmpeg过滤器框架

音视频基础 （九）---FFmpeg过滤器框架

ffmpeg的filter⽤起来是和Gstreamer的plugin是⼀样的概念&#xff0c;通过avfilter_link&#xff0c;将各个创建好的filter按 ⾃⼰想要的次序链接到⼀起&#xff0c;然后avfilter_graph_config之后&#xff0c;就可以正常使⽤。 ⽐较常⽤的滤镜有&#xff1a;scale、trim、over…
阅读更多...
Rabbit简单模式理解

Rabbit简单模式理解

简单模式 我们以最普通的方式去理解&#xff0c;并没有整合Springboot的那种 这是最简单的模式&#xff0c;一个生产者&#xff0c;一个消费者&#xff0c;一个队列 测试 1、 导包&#xff0c;没整合&#xff0c;不需要编写配置 2、需要生产者消费者 导包 <dependency…
阅读更多...
深度学习：基于PyTorch的模型解释工具Captum

深度学习：基于PyTorch的模型解释工具Captum

深度学习&#xff1a;基于PyTorch的模型解释工具Captum 引言简介示例安装解释模型的预测解释文本模型情绪分析问答 解释视觉模型特征分析特征消融鲁棒性 解释多模态模型 引言 当我们训练神经网络模型时&#xff0c;我们通常只关注模型的整体性能&#xff0c;例如准确率或损失函…
阅读更多...
cocos2.x =＞ node 属性修改

cocos2.x =＞ node 属性修改

简介 与节点属性相关的几个核心变量_trs、_matrix、_worldMatrix、_localMatDirty、_worldMatDirty。 _trs&#xff1a;存储节点的position、rotation、scale _matrix&#xff1a;存储节点的缩放、位移、旋转三者合一的变化矩陈&#xff08;仿射矩陈&#xff09; _worldMat…
阅读更多...
csp资料

csp资料

头文件 #include <bits/stdc.h> using namespace std isdigit(c); isalpha(c); switch(type){case value : 操作 } continue;//结束本轮循环 break;//结束所在的整个循环tips: //除法变乘法来算 //减法变加法 num1e42;//"1e4"表示10的4次方//用于移除容器中相…
阅读更多...
【面试专题】MySQL

【面试专题】MySQL

1.什么是BufferPool&#xff1f; Buffer Pool基本概念 Buffer Pool&#xff1a;缓冲池&#xff0c;简称BP。其作用是用来缓存表数据与索引数据&#xff0c;减少磁盘IO操作&#xff0c;提升效率。 Buffer Pool由缓存数据页(Page) 和 对缓存数据页进行描述的控制块 组成, 控制…
阅读更多...
鹏哥C语言复习——指针

鹏哥C语言复习——指针

目录 一.指针基础概念 二.指针和指针类型 三.野指针介绍 四.规避野指针的办法 五.指针运算 六.指针和数组 七.指针和数组传参 八.二级指针 九. 函数指针 十.qsort( )函数 十一.字符指针 一.指针基础概念 指针是什么&#xff1f; 指针理解的2个要点&#xff1a; 1.指…
阅读更多...
java内存分析工具visualvm

java内存分析工具visualvm

java内存分析工具visualvm 下载地址:https://visualvm.github.io/
阅读更多...
开源推荐榜【Taichi 专为高性能计算机图形学设计的编程语言】

开源推荐榜【Taichi 专为高性能计算机图形学设计的编程语言】

Taichi是一个高性能的并行编程语言&#xff0c;它被嵌入在Python中&#xff0c;使得开发者能够轻松编写可移植的、高性能的并行程序。这个库的核心优势在于它能够将计算密集型的Python代码在运行时通过即时编译器(Just-In-Time, JIT)转换成快速的机器代码&#xff0c;从而加速P…
阅读更多...
MT9630全制式Android智能商显解决方案

MT9630全制式Android智能商显解决方案

一、方案描述 商用显示通常是指专业显示器设备&#xff0c;可靠性和高清晰显示能力远强于普通显示器&#xff0c;在成像处理与色彩、亮度和对比度还有可视视角几方面具备优势&#xff0c;主要应用于商业场景&#xff0c;中国商业显示市场细分产品包括电子白板、商用电视、广告…
阅读更多...
012_control_flow_in_Matlab中的控制流

012_control_flow_in_Matlab中的控制流

Matlab中的控制流 虽然&#xff0c;我们说Matlab中的计算是向量化的&#xff0c;但是在某些情况下&#xff0c;作为一个“程序设计语言”&#xff0c;Matlab也提供了一些控制流结构&#xff0c;来帮助我们实现一些复杂的逻辑。 我会在介绍控制流的时候&#xff0c;提醒如何用…
阅读更多...
最新文章

Copyright @ 2022~2023