感觉根本不会写blog啊怎么办
诶不管了泥萌就凑合着看吧
首先肯定还是要找增广路
啥？泥问增广路是什么？增广路就是非匹配边和匹配边交错而且起点和终点都没有被匹配的路径
那么就可以枚举增广路的起点然后BFS找增广路
于是在搜索增广路的时候，会遇到两种点
第一种点是上一条边是匹配边的点，第二种点是上一条边是非匹配边的点
不妨叫做A型点和B型点，并且规定起点是A型点
然后对于每个A型点，都可能找到若干个B型点
但是对于每个B型点，它能找到的只有一个A型点
A-B=A-B=A-B ←因为增广路一定是这个样子的
因此BFS的时候只用把A型点加入队列就可以啦~
当A型点经过非匹配边搜索到没有标记类型的点的时候
如果这个点已经被匹配，那么就把这个点标记为B型点并把这个点的匹配点标记为A型点
否则这个点没有被匹配，找到增广路，那么把增广路上所有匹配边变成非匹配边，所有非匹配边变成匹配边，总匹配数+1
当然这是搜索到没有标记类型的点的情况
现在考虑搜索到了标记过类型就是已经走过的点
如果这个点是B型点，那么就说明找到了一个偶环，直接无视掉就可以了
但如果这个点是A型点的话，就说明找到了一个奇环
那么对于一个奇环，如果找到了从这个奇环上的一个点出发的增广路，那么一定能使匹配数+1
窝不方便画图泥萌脑补一下
于是我们就可以把这个奇环看成一个A型点，也就是把这个环缩成一朵花
然后把这个环上的所有A型点连出去的边连向这朵花就可以啦
至此就完美的解决了一般图最大匹配
其实具体细节还是很复杂的大家就去看代码吧
如果有小伙伴会多路增广的话直接应用到带花树里面就可以啦~
另外欢迎大家来问我和一般图最大匹配有关的问题
鄂公网安备 42010202000505 号