问题描述：
给定一些关系，是个二分图，要求它的最大完美匹配。
解题思路：
枚举左边的点，对任意一个点枚举它的边子集，再在枚举到的边子集的右边点集中以相同方式枚举，最后形成左右两边均为K的点，检测是否为完全二分图即可。
代码如下：
#include <iostream>
#include <vector>
using namespace std;
int t;
int n, i;
vector < int > lvec[40], rvec[40];
int l, r, dep;
int bo[40], Max;
struct Stack
{
int a[100];
int top;
}Left, Right;
int map[40][40];
//检查给定图是否是K-完美匹配图（这里K == Left.top）
int Process()
{
int i, j;
//Stack Left
//Stack Right
//检查两个栈中是否有完全边,即K*K条边
for(i = 0; i < Left.top; i++)
{
for(j = 0; j < Right.top; j++)
{
if(!map[ Right.a[j] ][ Left.a[i] ])
return 0;
}
}
return 1;
}
//对右边的第一个被左边点枚举到的点进行枚举，枚举它的边子集
int rdfs(int u, int index)
{
int i, size = rvec[u].size();
if(size < Left.top)
return 0;
if(Right.top > Left.top)
return 0;
if(Left.top == Right.top)
{
if( Process() )
return 1;
}
for(i = index; i < size; i++){
Right.a[ Right.top++ ] = rvec[u][i];
if( rdfs(u, i+1) )
return 1;
Right.top --;
}
return 0;
}
//左边任选一个点枚举他的边子集
void ldfs(int u, int index)
{
int i, size = lvec[u].size();
if(Left.top > 10)
return ;
Right.top = 0;
if(Left.top > Max && rdfs(Left.a[0], 0) )
{
if(Left.top > Max)
Max = Left.top;
}
for(i = index; i < size; i++){
Left.a[ Left.top++ ] = lvec[u][i];
ldfs(u, i+1);
Left.top --;
}
}
int main()
{
int i, j;
scanf("%d", &t);
while(t--)
{
Max = 0;
scanf("%d", &n);
memset(map, 0, sizeof(map));
for(i = 1; i <= 36; i++)
{
lvec[i].clear();
rvec[i].clear();
}
memset( bo, 0, sizeof(bo) );
for(i = 0; i < n; i++)
{
scanf("%d %d", &l, &r);
map[l][r] = 1;
bo[ l ] = 1;
}
for(i = 1; i <= 36; i++){
for(j = 1; j <= 36; j++){
if(map[i][j])
{
lvec[i].push_back( j );
rvec[j].push_back( i );
}
}
}
for(i = 1; i <= 36; i++)
{
if(bo[i]){
Left.top = 0;
ldfs(i, 0);
}
}
printf("%d\n", Max);
}
}