下雪了

洛谷P3386 【模板】二分图匹配

二分图匈牙利算法,归根结底就是递归找新边找找找!

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<stack>
#include<cmath>
#include<ctime>
#include<queue>
#include<deque>
#include<list>
#include<map>
#define int long long
#define ffor(i, a, b) for(ll i = a; i <= b; i++)
#define rfor(i, a, b) for(ll i = a; i >= b; i--)
#define mes(a,b) memset(a, b, sizeof(a))
#define cos(x) cos(x*PI/180.0)
#define sin(x) sin(x*PI/180.0)
#define stop system("pause")
#define see(s,x) cout<<(s)<<'='<<(x)<<endl
#define IMAX 0x7fffffff
#define PI 3.141592654
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x&(-x))
#define test(x) cout<<"Test "<<(x)<<endl;
typedef long long ll;
ll mod;
ll max(ll a, ll b) { return(a > b) ? a : b; }
ll min(ll a, ll b) { return(a < b) ? a : b; }
using namespace std;

vector<int> G[1005];
int tab[1005];
bool v[1005];

bool deal(int x)
{
    for (int i : G[x])
    {
        if (!v[i])
        {
            v[i] = true;
            if (!tab[i] || deal(tab[i]))
            {
                tab[i] = x;
                return true;
            }
        }
    }
    return false;
}

signed main()
{
    mes(tab, 0);
    int n, m, e;
    cin >> n >> m >> e;
    ffor(i, 1, e)
    {
        int x, y;
        scanf("%lld%lld", &x, &y);
        if (x <= n && y <= m)
            G[x].push_back(y);
    }
    int res = 0;
    ffor(i, 1, n)
    {
        mes(v, 0);
        res += deal(i);
    }
    cout << res << endl;
}