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