2063.JPG
看到这道题的时候想起学数据结构的时候学到一种结构叫图，当图中a和b之间有边的时候，矩阵里第a行第b列是1，否则就是0。所以这道题的配对组合可以用到二维数组，遍历数组找到成功配对组合。
这道题的难点在于需要用到递归，当一个男生（a1）找到女生（b1）可以配对时就先配对着，如果下一个男生（a2）也找到女生b1配对时就用递归判断a1是否能找到另一个可配对的女生（b2），若能找到，a1则和b2配对，a2就能就b1配对了，若找不到，a2继续寻找下一个女生。
代码如下：
#include <iostream>
#include<cstring>
using namespace std;
int flag[505] = { 0 };//作为暂时标记
int map[505][505];//意向配对组合
int yes[505];//成功配对
int k, n, m, a, b;
int find(int x)
{
for (int j = 1; j <= m; j++)
{
if (map[j][x] == 1 && flag[j] == 0)//有配对意向且没有标记过
{
flag[j] = 1;
if (yes[j] == 0 || find(yes[j]))//递归，如果该女生没有成功配对的或者已配对的男生能找到别的女生配对，就和该女生配对
{
yes[j] = x;
return 1;
}
}
}
return 0;
}
int main()
{
while (cin >> k)
{
if (k == 0)break;
cin >> m >> n;
memset(map, 0, sizeof(map));
memset(yes, 0, sizeof(yes));
while (k--)
{
cin >> a >> b;
map[a][b] = 1;
}
int out = 0;
for (int i = 1; i <= n; i++)
{
memset(flag, 0, sizeof(flag));
if(find(i))
out++;
}
cout << out<< endl;
}
return 0;
}
