dss.cpp

这是一个使用VC++编写的“智能支持决策系统DSS源程序”

// DSS.cpp : Defines the entry point for the console application.
//分配问题/匈牙利算法

#include "stdafx.h"

#include<iostream>
using std::cout;
using std::cin;
using std::endl;

#include<iomanip>
using std::setw;

#include<ctime>

#include<cstdlib>

#define size 5


int mark1[size][size]={0};//标记分配：三角为1；叉为2；无符号为0

//函数原型
void allocation(int a[][size] );
void judge(int b[][size]);
void domark(int c[][size]);


void main()
{   
    /////////////第一小步///////////
	int array[size][size];
	int i,j,k;

	srand(time(0));
	
	//cout<<"请输入效能矩阵的大小：";
    //cin>>size; 
    
	/*int ** array;//二维数组的动态分配
	array = new int * [size];
	for (i = 0 ; i < size; i++)
		array[i] = new int [size];*/
	
    
	char attribute;
	cout<<"请输入此分配问题所求效能矩阵的性质（b or s）：";
	cin>>attribute;

   	
	//cout<<"请输入矩阵("<<size<<"*"<<size<<"):"<<endl;
    for(i=0;i<size; i++){
		for(j=0;j<size; j++)
			array[i][j]=rand()%101;						
	}

	
	
	
    if(attribute=='b'){
		for(i=0;i<=size-1;i++){
			for(j=0;j<=size-1;j++)
				array[i][j]*=(-1);
		}
	}
	
    ////////////////第二小步///////////

    int min;
    
	for(i=0;i<size;i++){
		min=array[i][0];
		for(j=0;j<size;j++){
			if(array[i][j]<min)
				min=array[i][j];
		}
		for(k=0;k<size;k++)
			array[i][k]-=min;
	}


	
    /////////////第三小步////////////

	for(j=0;j<size;j++){
		min=array[0][j];
		for(i=0;i<size;i++){
			if(array[i][j]<min)
				min=array[i][j];
		}
		for(k=0;k<size;k++)
			array[k][j]-=min;
	}

	allocation(array);
    

}

//分配标记

void allocation(int a[][size])
{
	////////////第四步//////////////

	
	int i,j,zeronumber,k;
	int r,c;//行，列

	/*mark1 = new int * [s];//动态的数组分配
	for (i = 0 ; i < s; i++)
         mark1[i] = new int [s];*/

    //for(i=0;i<size;i++)//数组初始化为0
	//	for(j=0;j<size;j++)
	//		mark1[i][j]=0;
	

	///////////第五步///////////////

	for(i=0;i<size;i++){
	     zeronumber=0;
		for(j=0;j<size;j++){
			if(a[i][j]==0&&mark1[i][j]==0){
				++zeronumber;
				r=i;
				c=j;
			}			
		}
		if(zeronumber==1){
			mark1[r][c]=1;
			for(k=0;k<size;k++){
				if(a[k][c]==0&&mark1[k][c]==0)
					mark1[k][c]=2;
			}
		}
	}

    

	
	////////////////第六步/////////////////
    
	for(j=0;j<size;j++){
	     zeronumber=0;
		for(i=0;i<size;i++){
			if(a[i][j]==0&&mark1[i][j]==0){
				++zeronumber;
				r=i;
				c=j;
			}			
		}
		if(zeronumber==1){
			mark1[r][c]=1;
			for(k=0;k<size;k++){
				if(a[r][k]==0&&mark1[r][k]==0)
					mark1[r][k]=2;
			}
		}
	}
	
	/////////////////第七步/////////////////
    judge(a);//情况判断函数

}

