二分图

总结
二分图的最大匹配：匈牙利算法
二分图的最小点覆盖数 = 二分图最大匹配数
二分图最大独立集 = 总点数 - 二分图最大匹配数
（有向无环图）不可重叠最少路径覆盖数=原图点数 - 二分图的最大匹配

二分图多重匹配就是在匈牙利算法上加上一维 limit 的维度（可以引入源点和汇点进而转化成最大流问题）
二分图最大权匹配是条件好像是在完备匹配的基础上？ KM算法（也可通过网络流解决）

01染色；转换为行和列
将一件事情拆成两种属性并对对应属性间构造关系求最大匹配
将连接两种事务的条件看成边，即求最大匹配

前置知识：
增广路：由未匹配点开始未匹配点结束，中间交错出现匹配边与未匹配边的一条路径。可以发现当我们把一条增广路的边交换性质之后，二分图的匹配数量就会➕1

二分图最大匹配
1匈牙利算法：枚举每个未匹配点，看是否能找到增广路，如果找到则最大匹配➕1
最坏复杂度：O（n*m）
Question
HDU1281棋盘游戏找到最大匹配后枚举删掉那个点会使最大匹配减小

棋盘覆盖给定一个N行M列的棋盘，已知某些位置禁止放置，求能够放到棋盘上的1*2多米诺骨牌的最大个数？
脑补将棋盘01染色后，相邻两个点就可以看成一个骨牌，那么相邻点连边求最大匹配即可（即把0看成二分图左半边点，去找1）
Place the Robots构造出新行和新列后求最大匹配
导弹防御塔reda Shi 的城堡遭受了M个入侵者的攻击！Freda 控制着N座导弹防御塔，每座塔都有足够数量的导弹，但是每次只能发射一枚。每座塔每次发射前需要预热T1秒，发射后需要冷却T2秒。给定塔和入侵者的坐标。导弹从塔发出直到击中目标所需的飞行时间=塔和入侵者之间的距离。由于小伙伴 Rainbow Li 就要来拜访她的城堡，Freda 想用最少的时间击退所有的入侵者，请你告诉她一种攻击方案。

二分时间T后可以算出每座塔最多能发射几枚炮弹，那么将每个防御塔拆成时间不同的炮弹，然后在对所有符合条件的入侵者连边（导弹发射时间+距离<=T）每次二分求最大匹配看是否为完备匹配即可
最小点覆盖
二分图最小点覆盖集的大小=二分图最大匹配集的大小

构造方法及证明:
1️⃣ 求出最大匹配
2️⃣ 从右部每个未匹配点出发寻找增广路（一定失败）标记访问过的节点
3️⃣ 取左部标记点，右部未标记点 构成一组最小覆盖

那么
左部未匹配点一定未标记（无增广路），右部未匹配点一定标记（出发点）
并且每对匹配点要么同时标记要么同时未标记
1️⃣这时恰好每对匹配点都指标记了一个，即数值上相等成立
合法性：
分类讨论：
1️⃣匹配点与匹配点之间的边：每对匹配点各取一个
2️⃣未匹配点与未匹配点之间的边：不存在
3️⃣ 匹配点与未匹配点之间的边：此时左部匹配点一定被标记
4️⃣ 未匹配点与匹配点之间的边：此时右部匹配点一定未被标记
Question
Machine Schedule每个模式对应左右两边的点，每个任务对应一条边，将每个任务的a->b连边后求得其实就是最小覆盖。
Muddy Fields 还是构造新的行和列后根据题意连有向边求最小覆盖。

最大独立集 ：选出图中尽可能多的点使任意两点之间没边
二分图的最大独立集=总点数 - 二分图的最大匹配数
证明：
选出最多的点没有边即
去掉最少的点使剩下的点之间没有边---->最小点覆盖---->最大匹配

骑士放置给定一个N*M的棋盘，有一些格子不能放棋子。问棋盘上最多能放多少个不能互相攻击的骑士（马）
还是01染色后发现一个位置能攻击到的另一个位置的颜色都不相等，所以连边后求最大独立集即可（这里和求最大匹配有点绕要想清楚）

**最小路径覆盖：**用尽量少的不相交的简单路径覆盖有向无环图的所有顶点

不相交的简单路径—>所有点的入度，出度都不大于1。
所以将每个点拆成两个点分部左右（表示入度和出度）那么，对于u–>v的边来说就相当于将左边的u和右边的v连一条边
二分图的每个点只能连一条边就相当于一个匹配
有向图路径上的每条边对应二分图上的一条边
有向图路径上的出点对应二分图的左部点
有向图路径上的终点不对应

二分图

全站热榜