問題描述：
給定一些關(guān)系，是個(gè)二分圖，要求它的最大完美匹配。
解題思路：
枚舉左邊的點(diǎn)，對(duì)任意一個(gè)點(diǎn)枚舉它的邊子集，再在枚舉到的邊子集的右邊點(diǎn)集中以相同方式枚舉，最后形成左右兩邊均為K的點(diǎn)，檢測是否為完全二分圖即可。
代碼如下：
#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
//檢查兩個(gè)棧中是否有完全邊,即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;
}
//對(duì)右邊的第一個(gè)被左邊點(diǎn)枚舉到的點(diǎn)進(jìn)行枚舉，枚舉它的邊子集
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;
}
//左邊任選一個(gè)點(diǎn)枚舉他的邊子集
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);
}
}