Code:
#include <stdio.h>
#define MAX 1000 /* Array limit */
int percurso[MAX]; /* must be dinamic */
int cara=0,coroa=0;
int maxpeso=-1000000000; /* another infinite */
int in;
int ja_ta=0;
int somei=0;
typedef struct as_adjacencias
{
int vertice;
int peso;
struct as_adjacencias *proximo;
} ADJACENCIAS;
typedef ADJACENCIAS* adjacencias;
void insere (adjacencias* Adjacencias, int nof, int peso)
{
if(*Adjacencias == NULL)
{
*Adjacencias=(adjacencias)malloc(sizeof(ADJACENCIAS));
if(*Adjacencias == NULL)
return;
(*Adjacencias) -> vertice=nof;
(*Adjacencias) -> peso=peso;
(**Adjacencias).proximo = NULL;
}
else
insere (&(**Adjacencias).proximo, nof, peso);
}
adjacencias proximo_elemento (int elemento, adjacencias* Adjacencias)
{
if (elemento == (*Adjacencias) -> vertice)
return (**Adjacencias).proximo;
return proximo_elemento (elemento, &(**Adjacencias).proximo);
}
adjacencias lista[7001]; /*must be dinamic */
void poe_na_fila(int x)
{
percurso[coroa]=x;
coroa++;
}
int peso_elemento(adjacencias *Adjacencias, int b)
{
if (b== (*Adjacencias) -> vertice)
return (*Adjacencias) -> peso;
return peso_elemento (&(**Adjacencias).proximo,b);
}
int somador(int percurso[],int nos)
{
int i=0,soma=0;
somei=1;
for(i=0; i< coroa-1;i++)
soma += peso_elemento(&lista[percurso[i]],percurso[i+1]);
return soma;
}
void max_peso(int source, int sink, int nodes, adjacencias proximo)
{
int u = 0, n = 0;
if ( ja_ta ) return;
if (proximo==NULL && source == in)
{
ja_ta = 1;
return;
}
else
{
if (source == sink) {
poe_na_fila(source);
}
else
{
if (proximo==NULL)
{
percurso[coroa] = 0;
coroa -= 1;
max_peso(percurso[coroa], sink, nodes,proximo_elemento(source, &(*(lista+percurso[coroa]))));
}
else
{
poe_na_fila(source);
max_peso(proximo->vertice, sink, nodes, lista[proximo->vertice]);
}
}
if ( ja_ta ) return;
else
{
n = somador(percurso, nodes);
if (n > maxpeso)
maxpeso = n;
coroa = coroa - 1;
percurso[coroa] = 0;
coroa = coroa - 1;
max_peso(percurso[coroa], sink, nodes, proximo_elemento(source, &(*(lista+percurso[coroa]))));
}
}
}
main (int argc, char *argv[])
{
int noi,nof,peso,i,u,j,arcos,nos,inicio,fim;
inicio=fim=noi=nof=i=j=peso=arcos=nos=u=0;
FILE *fp;
fp=fopen(argv[1],"r");
if (fp==NULL)
printf("Impossível abrir o ficheiro %s", argv[1]);
else
{
fscanf(fp,"%d",&nos);
fscanf(fp,"%d",&arcos);
for(u=0;u<=nos;u++)
{
percurso[u]=0;
}
for(j=0; j<=nos;j++)
lista[j]=NULL;
for(i=0;i<arcos;i++)
{
fscanf(fp,"%d %d %d", &noi,&nof,&peso);
insere(&lista[noi],nof,peso);
}
fscanf(fp,"%d %d", &inicio, &fim);
in=inicio;
max_peso(inicio,fim,nos,lista[inicio]);
if(somei)
printf("%d\n",maxpeso);
else
printf("NA\n");
}
}
As I said in previous posts,the idea is to calculate max flow along a directed graph.The path is stored in the array percurso.For example: