程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> poj 2594 Treasure Exploration 最小路徑覆蓋/最大匹配

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

編輯:關於C++

 

 

#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

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved