Skip to content

@dennermiranda /gist:3800091
Created

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Edmonds Karp
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.