HutaoImpact：我去，这不V正弦ger_洛天依吗

HutaoImpact：我今天必须想个办法发烧回去抽银狼

HutaoImpact：我去我怎么还不走我马上退烧了

HutaoImpact：我给自己挂个冰元素弱点然后冻一晚上就能回家了

HutaoImpact：凭什么不让我拿，就凭这东西是你的？

HutaoImpact：我把机房那个窗户把手拆下来之后放到你柜子里了，让我拿一下

HutaoImpact：我不就是玩了会儿4399吗，为啥教练把我赶走了

STA_Morlin：你是信竞？巧了我是电竞的

根据HutaoImpact的一篇闲话只能放一共数论或者图论且两者不相容的东西原则所以我今天只能写两个闲话了

再推一首歌 《为了你唱下去》

二分图

二分图,又称二部图

就是能够将节点划分成满足节点由两个集合组成$\ $ 且 $\ $两个集合内部没有边的图

• 性质:

  • 二分图中的每一条边都一定是连接两个集合中各一个点

  • 二分图不存在长度为奇数的环

    • 每一条边都从一个集合到另一个集合，只有走偶数次才有可能回到同一集合内

• 判定

  • 我们可以使用 DFS 或 BFS 来遍历

    如果发现了奇环，则非二分图，反之则是

二分图最大匹配

任意两条边都没有公共端点的边的集合是图的一组匹配

给定一个二分图 \(G\) ，即分左右两部分，各部分之间的点没有边连接，要求选出一些边，使得这些边没有公共顶点，且边的数量最大。

解法：

• 匈牙利算法(增广路算法)

  对于任意一组匹配\(S\)，属于\(S\)的边被称为匹配边，不属于\(S\)的边称为非匹配边，匹配边的端点称作匹配点，其他节点叫做非匹配点

  如果二分图上存在一条连接两个非匹配点的路径\(path\)使得非匹配边和匹配边在\(path\)上交替出现则称\(path\)为匹配\(S\)的增广路，也称交错路

  • 性质

    长度\(len\)为奇数

    路径上\(1,3,5,len\)条边是非匹配边，第\(2,4,6,len-1\)是匹配边

  • 推论

    二分图的一组匹配\(S\)是最大匹配，当且仅当图中不存在\(S\)的增广路

  • 算法

    • 设\(S\)为空，则所有边都是非匹配边

    • 寻找增广路，把路径上所有边的匹配状态取反，得到一个更大的匹配\(S'\)

    • 重复第二步，直到图中没有增广路存在

  • 如何找到增广路

    对于左端点\(x\)和右端点\(y\)需要满足两个条件之一

    • \(y\)本身就是非匹配点

      此时\((x,y)\)是一条长度为\(1\)的增广路

    • \(y\)已经和\(x'\)匹配但是从\(x'\)能找到另一个\(y'\)和之匹配

      此时路径\(x\sim y\sim x' \sim y'\)是一条增广路

• 转化为网络最大流模型

  不会