带花树算法(匈牙利算法 \(Pro~max\))
我们考虑现在访问到 \(u\) 点(黑色),\(u\) 连向 \(v\) 点,分类讨论 \(v\) 点。
1、\(v\) 点没有被匹配过,直接令 \(u\) 点和 \(v\) 点匹配,然后更新答案
2、\(v\) 点匹配过,但之前还未被访问过,那么把 \(v\) 点染成白色,然后把 \(v\) 点的匹配点 \(x\) 加入队列,继续寻找增广路,并将 \(x\) 染成黑色。
3、\(v\) 点匹配过,且之前被访问过,是白色的,这显然是不可能的
标签:黑色,匹配,白色,笔记,学习,访问,算法 From: https://www.cnblogs.com/pengchujie/p/17662723.html