poj3041 最小点覆盖即最大匹配(匈牙利算法)(模板)

<pre>#include <iostream>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <utility>
#define inf (1<<28)
#define ll long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define mid ((l+r)>>1)
using namespace std;

#define MAXN 505
bool map[MAXN][MAXN], vis[MAXN];
int match[MAXN];
int n, k;

bool dfs(int u)
{
    for(int i=1;i<=n;i++)
    {
        if(!vis[i]&&map[u][i]){
            vis[i]=true;
            if(match[i]==-1||dfs(match[i])){//没被选或者这个点虽然被选了，但是可以增广
                match[i]=u;
                return true;
            }

        }
    }
    return false;
}

int Maxmatch()
{
    int ret=0;
    memset(match,-1,sizeof(match));
    for(int i=1;i<=n;i++)
    {
        memset(vis,false,sizeof(vis));
        if(dfs(i))ret++;
    }
    return ret;
}

int main()
{
    while( scanf( "%d%d", &n, &k) == 2)
    {
        int x, y;
        memset( map, false, sizeof map);
        for( int i = 1; i <= k; i ++)
        {
            scanf( "%d%d", &x, &y);
            map[x][y] = true;
        }
        int ans = Maxmatch();
        printf( "%d
", ans);
    }
    return 0;
}