好图当赏

使用场景

用于判断最大匹配成功数

底层逻辑

调节资源分配。

当某个请求的资源被占用时，找到占用资源的进程，尝试更改进程的占用资源，尝试将其分配到其他可以使用的资源

如果请求无法获得任何一个可以使用的资源则匹配失败

抽象表达

待字闺中，据为己有；名花有主，求他放手

——来自评论区

下面是爱慕关系

男1：女1，女2，女3

男2：女1，女2

男3：女1

男4：女3

男1爱慕女1 此时女1无对象 男1和女1在一起

男2爱慕女1 此时女1对象为男1 男2求男1分手

男1有备胎女2 男1分手和女2在一起 男2和女1在一起

男3爱慕女1 此时女1对象为男2 男3求男2分手

男2有备胎女2 但是女2有对象是男1 男2求男1分手

男1有备胎女3 男1分手和女三在一起 男2和女1分手和女2在一起 男3和女1在一起

男4爱慕女3 但是现在女3有对象是男1 男1尝试求女1的对男3分手

男3没有备胎无法分手

男1尝试求女2的对象男2分手

男2尝试找女1的对象男3分手

男3没有备胎无法分手

男1没有剩余备胎且不能为了他人导致自己没有对象

男1更换对象失败 女3仍和男1在一起

男4无法和女3在一起 且没有备胎 男4无法获得对象

最大匹配成功数为3

例题

#include <cstring>
#include <iostream>
#include <algorithm>
#define endl '\n'

using namespace std;

const int N = 510, M = 100010;

int n1, n2, m;
int h[N], e[M], ne[M], 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[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true;
            if (match[j] == 0 || find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
    }

    return false;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n1 >> n2 >> m;

    memset(h, -1, sizeof h);

    while (m--)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }

    int res = 0;
    for (int i = 1; i <= n1; i++)
    {
        memset(st, false, sizeof st);
        if (find(i)) res++;
    }

    cout << res << endl;

    return 0;
}

代码模板来自acwing——yxc