void judge(int b[][size])
{
	int i,j,k;
	int none[size]={0};//一行内没有做标记的零元素的个数
	int tri[size]={0};//一行内打三角的零元素的个数
	int cross[size]={0};//一行内打叉的零元素的个数
	int r[size]={0};//存放最终结果的行
	int c[size]={0};
	int nonerow[size]={-1};
	int nonecolumn[size]={-1};
	int c1=0,c2=0,c3=0;
	int temp[size]={0};

		
	for(i=0;i<size;i++){
		for(j=0;j<size;j++){
			if(b[i][j]==0&&mark1[i][j]==0){
				none[i]++;
				nonerow[i]=i;
				nonecolumn[i]=j;
			}
			else if(b[i][j]==0&&mark1[i][j]==1){
				tri[i]++;
				r[i]=i;
				c[i]=j;
			}
			else if(b[i][j]==0&&mark1[i][j]==2)
				cross[i]++;
			else
				;
		}
	}

    
		
	
	for(i=0;i<size;i++){
		if(tri[i]==1)
			c1++;
		if(none[i]==0)
			c2++;
		if(none[i]>=2){
			c3++;
			temp[i]++;
		}
	}

	if(c1==size){//第一种情况
		cout<<"完全分配的最优解为："<<endl;
		for(i=0;i<size;i++)
			cout<<setw(4)<<r[i]<<setw(4)<<c[i]<<endl;
	}
	else if(c2==size)//第二种情况
		domark(b);
	else if(c3>=2){//第三种情况
		for(i=0;i<size;i++){
			if(temp[i]==1){
				if(mark1[nonerow[i]][nonecolumn[i]]==0){
					mark1[nonerow[i]][nonecolumn[i]]=1;				
					for(k=0;k<size;k++){
						if(b[nonerow[i]][k]==0&&mark1[nonerow[i]][k]==0)
							mark1[nonerow[i]][k]=2;
						}
					for(j=0;j<size;j++){
						if(b[j][nonecolumn[i]]==0&&mark1[j][nonecolumn[i]]==0)
							mark1[j][nonecolumn[i]]=2;
						}
					}
				else
					break;
			}
		}

		
		allocation(b);
	}
	else
		allocation(b);
}

//第三步与第四步
void domark(int c[][size])
{
	int mark2[size]={0};//打勾为1;行
	int mark3[size]={0};//列
	int i,j,k;
	int trinumber=0;
	int temp2[size];//过渡数组
	int temp3[size];
	int end=0;

	
 /////////////第八步///////////////////

	for(i=0;i<size;i++){
		for(j=0;j<size;j++){
			if(mark1[i][j]==1){
				mark2[i]=0;
				break;
			}
			else
				continue;
		}
		if(j==size)
			mark2[i]=1;
		
	}

	
//////////////第九步/////////////////////
	
	do{//通过把前后的数组进行比较，以跳出循环
		end=0;
		for(i=0;i<size;i++)
			temp2[i]=mark2[i];

		for(i=0;i<size;i++)
			temp3[i]=mark3[i];

		for(i=0;i<size;i++){
			if(mark2[i]==1){
				for(j=0;j<size;j++){
					if(c[i][j]==0)
						mark3[j]=1;
					}
				}
			}
		
///////////////第十步/////////////////////
		for(i=0;i<size;i++){
			if(mark3[i]==1){
				for(j=0;j<size;j++){
					if(mark1[i][j]==1)
						mark2[i]=1;
					}
				}
			}
		for(k=0;k<size;k++){
			if((temp2[k]==mark2[k])&&(temp3[k]==mark3[k]))
				continue;
			else{
				end=1;
				break;
			}
		}

	}while(end==1);

	
	/////////////////第十三步////////////////
	int min;

	for(i=0;i<size;i++){
		if(mark2[i]==0)
			continue;
		else{
			min=c[i][0];
			for(j=0;j<size;j++){
				if(mark3[j]==1)
					continue;
				else{
					if(c[i][j]<min)
						min=c[i][j];
				}
			}
		}
	}
	//cout<<min<<endl;//找到最小值

	for(i=0;i<size;i++){
		if(mark2[i]==0)
			continue;
		else{
			for(j=0;j<size;j++)
				c[i][j]-=min;
			}
	}//未画横线的各行都减最小值

	/*for( k=0;k<size; k++){
		for(int p=0;p<size; p++)
			cout<<setw(6)<<c[k][p];
    	if(p==size)
			cout<<endl;
	}*/

	for(i=0;i<size;i++){
		if(mark3[i]==0)
			continue;
		else{
			for(j=0;j<size;j++)
				c[j][i]+=min;
			}
	}//已画竖线的各列都加最小值


	/*for( k=0;k<size; k++){
		for(int p=0;p<size; p++)
			cout<<setw(6)<<c[k][p];
    	if(p==size)
			cout<<endl;
	}*/

	for(i=0;i<size;i++)
		for(j=0;j<size;j++)
			mark1[i][j]=0;//对各行、列做无标记处理

   allocation(c);



}