///////////////////////////////////匈牙利算法///////////////////////////////
//2005.written?by?shenhui
///////////////////////////////////////////////////////////////////////////////////////////
//????????????????????????????????????????????????????????????????????????????????????????
//?理論依據是D.Konig的“矩陣中獨立零元素的定理”，以及一個性質：若從指派問題的系數矩陣的?
//?某行或某列分別減去一個常數k，得到一個新的矩陣與原矩陣具有相同的最優解。???????????????
//?算法描述：
//?????????一，變換系數矩陣：各行減去各行的最小元素，各列也一樣。對應程序中的ChangeMatrix?
//?????????????（）函數，Minimum（）子函數。
//?????????二，對一中得到的新矩陣確定獨立零元素個數，若為矩陣階數則以得到結果，退出；否則??????
//?????????????作能覆蓋所有零元素的最少直線數目的直線集合，并轉第三步。對應程序中的
//?????????????Drawcircle（）函數，subroute（）子函數，Modify（）函數。?????????????????
//?????????三，繼續變換系數矩陣，在未被直線覆蓋的元素中找到一個最小元素，對未被直線覆蓋的
//?????????????元素所在行中各元素都減去這一最小元素，為消除負元素，只要對他們所在列中各元
//?????????????素都加上這一最小元素即可，轉第二步。對應程序中的ChangeMatrix1（）函數。
//
//////////////////////////////////////////////////////////////////////////////////////////?
#include?“iostream.h“
#define?n??8
typedef?struct?node?{
	??????int?matrix[n+1][n+1];??????????????//系數矩陣
		??int?tz[n+1][n+1];??????????????//標記系數陣中0元素的位置
		??int?ti[n+1][n+1];??????????????//標記獨立0元素的位置
		??int?znr[n+1];????????????????//記錄每行0元素的個數，這些0沒有被畫圈和劃去
		??int?znc[n+1];????????????????//記錄每列0元素個數
		??int?row[n+1];????????????????//標記某行是否劃‘對鉤’。row[i]=1
		??int?ri[n+1];?????????????????//標記某行是否有獨立0元素。ri[i]=1
		??int?col[n+1];????????????????//標記某列是否劃‘對勾’。col[i]=1
??????????
}hungry;


hungry???s;??????????????????????????//定義一個全局變量
int??????m=0;??????????????????????????//定義一個全局變量記錄當前系數陣中的0元素個數。

//-----------------------------求每行每列的最小元素------------------------------------//
int?Minimum（int?iint?flag）?????????
{
	int?minj;
	if（flag==1）??????????????????????????????//求行的最小元素時，將i行第一元素賦予min
	????min=s.matrix[i][1];
	if（flag==0）??????????????????????????????//求列的最小元素時，將i列第一元素賦予min
		min=s.matrix[1][i];
	if（flag==1）
	{
		for（j=1;j<=n-1;j++）??????????????????//選擇法求最小元素?
		{
			if（min>=s.matrix[i][j+1]）
	?			min=s.matrix[i][j+1];
		}
	????for（int?a=1;a<=n;a++）
			if（s.matrix[i][a]==min）
				{
					s.tz[i][a]=1;
			????????s.znr[i]++;
		????????????m++;
				}
			
	}
????else?if（flag==0）
			{
			?for（j=1;j<=n-1;j++?）
			?{
				?if（min>=s.matrix[j+1][i]）
			????????min=s.matrix[j+1][i];
			?}
			?for（int?a=1;a<=n;a++）
				???if（s.matrix[a][i]==min）
				???{
					???if（s.tz[a][i]!=1）??????????????//避免重復計算0的個數
					???{
						???m++;
						???s.znr[a]++;
					???}
					?s.tz[a][i]=1;
					?s.znc[i]++;
				???}
		}	
				?
	return?min;???????????????????????????????//返回一行或一列的最小值到ChangeMatrix（）
}?
//----------------------------------------END------------------------------------------//








//----------------------------------變換系數矩陣---------------------------------//
void?ChangeMatrix（）?????????????????????????
{
	int?ijmin;
	for（i=1;i<=n;i++）
	{
		min=Minimum（i1）;?????????????????//求第i行的最小元素
????????for（j=1;j<=n;j++）
			s.matrix[i][j]-=min;?

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件????????323??2005-04-13?22:48??匈牙利算法\測試例子.txt

?????文件???????9997??2005-04-18?16:42??匈牙利算法\匈牙利算法!.cpp

?????目錄??????????0??2005-07-16?12:25??匈牙利算法

-----------?---------??----------?-----??----

????????????????10538????????????????????4