学步园

匈牙利算法：

找一条已经被匹配上的边和未被匹配上的边相互交替的路径，这条路径长度为奇数并且未被匹配上的边比被匹配上的边多1。通过把增广路上未被匹配上的边改为匹配上的边，而匹配上的边全部改为未被匹配上的边，就可以把匹配数加1。重复此操作直到再也找不到这样的路径。

例如：

第一步：我们从点a找到了与a有路径的点d，由于点d没有匹配到，所以直接添加a、d边。

第二步：搜索点b，通过b点找到d点，此时d点已经被匹配到，尝试搜索a点是否能找到增广路径，此时找到了e点。

第三步：用a、e边和b、d边更新该图，此时匹配数增加1.

第四步：搜索点c，此时找到点d，此时d点已经比匹配到，尝试搜索b点是否能找到增广路径，此时找不到了，结束搜索。

第五步：最终得到最大匹配数为2。

（第二步中：bd边、ad边、ae边就是一条匹配的和未匹配的边相互交替的路径，长度为奇数，此时未匹配上的边比已匹配上的边多1）

2063-过山车

使用匈牙利算法解决：

#include <iostream>
#include <cstring>
using namespace std;

int n1,n2,m,ans;
int result[1010];//记录V2中的点匹配的点的编号
bool state[1010];//记录V2中的每个点是否被搜索过 
bool data[1010][1010];//邻接矩阵 true代表有边相连  

void init ()
{
	int t1,t2;
	memset (data, 0, sizeof (data));
	memset (result, 0, sizeof (result));
	ans = 0;
	cin>>n1>>n2;
	for (int i = 1; i <= m; i++)
	{
		cin>>t1>>t2;
		data[t1][t2] = true;
	}
	return;
}

bool find (int a)
{
	for (int i = 1; i <= n2; i++)
	{
		if (data[a][i] == 1 && !state[i])//如果节点i与a相邻并且未被查找过
		{
			state[i] = true;//标记i为已查找过
			if (result[i] == 0 || find(result[i]))
			{//如果i未在前一个匹配M中或者i在匹配M中，但是从与i相邻的节点出发可以有增广路
				result[i] = a;//记录查找成功记录 　
				return true;//返回查找成功
			}
		}
	}
	return false;
}

int main()
{
	while (cin>>m&&m)
	{
		init ();
		for (int i =1; i <= n1; i++)
		{
			memset(state, 0, sizeof (state));//清空上次搜索时的标记 
			if (find(i))
				ans++;//从节点i尝试扩展 　　
		}
		cout<<ans<<endl;
	}
	return 0;
}