assignment problem using c

//PROGRAM FOR ASSIGNMENT PROBLEM
#include
#include
#include
struct table
{
int cost;
int mark;

};
void read(struct table **t1,struct table **t2,int p)
{
int i,j,c;
printf("Enter the cost matrix");
for(i=0;i for(j=0;j {
scanf("%d",&c);
t1[i][j].cost=c;
t1[i][j].mark=0;
t2[i][j].cost=c;
t2[i][j].mark=0;
}

}
void display(struct table **t,int p)
{
int i,j;
printf("\n");
for(i=0;i {
for(j=0;j {
printf("%d\t",t[i][j].cost);

}
printf("\n");
}

}
int row_mini(struct table **t1,int k,int p)
{
int i=k,j=0,min;
min=t1[i][j].cost;
for(j=0;j {

if(t1[i][j+1].cost min=t1[i][j+1].cost;

}
return(min);
}
int col_mini(struct table **t1,int k,int p)
{
int i=0,j=k,min;
min=t1[i][j].cost;
for(i=0;i {

if(t1[i+1][j].cost min=t1[i+1][j].cost;

}
return(min);
}


void row_reduction(struct table **t1,int p)
{
int i,min,j;
struct table *t2[20];
for(i=0;i {

min=row_mini(t1,i,p);
for(j=0;j {
t1[i][j].cost=t1[i][j].cost-min;

}

}
printf("\n after row reduction\n");
display(t1,p);
}
void col_reduction(struct table **t1,int p)
{
int i,min,j;
struct table *t2[20];
for(i=0;i {

min=col_mini(t1,i,p);
for(j=0;j {
t1[j][i].cost=t1[j][i].cost-min;

}

}
printf("\n after column reduction\n");
display(t1,p);
}
void arbcolass(struct table **t1,int p,int cloc)
{
int i,j,flag,row,col;
flag=0;
for(j=0;j {

if(t1[j][cloc].cost==0 && t1[j][cloc].mark==0&&flag==0)
{
t1[j][cloc].mark=1;
flag=1;
row=j;
}
if(t1[j][cloc].cost==0 && t1[j][cloc].mark==0&&flag==1)
t1[j][cloc].mark=-1;

}
for(j=0;j {
if(t1[row][j].cost==0 && t1[row][j].mark==0)
t1[row][j].mark=-1;
}
}
void arbrowass(struct table **t1,int p,int rloc)
{
int i,j,flag,row,col;
flag=0;

for(j=0;j {

if(t1[rloc][j].cost==0 && t1[rloc][j].mark==0&&flag==0)
{
t1[rloc][j].mark=1;
col=j;
flag=1;
}
if(t1[rloc][j].cost==0 && t1[rloc][j].mark==0&&flag==1)
t1[rloc][j].mark=-1;

}
for(j=0;j {
if(t1[j][col].cost==0 && t1[j][col].mark==0)
t1[j][col].mark=-1;
}
}
void make_arbitryass(struct table **t1,int p)
{
int i,j,flag,count,count1,*rowc,*colc,min,rmin,cmin,k,cloc,rloc;
count1=count=0;
colc=(int *)malloc(sizeof(int)*p);
rowc=(int *)malloc(sizeof(int)*p);
for(i=0;i {
count=0;
for(j=0;j {
if((t1[i][j].cost==0)&&(t1[i][j].mark==0))
{
count++;

}
}
rowc[i]=count;
}
rmin=999;
for(k=0;k if(rowc[k] {
rmin=rowc[k];
rloc=k;
}


for(i=0;i {
count1=0;
for(j=0;j {
if(t1[j][i].cost==0 && t1[j][i].mark==0)
{
count1++;

}
}
colc[i]=count1;
}
cmin=999;
for(k=0;k if(colc[k] {
cmin=colc[i];
cloc=k;
}
if(cmin<=rmin)
{
arbcolass(t1,p,cloc);

}
else
{
arbrowass(t1,p,rloc);


}
}

void assign(struct table **t1,int p)
{
int count,count1,col,row,i,j,flag;
label:
flag=0;
for(i=0;i {
count=0;

for(j=0;j {
if(t1[i][j].cost==0 && t1[i][j].mark==0)
{
col=j;
count++;
}
}

if(count==1)
{
flag=1;
for(j=0;j {
if(t1[j][col].cost==0 && t1[j][col].mark==0)
t1[j][col].mark=-1;
}
t1[i][col].mark=1;

}

}
for(i=0;i {
count1=0;
for(j=0;j {
if(t1[j][i].cost==0 && t1[j][i].mark==0)
{
row=j;
count1++;
}
}

if(count1==1)
{
flag=1;
for(j=0;j {
if(t1[row][j].cost==0 && t1[row][j].mark==0)
t1[row][j].mark=-1;
}
t1[row][i].mark=1;

}

}
if(ifall_marked(t1,p) &&flag==1)
goto label;
else
if(flag==0 && ifall_marked(t1,p))
{
make_arbitryass(t1,p);
goto label;
}
}


int ifall_marked(struct table **t1,int p)
{
int i,j;
for(i=0;i for(j=0;j {
if(t1[i][j].cost==0)
if(t1[i][j].mark==0)
return 1;
}
return 0;
}
int count_assign(struct table **t1,int p)
{
int count=0,i,j;
for(i=0;i {
for(j=0;j {
if(t1[i][j].mark==1)
count++;
}
}
return count;
}
void reduction(struct table **t1,int p, int *rtick,int *ctick)
{
int i,j,min;
min=minimum(t1,p,rtick,ctick);
for(i=0;i for(j=0;j {
if((rtick[i]==1)&&(ctick[j]==0))
t1[i][j].cost-=min;
if((rtick[i]==0)&&(ctick[j]==1))
t1[i][j].cost+=min;
}
}
int minimum(struct table **t1,int p,int *rtick,int *ctick)
{
int i,j,min;
min=t1[i][j].cost;
for(i=0;i for(j=0;j {
if(t1[i][j].mark!=2)
if(t1[i][j].cost min=t1[i][j].cost;
}
return min;
}
void tick(struct table **t1,int p,int *rtick,int *ctick)
{
int i,j,k,count,loc;
for(i=0;i {
count=0;
for(j=0;j {
if(t1[i][j].mark==1&&t1[i][j].cost==0)
{
count++;
} }

if(count==0)
{
for(k=0;k if(t1[i][k].mark==-1)

loc=k;

rtick[i]=1;
ctick[loc]=1;
}

for(k=0;k {
if(t1[k][loc].mark==1)
rtick[k]=1;
}
}



for(i=0;i {
if(rtick[i]==0)
{
for(j=0;j {
t1[i][j].mark=2;
}
}
}
for(i=0;i {
if(ctick[i]==1)
{
for(j=0;j {
t1[j][i].mark=2;
}
}
}

}
void clear_mark(struct table **t1,int p)
{
int i,j;
for (i=0;i {
for(j=0;j {
t1[i][j].mark=0;
}
}
}
int solution(struct table **t1,struct table**t2,int p)
{
int sol=0,i,j;
for(i=0;i {
for(j=0;j {
if(t1[i][j].mark==1)
sol+=t2[i][j].cost;
}
}
return sol;
}
void main()
{
int p,c,i,*rtick,*ctick,j;
struct table **t1,**t2;
clrscr();
printf("\t\tAssignment problem");
printf("\n\t\t*****************");
printf("Enter the order");
scanf("%d",&p);
rtick=(int *)malloc(sizeof(int)*p);
ctick=(int *)malloc(sizeof(int)*p);
t1=(struct table **)malloc(sizeof(struct table *)*p);
t2=(struct table **)malloc(sizeof(struct table *)*p);
for(i=0;i {
rtick[i]=0;
ctick[i]=0;
}
for(i=0;i {
t1[i]=(struct table *)malloc(sizeof(struct table)*p);
t2[i]=(struct table *)malloc(sizeof(struct table)*p);
}
read(t1,t2,p);
printf("\nBefore reduction\n");
display(t1,p);
row_reduction(t1,p);
col_reduction(t1,p);
assign(t1,p);

if(count_assign(t1,p) {

tick(t1,p,rtick,ctick);
reduction(t1,p,rtick,ctick);
clear_mark(t1,p);
assign(t1,p);

}

printf("The optimal solution is %d",solution(t1,t2,p));

getch();
}