Definição de Fluxo em Redes
Uma rede é um grafo direcionado especial com um fonte \(s\) e um sumidouro \(t\), onde cada aresta possui uma capacidade. Um fluxo na rede é uma atribuição de valores às arestas (chamados fluxos) que respeita as restrições de capacidade e a conservação do fluxo em todos os vértices exceto \(s\) e \(t\). Matematicamente, para todo vértice \(u\) (exceto \(s\) e \(t\)): a soma dos fluxos nas arestas que entram em \(u\) é igual à soma dos fluxos nas arestas que saem de \(u\). Em alguns contextos, o "fluxo" refere-se ao valor total que chega ao sumidouro \(t\).
Fluxo Máximo
Dada uma rede com capacidades nas arestas, o problema do fluxo máximo consiste em encontrar a maior quantidade de fluxo possível de \(s\) a \(t\).
Conceito
A ideia central do algoritmo de fluxo máximo é utilizar arestas reversas para permitir "desfazer" decisões anteriores. Inicialmente, para cada aresta, cria-se uma aresta reversa com capacidade zero. O processo consiste em repetidamente encontrar um caminho aumentante na rede residual (a rede que representa a capacidade restante) de \(s\) a \(t\). Para cada caminho aumentante, determina-se a capacidade mínima \(w\) ao longo do caminho. O fluxo total é aumentado em \(w\), as capacidades das arestas diretas no caminho são reduzidas em \(w\), e as capacidades das arestas reversas correspondentes são aumentadas em \(w\). Isso permite "desfazer" fluxo em iterações posteriores, se necessário.
O algoritmo termina quando não existem mais caminhos aumentantes na rede residual, e nesse ponto o fluxo atual é máximo.
Algoritmo de Ford-Fulkerson (FF)
O algoritmo Ford-Fulkerson implementa a ideia acima utilizando busca em profundidade (DFS) para encontrar caminhos aumentantes. No entanto, a DFS pode ser ineficiente em certas topologias, como grafos com capacidades elevadas em arestas alternadas, levando a muitas iterações.
Algoritmo de Edmonds-Karp (EK)
Uma melhoria simples ao Ford-Fulkerson é utilizar busca em largura (BFS) para encontrar sempre o caminho aumentante mais curto (em número de arestas). Essa versão é conhecida como algoritmo de Edmonds-Karp. A complexidade de tempo é \(O(nm^2)\), onde \(n\) é o número de vértices e \(m\) é o número de arestas. Na prática, especialmente em grafos esparsos e dados aleatórios, o desempenho é muito bom.
Exemplo de imlpementação em C++ (variáveis e estrutura modificadas para clareza):
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN = 205;
const long long INF = 0x3f3f3f3f3f3f3f3f;
int numVertices, numEdges;
long long capacidade[MAXN][MAXN];
long long fluxoAtual[MAXN];
int verticeAnterior[MAXN];
long long bfsFluxoMaximo(int fonte, int sumidouro) {
memset(verticeAnterior, -1, sizeof(verticeAnterior));
memset(fluxoAtual, 0, sizeof(fluxoAtual));
fluxoAtual[fonte] = INF;
verticeAnterior[fonte] = 0;
queue<int> fila;
fila.push(fonte);
while (!fila.empty()) {
int u = fila.front();
fila.pop();
if (u == sumidouro) return fluxoAtual[sumidouro];
for (int v = 1; v <= numVertices; v++) {
if (verticeAnterior[v] == -1 && capacidade[u][v] > 0) {
verticeAnterior[v] = u;
fluxoAtual[v] = min(fluxoAtual[u], capacidade[u][v]);
fila.push(v);
}
}
}
return 0;
}
long long calcularFluxoMaximo(int fonte, int sumidouro) {
long long fluxoTotal = 0;
while (true) {
long long aumento = bfsFluxoMaximo(fonte, sumidouro);
if (aumento == 0) break;
int v = sumidouro;
while (v != fonte) {
int u = verticeAnterior[v];
capacidade[u][v] -= aumento;
capacidade[v][u] += aumento;
v = u;
}
fluxoTotal += aumento;
}
return fluxoTotal;
}
int main() {
int fonte, sumidouro;
cin >> numVertices >> numEdges >> fonte >> sumidouro;
memset(capacidade, 0, sizeof(capacidade));
for (int i = 0; i < numEdges; i++) {
int u, v, c;
cin >> u >> v >> c;
capacidade[u][v] += c;
}
cout << calcularFluxoMaximo(fonte, sumidouro) << endl;
return 0;
}
Algoritmo de Dinic
O algoritmo de Dinic otimiza o processo ao construir uma rede de nível (usando BFS) e então realizar múltiplas buscas em profundidade (DFS) nessa rede para encontrar vários caminhos aumentantes de uma vez. Isso reduz significativamente o número de vezes que a BFS é executada.
Principais características:
- A BFS atribui um nível (distância mínima a partir da fonte) a cada vértice.
- A DFS só segue arestas de nível \(k\) para nível \(k+1\).
- Otimizações como a "otimização de arco corrente" são frequentemente aplicadas.
A complexidade de tempo é \(O(n^2 m)\) no pior caso, mas com otimizações e em muitos cenários práticos é mais rápido.
Exemplo de implementação (com modificações):
#include <iostream>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;
const int MAXN = 205;
const long long INF = 0x3f3f3f3f3f3f3f3f;
struct Aresta {
int para, capacidade, proximo;
};
int numVertices, numEdges, fonte, sumidouro;
vector<Aresta> arestas[MAXN];
int profundidade[MAXN];
int ponteiro[MAXN];
void adicionarAresta(int de, int para, int cap) {
arestas[de].push_back({para, cap, (int)arestas[para].size()});
arestas[para].push_back({de, 0, (int)arestas[de].size() - 1});
}
bool bfsDinic() {
memset(profundidade, -1, sizeof(profundidade));
profundidade[fonte] = 0;
queue<int> fila;
fila.push(fonte);
while (!fila.empty()) {
int u = fila.front();
fila.pop();
for (const auto& aresta : arestas[u]) {
if (profundidade[aresta.para] == -1 && aresta.capacidade > 0) {
profundidade[aresta.para] = profundidade[u] + 1;
fila.push(aresta.para);
}
}
}
return profundidade[sumidouro] != -1;
}
long long dfsDinic(int u, long long fluxoMinimo) {
if (u == sumidouro) return fluxoMinimo;
for (int& i = ponteiro[u]; i < arestas[u].size(); i++) {
Aresta& aresta = arestas[u][i];
if (profundidade[aresta.para] == profundidade[u] + 1 && aresta.capacidade > 0) {
long long fluxoEnviado = dfsDinic(aresta.para, min(fluxoMinimo, (long long)aresta.capacidade));
if (fluxoEnviado > 0) {
aresta.capacidade -= fluxoEnviado;
arestas[aresta.para][aresta.proximo].capacidade += fluxoEnviado;
return fluxoEnviado;
}
}
}
return 0;
}
long long dinicFluxoMaximo() {
long long fluxoTotal = 0;
while (bfsDinic()) {
memset(ponteiro, 0, sizeof(ponteiro));
long long fluxo;
while ((fluxo = dfsDinic(fonte, INF)) > 0) {
fluxoTotal += fluxo;
}
}
return fluxoTotal;
}
int main() {
cin >> numVertices >> numEdges >> fonte >> sumidouro;
for (int i = 0; i < numEdges; i++) {
int u, v, c;
cin >> u >> v >> c;
adicionarAresta(u, v, c);
}
cout << dinicFluxoMaximo() << endl;
return 0;
}
Corte Mínimo
Um corte em uma rede é um conjunto de arestas cuja remoção desconecta a fonte do sumidouro. O corte mínimo é o corte cuja soma das capacidades das arestas removidas é mínima. Um resultado fundamental é que o valor do fluxo máximo é igual à capacidade do corte mínimo.
Problemas Clássicos Baseados em Corte
Problema do Grafo de Fechamento de Peso Máximo
Dado um grafo direcionado com pesos (positivos ou negativos) nos vértices e arestas com capacidade infinita representando dependências, deseja-se encontrar um subconjunto de vértices que maximize a soma dos pesos, sujeito à restrição de que se um vértice for escolhido, todos os seus dependentes também devem ser escolhidos.
A construção da rede para esse problema é clássica:
- Cria-se uma fonte \(s\) e um sumidouro \(t\).
- Para cada vértice \(i\) com peso positivo \(w_i\), adiciona-se uma aresta de \(s\) para \(i\) com capacidade \(w_i\).
- Para cada vértice \(i\) com peso negativo \(w_i\), adiciona-se uma aresta de \(i\) para \(t\) com capacidade \(-w_i\).
- Para cada dependência \((a, b)\), adiciona-se uma aresta de \(a\) para \(b\) com capacidade infinita.
A resposta é a soma dos pesos positivos menos o valor do fluxo máximo (ou corte mínimo) na rede construída.
Exemplos de aplicação incluem problemas como "Fluxo Máximo com Restrições" e "Problema do Plano Espacial".
Fluxo de Custo Mínimo (MCMF)
No problema do fluxo de custo mínimo, cada aresta possui, além de uma capacidade, um custo por unidade de fluxo. O objetivo é encontrar o fluxo máximo que minimiza o custo total.
Uma abordagem comum é o algoritmo de Successive Shortest Path, que utiliza o algoritmo de Dijkstra (ou SPFA) para encontrar, a cada iteração, o caminho aumentante de custo mínimo na rede residual.
Exemplo de implementação (usando SPFA):
#include <iostream>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;
const int MAXN = 5005;
const long long INF = 0x3f3f3f3f;
struct Aresta {
int para, capacidade, custo, proximo;
};
int numVertices, numEdges, fonte, sumidouro;
vector<Aresta> arestas[MAXN];
long long distancia[MAXN];
int verticeAnt[MAXN];
int arestaAnt[MAXN];
bool emFila[MAXN];
long long fluxoAtual[MAXN];
void adicionarAresta(int de, int para, int cap, int custo) {
arestas[de].push_back({para, cap, custo, (int)arestas[para].size()});
arestas[para].push_back({de, 0, -custo, (int)arestas[de].size() - 1});
}
bool spfa() {
memset(distancia, 0x3f, sizeof(distancia));
memset(fluxoAtual, 0, sizeof(fluxoAtual));
memset(emFila, false, sizeof(emFila));
distancia[fonte] = 0;
fluxoAtual[fonte] = INF;
emFila[fonte] = true;
queue<int> fila;
fila.push(fonte);
while (!fila.empty()) {
int u = fila.front();
fila.pop();
emFila[u] = false;
for (int i = 0; i < arestas[u].size(); i++) {
Aresta& aresta = arestas[u][i];
if (aresta.capacidade > 0 && distancia[u] + aresta.custo < distancia[aresta.para]) {
distancia[aresta.para] = distancia[u] + aresta.custo;
verticeAnt[aresta.para] = u;
arestaAnt[aresta.para] = i;
fluxoAtual[aresta.para] = min(fluxoAtual[u], aresta.capacidade);
if (!emFila[aresta.para]) {
emFila[aresta.para] = true;
fila.push(aresta.para);
}
}
}
}
return distancia[sumidouro] != INF;
}
pair<long long, long long> fluxoCustoMinimo() {
long long fluxoTotal = 0, custoTotal = 0;
while (spfa()) {
long long aumento = fluxoAtual[sumidouro];
fluxoTotal += aumento;
custoTotal += aumento * distancia[sumidouro];
int v = sumidouro;
while (v != fonte) {
int u = verticeAnt[v];
int idx = arestaAnt[v];
arestas[u][idx].capacidade -= aumento;
arestas[v][arestas[u][idx].proximo].capacidade += aumento;
v = u;
}
}
return {fluxoTotal, custoTotal};
}
int main() {
cin >> numVertices >> numEdges >> fonte >> sumidouro;
for (int i = 0; i < numEdges; i++) {
int u, v, cap, custo;
cin >> u >> v >> cap >> custo;
adicionarAresta(u, v, cap, custo);
}
auto resultado = fluxoCustoMinimo();
cout << resultado.first << " " << resultado.second << endl;
return 0;
}
Problemas Clássicos de Fluxo de Custo Mínimo
Muitos problemas de otimização podem ser modelados como fluxo de custo mínimo, como:
- Problema de Escalonamento de Tarefas (ex.: "Reparando Carros" e "Festival Gastronômico").
- Porblema de Emparceiramento de Peso Máximo em Grafos Bipartidos.
- Problema de Designação com restrições.
A modelagem frequentemente envolve criar nós para representar eventos ou escolhas, e arestas com custos que refletem a contribuição para o objetivo.
Árvore de Corte Mínimo (Gomory-Hu)
Para responder consultas de corte mínimo entre quaisquer dois vértices em um grafo não direcionado, pode-se construir uma árvore de Gomory-Hu. Essa árvore compacta a informação de todos os cortes mínimos pairwise, e o corte mínimo entre dois vértices é igual ao peso mínimo na caminho único entre eles na árvore.
A construção utiliza divisão e conquista: escolhe-se dois vértices, calcula-se o corte mínimo entre eles na rede original, particiona os vértices de acordo com o lado do corte, e repete recursivamente.