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).
/*
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;
}
#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 */