Created

Embed URL

HTTPS clone URL

SSH clone URL

You can clone with HTTPS or SSH.

Download Gist

Edmonds Karp

View gist:3800091
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137
#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.