Edmonds Karp

gistfile1.txt

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>

using namespace std;

#define min(a, b) (a<b?a:b)

/*  (())
 * G[][]: rede.
 * Gf[][]: rede residual.
 * f[][]: fluxo.                      
 */
int G[1000][1000];
int Gf[1000][1000];
int f[1000][1000];

/* 
 * pai[]: vetor que guarda o vertice "pai" na "Busca em Largura".
 * visitado[]: vetor que indica se o vertice ja foi visitado na "Busca em Largura": 0 -> nao visitado, 1 -> visitado.
 */
int pai[1000], visitado[1000];

/* 
 * Funcao implementando "Busca em Largura" para ser utilizada na rede residual.
 * s: vertice de origem.
 * t: vertice de destino.
 * n: numero de vertices.
 * retorna: 1 se houver caminho de s ate t; 0 caso contrario.
 */
int buscaLarg(int s, int t, int n) {

	int u;
	queue<int> fila;

	memset(pai, 0, sizeof(pai));
	memset(visitado, 0, sizeof(visitado));

	visitado[s] = 1;
	fila.push(s);

	while(!fila.empty()) {
				
		u = fila.front();
		fila.pop();

		for(int i=1; i<=n; i++) {
			if(Gf[u][i] != 0 && !visitado[i]) {
				fila.push(i);
				pai[i] = u;
				visitado[i] = 1;
				if(i == t)
					return 1;		
			}
		}
	}	

	return 0;
}

int main() {

/* n: numero de vertices.
 * s: vertice de origem (fonte).
 * t: vertice de destino (sumidouro).
 * u: variavel representando um vertice qualquer.
 * v: variavel representando um vertice qualquer.
 * c: variavel representando a capacidade de um vertice qualquer.
 * cf: variavel indicando a menor capacidade residual em um caminho aumentante.
 * aux: variavel auxiliar.
 * fluxoMax: variavel indicando o fluxo maximo.
 */
	int n, s, t, u, v, c, cf, aux, fluxoMax;
	
	FILE *file;
	
	printf("Entre com n, s e t: ");
	scanf("%d %d %d", &n, &s, &t);

	memset(G, 0, sizeof(G));
	memset(Gf, 0, sizeof(Gf));
	memset(f, 0, sizeof(f));

	file = fopen("grafo.txt", "r");

	while(fscanf(file, "%d %d %d", &u, &v, &c) != EOF) {
		
		G[u][v] = c;

	}
	
	fclose(file);

	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++) 
			Gf[i][j] = G[i][j];
			
	while(buscaLarg(s, t, n)) {
		 
		// Seleciona a menor capacidade do caminho aumentante
		cf = Gf[pai[t]][t];
		aux = pai[t];
		while(aux != s) {
			cf = min(cf, Gf[pai[aux]][aux]);
			aux = pai[aux];	
		}
		
		// Atualiza o fluxo no caminho aumentante
		aux = t;
		while(aux != s) {

			f[pai[aux]][aux] += cf;
			f[aux][pai[aux]] -= cf;
			Gf[pai[aux]][aux] -= cf;
			Gf[aux][pai[aux]] += cf;
 			
			aux = pai[aux];	
		}				
	}	

	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++) {
			if(f[i][j])
			printf("fluxo %d -> %d: %d\n", i, j, f[i][j]);
	}

	fluxoMax = 0;
	for(int i=1; i<=n; i++) {
		fluxoMax += f[s][i];
	}
	
	printf("fluxo maximo: %d\n", fluxoMax);
		
	
	return 0;
}