Ford-Fulkerson - Max Flow

Problemas para treinar: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=685

Explicação sobre o grafo residual: https://cs.stackexchange.com/questions/55041/residual-graph-in-maximum-flow

Abaixo seguem dois exemplos de código. No primeiro, utilizamos apenas uma matriz de adjacências para representar o grafo. Entretanto, nesse caso, o BFS é um pouco mais lento, pois todas as vezes ele faz o loop completo de acordo com a quantidade de colunas da matriz. Ou seja, ele percorre todas as colunas da matriz de adjacências para verificar se existe uma aresta.

Já a segunda implementação (que foi feita pela Romário) usa tanto uma lista quanto uma matriz de adjacência para representar o grafo. Assim, ele consegue o melhor dos dois mundos: o acesso direto a uma determinada aresta (graças a matriz) e percorrer somente as arestas que existirem a partir de um determinado nó (graças a lista).

Código 1 - Somente com matrizes de adjacências:

/*

Ford-Fulkerson

Maximum-Flow

Rodrigo Paes

*/

#include <bits/stdc++.h>

using namespace std;

#define MAX 6

/*

Retorna true caso consiga visitar o nó destino.

Constrói também o array parent.

*/

bool bfs(int residual_graph[MAX][MAX], int source, int target, int parent[])

    bool visited[MAX];

    memset(visited, false, sizeof(visited));

    queue<int> q;

    q.push(source);

    visited[source] = true;

    parent[source] = -1;

    while (!q.empty())

        int u = q.front(); q.pop();

for (int v=0; v < MAX; ++v) //perceba aqui que ele sempre vai até MAX. A implementação com listas evita isso.

            if (!visited[v] && residual_graph[u][v] > 0)

                q.push(v);

                parent[v] = u;

                visited[v] = true;

    return visited[target];

int ford_fulkerson(int graph[MAX][MAX], int source, int target)

    int u, v;

    int residual_graph[MAX][MAX];

    memcpy(residual_graph, graph, MAX*MAX*sizeof(int));

    int parent[MAX];

    int max_flow = 0;

/*

    o bfs faz a visitação da origem para o destino. Guardando o parent

*/

    while (bfs(residual_graph, source, target, parent))

/*

        Agora, de trás pra frente, verificamos qual é a aresta

        com menor capacidade residual. Ou seja, qual é o

        "gargalo" daquele caminho.

*/

        int path_flow = INT_MAX;

        for (v = target; v!=source; v=parent[v])

            u = parent[v];

            path_flow = min( path_flow, residual_graph[u][v] );

/*

        Uma vez descoberta o "gargalo", é preciso subtrair

        das capacidades de cada aresta do caminho, esse valor.

        O caminho é sempre: u->v

        Logo, temos que diminuir da aresta [u][v] e aumentar a aresta [v][u]

*/

        for (v = target; v!=source; v=parent[v])

            u = parent[v];

            residual_graph[u][v] -= path_flow;

            residual_graph[v][u] += path_flow;

            /* Vai chegar um momento, onde a aresta entre dois nós ficará zerada e, com isso,

            esse caminho não será mais utilizado

*/

        /* Um caminho já foi, adiciona ao fluxo máximo */

        max_flow += path_flow;

    return max_flow;

int main()

    // Let us create a graph shown in the above example

    int graph[MAX][MAX] = { {0, 16, 13, 0, 0, 0},

                        {0, 0, 10, 12, 0, 0},

                        {0, 4, 0, 0, 14, 0},

                        {0, 0, 9, 0, 0, 20},

                        {0, 0, 0, 7, 0, 4},

                        {0, 0, 0, 0, 0, 0}

};

    cout << "The maximum possible flow is " << ford_fulkerson(graph, 0, 5) << endl;

    return 0;

Código 2 - Implementação com matriz e lista:

#include <bits/stdc++.h> using namespace std; #define MAX 100 #define INF 1e9 int adjMatrix[MAX][MAX], max_flow, flow, src, sink; vector<int> parent, adjList[MAX]; void augment(int v, int minEdge) {     if(v == src) {flow = minEdge; return;}     else if(parent[v] != -1){         augment(parent[v], min(minEdge, adjMatrix[parent[v]][v]));         adjMatrix[parent[v]][v] -= flow;         adjMatrix[v][parent[v]] += flow;     } } int maxflow(){     max_flow = 0;     while(1){         flow = 0;         bitset<MAX> vis; vis[src] = true;         queue<int>q; q.push(src);         parent.assign(MAX, -1);         while(!q.empty()){             int u = q.front(); q.pop();             if(u == sink) break;             for(int j = 0; j<adjList[u].size(); j++){                 int v = adjList[u][j];                 if(adjMatrix[u][v] > 0 && !vis[v]){                     vis[v] = true, q.push(v), parent[v] = u;                 }             }         }         augment(sink, INF);         if(flow == 0)break;         max_flow+=flow;     }     return max_flow; }  int main(){     //ios_base::sync_with_stdio(0);     int n, m;     scanf("%d %d", &n, &m);     memset(adjMatrix, 0, sizeof adjMatrix);     for(int i = 0; i < m; i++){         int u, v, w;         scanf("%d %d %d", &u, &v, &w);         adjList[u].push_back(v);         adjList[v].push_back(u);         adjMatrix[u][v] = w; // fluxo entre esses dois vertices     }     src = 0; // inicio     sink = 1; // destino     printf("%d\n", maxflow()); }  /* entrada pra o grafo do video 5 7 0 2 100 0 3 50 2 3 50 2 4 50 2 1 50 3 4 100 4 1 125 */

Google Sites

Report abuse