【二分图】匈牙利求最大匹配

导读 ^ _ ^

情人节特刊。
一群爱好算法的单身人士在家用着二分图匈牙利算法帮别人牵着红线。呜呜呜呜呜~

匈牙利求最大匹配（n * m，实际效果很好）

思路与流程

• 对要匹配的指向可以匹配的对象。
• 从第一个点进行匹配
• 如果冲突，协商修改
• 每次修改或者匹配成功，则结果加1

月佬算法
两个点的目标点“冲突”的时候，采取“协商”的办法。
即序号小的连接可能连接的另一条边。 若“协商”失败，则放弃序号较大的点的边。

代码实现

/* 
采取“枚举-匹配-协商-后退-修改”的思路
n * m，实际效果很好
match存被勾选的被动方
*/
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
const int N = 510, M = 10010;

int n1,n2,m;//左边有n1个点，右边有n2个点
int e[M],ne[M],h[N],idx;
int match[N];
bool st[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a],h[a] = idx++;
}

bool find(int x) {
    for(int i = h[i]; i != -1; i++) {//枚举每一个看上的集合
        int j = e[i];
        if(!st[j]) {//本轮次匹配时，没有男生相中的女生(动态，临时概念)
            st[j] = true;//有人相中了
            // match[j] == 0:如果j女生以前没有男朋友，那OK，可以
            // find(match[j]):如果j的男朋友match[j]可以找其它女生
            if(match[j] == 0 || find(match[j]))  {
                match[j] = x;//设置女生j的男朋友是x,逆袭成功！
                return true;
            }
        }
    }
    return false;//找不到
}

int main( ) {
    scanf("%d%d%d",&n1,&n2,&m);
    memset(h, -1, sizeof h);

    while(m--) {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
    }
    
    int res = 0;
    for(int i = 1; i <= n1; i++) {
       //表示后来的更牛，它看上的妹子，就会让其它人让出来，都是没有人选择过的状态！
       //st用来标识每轮相亲中，已经被相上的
       memset(st, false, sizeof st);
       if(find(i))  res++;//如果成功找到妹子，个数加1
    }

    cout << res << endl;

    return 0;
}

#谢谢你的观看！

^ _ ^