【匈牙利算法】

這是一個在二分圖中尋找最大匹配的算法。

基本思路：尋找增廣路徑，它是一種用增廣路徑求二分圖最大匹配的算法，找不到增廣路時，達到最大匹配。所謂的增廣路徑，就是從一個未匹配點出發，經過非匹配邊，匹配邊，非匹配邊，如果能到達一個未匹配點，則這條交替路稱為增廣路徑。對于增廣路徑，我們必定能重新調整匹配，使得我們的匹配邊+1。

例子：現在假設有3個女生3個男生，每個人都可能對多個異性有好感，假設1號男生喜歡1號,3號女生，2號男生喜歡1號，2號女生，3號男生喜歡2號、3號女生。現在我們跑一遍匈牙利算法。從1號男生起，1號女生跟他相連，并且沒有被匹配，因此1號男生跟1號女生之間匹配。然后我們為2號男生匹配，他喜歡1號女生，然而1號女生已經匹配給1號男生了，那我們看一下1號男生是否有別的女生可以匹配，結果是有的，3號女生。（3號女生也已經匹配，）于是1號男生跟3號女生，2號男生跟1號女生匹配。這便是增廣路的一個例子。最后3號男生跟2號女生匹配，整個算法完成。

下面是代碼：

int e[51][51];//保存一個圖int vis[51];int match[51];int dfs(int u){	for(int i=1;i<=n;i++)	{		if(vis[i]==0&&e[u][i]==1)//如果這個點訪問過，并且他們之間有邊相連		{			vis[i]=1;			if(match[i]==0||dfs(match[i]))//這個點還沒有被匹配或者他原來匹配的點可以去匹配另外的點，如果有，則存在增廣路。這是一個遞歸過程 			{				match[i]=u; //標記i與u匹配 				return 1;			}		}		}	return 0;}  int main() {	//省略讀取數據操作 	tot=0;	for(int i=1;i<=n;i++)	{		memset(vis,0,sizeof(vis));			if(dfs(i))			tot++;//如果當前點可以匹配，則最大匹配數+1 	} }