poj 2594 Treasure Exploration 最小路徑覆蓋/最大匹配

poj 2594 Treasure Exploration 最小路徑覆蓋/最大匹配

#include
#include

const int N=510;
int line[N][N];
int mac[N];
int used[N];
int n,m;

void floyd()
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			for(int k=1;k<=n;k++)
			{
				if(line[j][i] && line[i][k])
				{
					line[j][k]=1;
				}
			}
		}
	}
}

bool get_path(int u)
{
	for(int i=1;i<=n;i++)
	{
		if(line[u][i] && !used[i])
		{
			used[i]=1;
			if(mac[i]==-1 || get_path(mac[i]))
			{
				mac[i]=u;
				return 1;
			}
		}
	}
	return 0;
}

int MaxMatch()
{
	int num=0;
	memset(mac,-1,sizeof(mac));
	for(int i=1;i<=n;i++)
	{
		memset(used,0,sizeof(used));
		if(get_path(i))
			num++;
	}
	return num;
}

int main()
{

	while(~scanf(%d%d,&n,&m),m||n)
	{
		memset(line,0,sizeof(line));
		for(int i=0;i