二分图匹配学习笔记

· · 个人记录

二分图匹配

1.二分图是什么

如果能把一张图G(V , E)分成两个点集，X ， Y。保证点集X中从任意一个点出发的边通向的点都在点集Y中，Y中从任意一个点出发的边通向的点都在点集X中。则图G(V , E)为二分图。

2.图的最大匹配是什么

定义边E链接的两个点(u , v)为边E所覆盖的点，那么一个图的最大匹配就是选出尽量多的边并且没有覆盖重复节点的边。

3.二分图的最大匹配怎么搞

随便乱搞

匈牙利算法：定义增广路，两个未覆盖的节点中存在路径P，若P中的边成覆盖边与非覆盖边交替出现，那么P为一条增广路。可以发现，若存在增广路，则把增广路中覆盖与未覆盖取反，那么答案一定会增加1。

算法流程：

bool NTR(u) 

for(v = 所有与u相连的节点)
    if(cp[v] 不存在 || NTR(cp[v])) cp[v] = u , return true;
return false;

    /*对于每一个节点，它要找一个cp，而如果对方并没有cp，那么直
    接与它结成cp；而如果对方已经有cp了，那么想办法NTR（我查了
    一下，NTR并不一定代表自己被绿，还有绿别人的意思）它，如果
    成功NTR，那么与它结成cp，这也意味着找到了一条增广路，所以
    一定更优。但如果谁都NTR不了，那么节点u就是败犬，算法结束。*/