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


hungry???s;??????????????????????????//定義一個(gè)全局變量
int??????m=0;??????????????????????????//定義一個(gè)全局變量記錄當(dāng)前系數(shù)陣中的0元素個(gè)數(shù)。

//-----------------------------求每行每列的最小元素------------------------------------//
int?Minimum（int?iint?flag）?????????
{
	int?minj;
	if（flag==1）??????????????????????????????//求行的最小元素時(shí)，將i行第一元素賦予min
	????min=s.matrix[i][1];
	if（flag==0）??????????????????????????????//求列的最小元素時(shí)，將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）??????????????//避免重復(fù)計(jì)算0的個(gè)數(shù)
					???{
						???m++;
						???s.znr[a]++;
					???}
					?s.tz[a][i]=1;
					?s.znc[i]++;
				???}
		}	
				?
	return?min;???????????????????????????????//返回一行或一列的最小值到ChangeMatrix（）
}?
//----------------------------------------END------------------------------------------//








//----------------------------------變換系數(shù)矩陣---------------------------------//
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;?

?屬性????????????大小?????日期????時(shí)間???名稱
-----------?---------??----------?-----??----

?????文件????????323??2005-04-13?22:48??匈牙利算法\測(cè)試?yán)?txt

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

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

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

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