Thuat toán FF cây cung nhỏ nhất

#include <stdio.h>




typedef int kluong[100][100];

typedef struct {
int dau, truoc, delta, daxet;
}knhan;

int n,s,t,m;
int a[100][100];
knhan nhan[100];
int f[100][100],lt[100][100];
int i,j;


int innhan(){
for (i=1;i<=n;i++)
if (nhan[i].daxet)
printf(" [%d](%c%d,%d),",
i,
nhan[i].dau,
nhan[i].truoc,
nhan[i].delta);
else printf(" %d(%c%d,%d),",
i,
nhan[i].dau,
nhan[i].truoc,
nhan[i].delta);
}

int inmatran(int A[100][100]){
printf("\n");
for (i=1;i<=n;i++){
for (j=1;j<=n;j++)
printf("%4d",A[i][j]);
printf("\n");
}
}

int input(){
int u,v,l,k;
FILE *f=fopen("inputnetwork.txt","r");
fscanf(f,"%d %d %d %d",&n,&m,&s,&t);

for(i=1;i<=n;i++)
for(j=1;j<=n;j++) a[i][j]=0;

for(k=1;k<=m;k++){
fscanf(f,"%d %d %d",&u,&v,&l);
a[u][v]=l;
}
fclose(f);
printf("mang: "); inmatran(a);


}

int min(int a, int b){
return (a<b?a:b);
}

knhan taonhan(int dau, int truoc, int delta, int daxet){
knhan N;
N.dau  =  dau;
N.truoc = truoc;
N.delta  =  delta;
N.daxet = daxet;
return N;
}

int tangluong(){
int x,y;
//7.1
for(i=1;i<=n;i++) nhan[i]=taonhan(0,0,0,0);
nhan[s]=taonhan('+',s,9999999,0);

// lap 7.2

do{//7.2.1
//tim dinh co nhan ma chu xet
for(x=1;x<=n;x++)
if((nhan[x].delta>0) // co nhan
&& (nhan[x].daxet==0)) break; //for x
if(x>n) break; // ket thuc 7.2
else nhan[x].daxet=1;
//nhan[x].daxet=1;
printf("\ndinh xet %d:",x);

//7.2.2 kiem tra cac anh cua x
for(y=1;y<=n;y++)
if((a[x][y]>0) && // la anh
(nhan[y].delta==0)&& //y chua co nhan
(f[x][y]<a[x][y])){ //luong con tang dc
nhan[y]=taonhan('+',x,min(nhan[x].delta,a[x][y]-f[x][y]),0);
printf("\n nhan cua dinh %d: (%c%d,%d)",y,nhan[y].dau,nhan[y].truoc,nhan[y].delta);

if (y==t) break;
}
if(nhan[t].delta>0) break; //7.2
//7.2.3 kiem tra cac tao anh cua x
for(y=1;y<=n;y++)
if((a[y][x]>0) &&
(nhan[y].delta==0 )&&
(f[y][x]>0)){
nhan[y]=taonhan('+',x,min(nhan[x].delta,f[x][y]),0);
printf("\n nhan cua dinh %d: (%c%d,%d)",y,nhan[y].dau,nhan[y].truoc,nhan[y].delta);
if (y==t) break;
}

if(nhan[t].delta>0) break;

}
while(x<=n);
//7.3
 /*lap den khi t co nhan hoac k con tim thaay */

if(nhan[t].delta==0){
  printf("\n k co duong tang luong, nhan: "); innhan();
 
return 0;

}
else{
//lt
//khoi tao lt

for(i=1;i<=n;i++)
for(j=1;j<=n;j++) lt[i][j]=0;

 x=t;
 int gttl=nhan[x].delta;
printf("\nduong tang luong: GTTL = %d ",gttl);
 while(x!=s){
  y=nhan[x].truoc;
  printf("%d <---",x);
  if(nhan[x].dau=='+') lt[y][x]+=gttl;
  else lt[y][x]-=gttl;
  if(y==s) printf("%d",y);
  x=y;

  }
return 1;
}

return 0;
}


int Ford(){

//chuan bi luong
for(i=1;i<n;i++)
for(j=1;j<n;j++) f[i][j]=0;

while(tangluong()){
for(i=1;i<=n;i++)
for(j=1;j<=n;j++) f[i][j]+=lt[i][j];

printf("\nduong tang luong: ");
inmatran(lt);

printf("\nluong sau khi tang: ");
inmatran(f);
}

}


int output(){
int gt=0;
FILE *f1=fopen("outputnetwork.txt","w");

printf("\nket qua: ");
for(i=1;i<=n;i++) gt+=f[s][i];

fprintf(f1,"%d",gt);

printf("\n%d\n",gt);

fprintf(f1,"\n");

for(i=1;i<=n;i++) if(nhan[i].delta>0) {
fprintf(f1,"%d ",i);
printf("%d ",i);}

fprintf(f1,"\n");
printf("\n");

for(i=1;i<=n;i++) if(nhan[i].delta==0) {
fprintf(f1,"%d ",i);
printf("%d ",i);}

fclose(f1);
}
int main(){
input();
Ford();
output();
}