51Nod-2006-飞行员配对(二分图最大匹配)

如题，这种题我以前见过，但是作为菜鸟当然做不出来，而今天既然再次遇见，便打算将其搞清楚。遂网上搜索解法，但见满篇代码，却不见有谁讲清楚到底是怎么一回事。大佬们一句裸题就放代码了，可是小白不懂啊~

于是便有了如下经历，终于花了两个小时A掉了

首先，这是一道数据流的题，但我不会数据流，以后学到了再说。但此题还有另一种解法，其名为匈牙利算法。这让我联想到匈牙利命名法，但其实并没有什么关系。唔，我就是用匈牙利算法来解的这道题。

不了解匈牙利算法的童鞋，去看这位大佬的博客：​​匈牙利算法​​

他的代码乍一看是看不懂的，因为不完整，但是算法思想讲的很透彻，看懂思想即可。

接下来是针对这道题的解法了，到现在才发现确实没什么好说的，直接拿匈牙利算法套进去就是答案，不过还是根据我的代码解释一下。

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define MAX_LEN 500
#define MOD 1000000007

int a[MAX_LEN][MAX_LEN] = {0};
int used[MAX_LEN] = {0};
int eng[MAX_LEN] = {-1};
int sum = 0;

void init()
{
    memset(used,0,sizeof(used));
}

bool pp(int x,int m,int n)
{
    int i,j;
    for(i=m;i<n;i++)
    {
        if(a[x][i] == 1 && used[i] == 0)
        {
            used[i] = 1;
            if(eng[i] == -1 || pp(eng[i],m,n))
            {
                eng[i] = x;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    int m,n;
    int w,y;
    cin>>w>>y;
    while(cin>>m>>n)
    {
        if(m==-1 || n==-1)
        {
            break;
        }

        a[m-1][n-1] = 1;
    }

    memset(eng,-1,sizeof(eng));

    for(int i=0;i<w;i++)
    {
        init();
        if(pp(i,w,y))
        {
            sum++;
        }
    }

    cout<<sum<<endl;
}