匈牙利算法指派问题C++代码

匈牙利算法的C++实现，解决指派问题，含有注释，可以直接编译使用，很好很强大！

///////////////////////////////////匈牙利算法///////////////////////////////
//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