Grafos: Fluxos em Redes e Emparelhamento Bipartido

O Paradigma de Capacidades Escassas

Imagine tubulações de água fluindo de uma Fonte (Source S) até um Sumidouro (Sink T). Cada cano possui uma espessura física limitando quantos litros de água podem passar por segundo (Capacity). Acionar todos os canos no talo fará com que os pontos de cruzamento no meio do caminho esguichem água pra fora se estiver recebendo mais litros do que a via de saída aguenta escoar.

O teorema central das Redes Neurais Hidráulicas: Max Flow Min Cut diz que “O fluxo colossal máximo que você consegue despachar da Fonte pro Sumidouro é exatamente governado pela largura do pior cano no meio do escoamento (Gargalo)”.

A solução universal acadêmica para achar essa resposta é rodar os clássicos Ford-Fulkerson ou seu filho aprimorado via BFS: Edmonds-Karp (\(O(V \cdot E^2)\)).

Matching Bipartido (Um caso peculiar de fluxo)

Existe um subtipo ultra amigável e corriqueiro nos vestibulares onde as tubulações só aceitam trafegar 1 litro (Capacidade Unitária) e as coisas se dividem em dois grupos perfeitos que precisam “dar Match” (Voluntários de um lado, Camisetas do outro; Uber de um lado, Passageiro do outro).

Emparelhamento Bipartido Recursivo: Algoritmo Augmenting Path

Como os limites estouram num máximo de 1, não precisamos levantar matrizes residuais gigantescas do Edmonds-Karp. Podemos resolver tudo na elegância de uma busca DFS por “Caminho Aumentante”.

#include <iostream>
#include <vector>
#include <string.h>
#include <cassert>

using namespace std;

// No nosso contexto Bipartido: Nro de Pessoas (Lado Esquerdo)
int leftN = 3; 

// Vector de ligaçoes da Pessoa para <Tamanhos (Lado Direito)>
vector<vector<int>> adj;

// matchRight[i] guarda o ID da Pessoa q ficou emparelhada com o Tamanho i
vector<int> matchRight;
vector<bool> visitado; // pra não ficar caçando a mesma pessoa sem parar

// Tenta achar um match exclusivo para a pessoa `u`
bool dfsAugmentar(int u) {
    for (int v : adj[u]) {
        // Se a camisa 'v' não estava travada nessa rodada temporal de renegociação
        if (!visitado[v]) {
            visitado[v] = true;
            
            // Se a camisa 'v' ta LIVRE (-1)
            // OU: A camisa ta ocupada, mas o cara que tava com ela CONSEGUE pegar outra! (Recursão mágica de reconiliação)
            if (matchRight[v] < 0 || dfsAugmentar(matchRight[v])) {
                matchRight[v] = u; // Trava a posse com u
                return true;
            }
        }
    }
    return false; // Acabou as opções que davam cadeia sucessiva 
}

int calcularMaxBipartiteMatching(int rightN) {
    matchRight.assign(rightN, -1);
    
    int maxFlow = 0;
    // Pede pra todo esquerdista tentar rolar seu casório com a direita
    for (int u = 0; u < leftN; u++) {
        visitado.assign(rightN, false); 
        if (dfsAugmentar(u)) {
            maxFlow++;
        }
    }
    return maxFlow;
}


void executando_testes() {
    leftN = 3;  // P1(0), P2(1), P3(2)
    int rightN = 3; // M(0), G(1), P(2)
    
    adj.assign(leftN, vector<int>());
    
    // Modelando via Mermaid superior:
    adj[0].push_back(0); // P1(0) aceita M(0)
    adj[0].push_back(1); // P1(0) aceita G(1)
    
    adj[1].push_back(0); // P2(1) aceita M(0)
    adj[1].push_back(2); // P2(1) aceita P(2)
    
    adj[2].push_back(1); // P3(2) aceita G(1)

    // O Fluxo Máximo do Matching deve logicamente conseguir 3 contatos perfeitos:
    assert(calcularMaxBipartiteMatching(rightN) == 3);

    cout << "[✅] Testes DFS de Bipartite Matching validados. Todos conseguiram a camisa!\n";
}

int main() {
    executando_testes();
    return 0;
}

A grande vantagem visual do Emparelhamento é a facilidade natural das chamadas recursivas, onde um elemento X aborda a camisa Y, vê que K já estava lá, mas magicamente convoca K a entregar a camisa Y e se contentar com uma livre paralela. Isso flui como mágica em \(O(V \cdot E)\).

Exercício Guiado (Alocação Limitada Otimizada)

Problema Clássico: Beecrowd 1362 - Minhas Camisetas Me Servem

Esse problema estampa a narrativa que disparamos! No evento, vários voluntários só aceitam estritamente 2 tamanhos (M ou G). Só que temos E camisas totais distribuídas de forma igual em 6 fardos tamanhos padronizados (S, M, L…).

Raciocínio Adaptado: Você poderia multiplicar os nós direitos para espelhar as quantidades múltiplas na vitrine (Se temos 4 camisas G, a “direita” no Bipartite teria os nós G1, G2, G3, G4 enfileirados). Liga-se a pessoa i aos N nós daquele escopo. Rodou o calcularMaxBipartiteMatching(), a resposta deu igual à numeração exata de Voluntários de entrada? Imprima YES!

Grafos: Fluxos em Redes e Emparelhamento Bipartido

O Paradigma de Capacidades Escassas

Matching Bipartido (Um caso peculiar de fluxo)

Emparelhamento Bipartido Recursivo: Algoritmo Augmenting Path

Exercício Guiado (Alocação Limitada Otimizada)

Listagem de Exercícios Complementares (Matching)