Algoritmul Ford Fulkerson

>Ford Fulkerson – program in C

//Ford F
//nodul de intrare este nodul 1, nodul de iesire este nodul n
#include <stdio.h>
#include <conio.h>
#include <string.h>

struct edge
{
int x;
int y;
int capacitate;
int flux;
}muchie[20];

int i,j,n,m,fluxmax=0,a[20][20],gn[20][20],c[20],drum[20],dimdr;
char eticheta[20];

void citire_date()
{
FILE *f=fopen("retea.txt","r");
int x,y,cap;
//pe prima linie nr de noduri  pe a doua linie nr de muchii
//pe liniile urmatoare se trece x, y, capacitate
fscanf(f,"%d",&n);
fscanf(f,"%d",&m);

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

for(i=1;i<=m;i++)
 {
   fscanf(f,"%d %d %d",&x,&y,&cap);
   a[x][y]=1;
   muchie[i].x=x;
   muchie[i].y=y;
   muchie[i].capacitate=cap;
   muchie[i].flux=0;
 }
}

void afisare_matrice(int mat[20][20])
{
for(i=1;i<=n;i++)
 {
   for(j=1;j<=n;j++)
    printf(" %d ",mat[i][j]);
    printf("n");
 }
}

void construct_matr()
{  //se constr gn, matricea grafului neor asoc retelei
for(i=1;i<=n;i++)
 for(j=1;j<=n;j++)
   gn[i][j]=0;
for(i=1;i<=n;i++)
 for(j=1;j<=n;j++)
   if(a[i][j]==1)
     {
       gn[i][j]=1;
       gn[j][i]=1;
     }
}

int calcul_delta(int vec[20], int dim)
{  //se calc flux minim pe lant
int min=30000;
for(i=1;i<=m;i++)
  for(j=2;j<=dim;j++)
   if (( muchie[i].x==vec[j-1]) && (muchie[i].y==vec[j]))
   //daca x-ul din muchie corespunde cu cel din lantul generat
     if(a[vec[j-1]][vec[j]]==1)
     if(muchie[i].capacitate-muchie[i].flux<min) min=muchie[i].capacitate-muchie[i].flux;
   else if(a[vec[j]][vec[j-1]]==1)
     if(muchie[i].flux<min) min=muchie[i].flux;
return min;
}

int saturat(int vec[20], int dim)
{
int ok=0;
for(j=2;j<=dim;j++) //varfuri
   for(i=1;i<=m;i++)  //muchii
     if (( muchie[i].x==vec[j-1]) && (muchie[i].y==vec[j]))
     if(muchie[i].flux==muchie[i].capacitate)
 ok=1;
return ok;
}

void resetare()
{
for(i=1;i<=n;i++) eticheta[i]='0';
  eticheta[1]='+';
}

void eticheteaza(int vec[20], int dim)
{
int delta;
//if(saturat(vec,dim)==0)
if((eticheta[n]!='+')||(eticheta[n]!='-'))
{
    resetare();
    delta=calcul_delta(vec,dim);
    fluxmax=fluxmax+delta;
  for(j=2;j<=dim;j++) //varfuri
   for(i=1;i<=m;i++)  //muchii
      if (( muchie[i].x==vec[j-1]) && (muchie[i].y==vec[j]))
     if(a[vec[j-1]][vec[j]]==1)
       {
         muchie[i].flux=muchie[i].flux+delta;
      if(vec[j-1]==1) 
           eticheta[vec[i]]='+';
         eticheta[vec[j]]='+';
       }
     else
       {
         muchie[i].flux=muchie[i].flux-delta;
  eticheta[vec[j]]='-';
       }
  }
if((eticheta[n]!='+')&&(eticheta[n]!='-'))
//if(saturat(vec,dim)==0)
      eticheteaza(vec,dim);
}

void verifica_lant(int vec[20], int dim)
{
int ok=1;
for (i=2;i<=dim;i++)
  if(gn [ vec[i-1] ] [ vec[i] ]==0) ok=0;
  if (ok==1)
    eticheteaza(vec,dim);
}

void tipar (int k)
{
int ok=0, aux[20], dimaux=0;
k++;
for(i=1;c[1]==1&&c[i-1]!=n;i++)
 {
   dimaux++;
   aux[dimaux]=c[i];
 }
//se verifica daca lantul generat acum e diferit de cel generat anterior
//if(dimdr!=dimaux)
  for(i=1;i<=dimaux;i++)
    if(drum[i]!=aux[i]) ok=1;
if(ok==1)
  {
    dimdr=dimaux;
    for(i=1;i<=dimdr;i++)
      drum[i]=aux[i];
    verifica_lant(drum,dimdr);
  }
}

int valid (int k)
{
int i, ok=1;
for(i=1;i<=k-1;i++)
 if(c[i]==c[k]) ok=0;
return ok;
}

void bktr (int k)
{
int i;
for(i=1;i<=n;i++)
{
  c[k]=i;
   if(valid (k)==1)
    if(k==n) tipar(k);
    else bktr(k+1);
}
}

void main()
{
citire_date();
construct_matr();
bktr(1);
printf("nFlux max=%dn",fluxmax);
getch();