#include <iostream.h>
#include <limits.h>
#include <iomanip.h>
#include <math.h>

const int SIZE=6;

void transport(int m,int n,int inf,int a[],int b[],
           int c[SIZE][SIZE],int x[SIZE][SIZE],int &ko);

int main()
{
	int m=5,n=7,inf=INT_MAX;
	int a[SIZE]={0,30,10,45,30},
	int b[SIZE]={0,25,20,6,7,22,35};
	
	int c[SIZE][SIZE]=
	{{0, 0, 0, 0, 0, 0, 0},
	{ 0,30,11, 5,35, 8,29},
	{ 0, 2, 5, 2, 5, 1, 9},
	{ 0,35,20, 6,40, 8,33},
	{ 0,19, 2, 4,30,10,25}};

	int X[SIZE][SIZE];
	int KO;
	int x,y;

	cout<<"The array:"<<endl;
	for (x=1;x<=m;x++)
	{
		for(y=1;y<=n;y++)
			cout<<setw(4)<<c[x][y];
		cout<<endl;
	}
    
    transport(m,n,inf,a,b,c,X,KO);

	cout<<"The Solution:"<<endl;
	for (x=1;x<=n;x++)
	{
		for(y=1;y<=n;y++)
			cout<<setw(4)<<X[x][y];
		cout<<endl;
	}
    cout<<"KO="<<KO<<endl;
	cout<<endl<<"The array:"<<endl;

	for (x=1;x<=m;x++)
	{
		for(y=1;y<=n;y++)
			cout<<setw(4)<<c[x][y]*X[x][y];
		cout<<endl;
	}

	return 0;
}

void transport(int m,int n,int inf,int a[],int b[],
         int c[SIZE][SIZE],int X[SIZE][SIZE],int &KO)
{
	int i,j,sf,r,ra;
	bool lab,lab1,lab2;
	int u[SIZE],w[SIZE],eps[SIZE];
	int v[SIZE],k[SIZE],del[SIZE];

	for (i=1;i<=m;i++) u[i]=0;
	for (j=1;j<=n;j++)
	{
		r=inf;
		for (i=1;i<=m;i++)
		{
			X[i][j]=0;
			sf=c[i][j];
			if (sf<r) r=sf;
		}
		v[j]=r;
	}
	lab1=false;

	do  //until lab1, which indicates optimal solution
	{

		for(i=1;i<=m;i++)
		{
			w[i]=0;
			eps[i]=a[i];
		}
		for (j=1;j<=n;j++)
			k[j]=del[j]=0;
		do   //until lab   this is labelling rows and columns
		{

			lab=true;  //lab becomes false when a column is labeled
			lab2=true; //lab2 is false is breakthrough
			i=0;       //appears, and true otherwise    jj fix
			do  //until i=m or lab2=false
			{

				i++;
				sf=eps[i];
				eps[i]=-sf;
				if (sf>0)
				{
					ra=u[i];
					j=0;                              //JJ fix
					do  //until j=n or lab2=false
					{

						j++;
						if ((del[j]==0)&&((v[j]-ra)==c[i][j]))
						{                   //element I,J is admissible

							k[j]=i;         //column j can be labelled
							del[j]=sf;
							lab=false;

							if (b[j]>0)          //breakthrough
							{

								lab=true;
								lab2=false;
								sf=abs(del[j]);
								r=b[j];
								if (r<sf) sf=r;
								b[j]=r-sf;
								do
								{
									i=k[j];
									X[i][j]=X[i][j]+sf;
									j=w[i];
									if (j!=0) X[i][j]=X[i][j]-sf;
								} while (j!=0);
								a[i]=a[i]-sf;
								j=0;    //jj fix
								do
								{

									j++;
									lab1=(b[j]<=0);
								}while ((j!=n)&&lab1);
								if (lab1)
								{   //optimal solution has been found
									sf=0;
									for (i=1;i<=m;i++)
										for (j=1;j<=n;j++)
										{
											r=X[i][j];
											if (r>0) sf=sf+r*c[i][j];
										}
									KO=sf;
								}  //end if(lab1)
							}  //end breakthrough
						}  //end labeling column
					}while ((j<n)&&lab2);
				}   //sf>0
			}while ((i<m)&&lab2);

			if (!lab)
			{         //labeling rows and columns
				lab=true;
				for (j=1;j<=n;j++)
				{
					sf=del[j];
					if (sf>0)
					{
						for (i=1;i<=m;i++)
							if (eps[i]==0)
							{
								r=X[i][j];
								if (r>0)
								{
									w[i]=j;
									if (r<=sf) eps[i]=r;
									else eps[i]=sf;
									lab=false;
								}
							}  //end i loop and eps[i]=0
						del[j]=-sf;
					}   //sf>0
				}  //j loop
			}  //not lab
		} while (!lab);

		if (lab2)
		{

			r=inf;
			for (i=1;i<=m;i++)
				if (eps[i]!=0)
				{
					ra=u[i];
					for (j=1;j<=n;j++)
						if (del[j]==0)
						{
							sf=c[i][j]+ra-v[j];
							if (r>sf) r=sf;
						}
				}  //i loop, eps[i]!=0
			for (i=1;i<=m;i++)
				if (eps[i]==0) u[i]+=r;
			for (j=1;j<=n;j++)
				if (del[j]==0) v[j]+=r;
		}  //end lab2
		
	}while (!lab1);
	
return;
}