二分匹配部分

[c]代码库

int n1,n2,edge;
int map[M][M];//邻接矩阵 
int vis[M];//n2,集合中对每一个点的访问做标记 
int match[M};//表示当前n1中可以与 n2 集合中相邻的点 
void init( )
{
	int n1,n2,edge;
	scanf("%d%d%d",&n1,&n2,&edge);
	memset(map,0,sizeof(map));
	memset(match,0,sizeof(match));
	for(int i=0;i<edge;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		map[x][y]=1;
	}
}

int find(int node)//是否存在n1集合中以结点node开始的增广路 
{
  for(int i=1;i<=n2;i++)
    if(map[node][i]&&!vis[i]==0)//如果节点 i 与 node相邻并且未访问过 
	{
	  vis[i]=1;
	  if(match[i]==-1||find(match[i]))//如果找到一个未覆盖点i中或从与i相邻的节点出发有增广路
	  {
	    match[i]=node;
		return 1;	
	  }	
	}	
  return 0;
} 

int result_max_match(int n1)//返回最大二分匹配值 
{
  int i,ans=0;
  for(i=1;i<=n1;i++)
  {
  	memset(vis,0,sizeof(vis));//注意初始化 
  	if(find(i))
  	  ans++;
  }
  return ans;
}