%d0%d9%d1%c0%c0%fb_dfs.cpp

ACM经典算法ACM经典算法ACM经典算法

#include<cstdio>
#include<memory.h>
const int MAX = 1000;
bool map[MAX][MAX],visit[MAX];
int match[MAX];
int a,b;//a,b为二分图两部分集合的元素个数 
bool DFS(int i)//DFS查找交替链 
{
	int j,k;
	for(j=0;j<b;j++)
	{
		if(map[i][j] && !visit[j])
		{
			visit[j] = true;
			k=match[j];
			match[j]=i;
			if(k== -1||DFS(k))
				return true;
			match[j] = k;
		}
	}
	return false;
}
int Hungary()//匈牙利算法 
{
	int	i,ans = 0;
	memset(match,-1,sizeof(match));
	for(i=0;i<a;i++)
	{
		memset(visit,0,sizeof(visit));
		if(DFS(i)) ans++;
	}
	return ans;//返回最大匹配的个数 
}
int main()
{
    int i,n,t,res;
    scanf("%d%d",&a,&b);//读入两部分元素个数 
    memset(map,0,sizeof(map));
   //
   //向map中读入图. xi与yi相连表示为map[xi][yi]=true;
   //所有结点编号从0开始 
   //
    res=Hungary();
    return 0;
}