A tarefa de encontrar o emparelhamento de peso máximo em um grafo bipartido pode ser abordada com o algoritmo KM. Alternativamente, problemas de fluxo de custo também podem ser aplicados. Recentemente, encontrei um problema que exigia a aplicação do algoritmo KM para resolver um sistema de inequações. Embora a conversão para um problema de fluxo de custo ainda fosse uma opção, a abordagem com limites superiores (top labels) se mostrou bastante útil durante o aprendizado. Este artigo explora a versão do algoritmo KM para emparelhamento completo de peso máximo. Emparelhamentos incompletos serão discutidos posteriormente. Seja \\(w(x, y)\\) o peso da aresta entre o vértice \\(x\\) no conjunto esquerdo e o vértice \\(y\\) no conjunto direito. Se não houver uma aresta, o peso é considerado \\(-\infty\\). Inicialmente, atribuímos limites superiores (top labels) aos vértices do conjunto esquerdo, denotdaos por \\(L(x)\\), e aos vértices do conjunto direito, denotados por \\(R(y)\\). Para cada \\(x\\), \\(L(x)\\) é inicializado com o peso máximo da aresta incidente a \\(x\\). Para cada \\(y\\), \\(R(y)\\) é inicializado com 0. Um subgrafo de igualdade é formado por arestas \\((x, y)\\) que satisfazem a condição \\(L(x) + R(y) = w(x, y)\\). Essencialmente, o algoritmo KM opera de maneira semelhante ao algoritmo de Hungria, buscando encontrar um emparelhamento perfeito para cada vértice. O fluxo do algoritmo é o seguinte: Iteramos sobre cada vértice \\(x\\) do conjunto esquerdo. Tentamos encontrar um parceiro de emparelhamento para \\(x\\) dentro do subgrafo de igualdade atual usando uma abordagem similar à do algoritmo de Hungria. Se um parceiro de emparelhamento não puder ser encontrado para \\(x\\), identificamos um valor mínimo \\(D\\). Em seguida, subtraímos \\(D\\) dos limites superiores dos vértices do conjunto esquerdo que foram visitados e adicionamos \\(D\\) aos limites superiores dos vértices do conjunto direito que foram visitados. Como \\(x\\) não encontrou um parceiro, o número de vértices visitados no conjunto esquerdo será maior em um do que no conjunto direito. Essa operação ajusta os limites superiores de forma a expandir o subgrafo de igualdade, mantendo a invariância do emparelhamento ou aumentando o número de arestas disponíveis para o emparelhamento. O valor \\(D\\) é determinado pelo mínimo valor de \\(L(x) + R(y) - w(x, y)\\) para todas as arestas \\((x, y)\\) que não pertencem ao subgrafo de igualdade, onde \\(x\\) foi visitado e \\(y\\) não foi. A implementação direta dessa abordagem pode levar a uma complexidade de \\(O(n^4)\\).
#include <iostream>
#include <vector>
#include <algorithm>
const int INF = 1e9;
struct Edge {
int to;
int weight;
};
int main() {
int num_left, num_right, num_edges;
std::cin >> num_left >> num_right >> num_edges;
std::vector<std::vector<int>> weights(num_left, std::vector<int>(num_right, 0));
for (int i = 0; i < num_edges; ++i) {
int u, v, w;
std::cin >> u >> v >> w;
--u; --v; // Ajuste para índices baseados em 0
weights[u][v] = std::max(weights[u][v], w); // Considera o maior peso se houver arestas múltiplas
}
std::vector<int> L(num_left, 0), R(num_right, 0);
for (int i = 0; i < num_left; ++i) {
for (int j = 0; j < num_right; ++j) {
L[i] = std::max(L[i], weights[i][j]);
}
}
std::vector<int> match_right(num_right, -1); // match_right[j] = i, se j está emparelhado com i
int max_dim = std::max(num_left, num_right);
for (int i = 0; i < num_left; ++i) {
std::vector<bool> visited_left(num_left, false);
std::vector<bool> visited_right(num_right, false);
std::vector<int> slack(num_right, INF);
std::vector<int> prev_match(num_right, -1); // Para reconstruir o caminho aumentante
int current_left_node = i;
match_right.assign(num_right, -1); // Reinicia o emparelhamento para cada iteração principal (simplificação para demonstração)
while (current_left_node != -1) {
visited_left[current_left_node] = true;
int delta = INF;
int next_right_node = -1;
for (int j = 0; j < num_right; ++j) {
if (!visited_right[j]) {
int current_slack = L[current_left_node] + R[j] - weights[current_left_node][j];
if (current_slack < slack[j]) {
slack[j] = current_slack;
prev_match[j] = current_left_node;
}
if (slack[j] < delta) {
delta = slack[j];
next_right_node = j;
}
}
}
for (int k = 0; k < num_left; ++k) {
if (visited_left[k]) {
L[k] -= delta;
}
}
for (int k = 0; k < num_right; ++k) {
if (visited_right[k]) {
R[k] += delta;
} else {
slack[k] -= delta;
}
}
visited_right[next_right_node] = true;
current_left_node = match_right[next_right_node];
match_right[next_right_node] = prev_match[next_right_node];
}
}
long long total_weight = 0;
for (int i = 0; i < num_left; ++i) {
total_weight += L[i];
}
for (int i = 0; i < num_right; ++i) {
total_weight += R[i];
}
std::cout << total_weight << std::endl;
std::vector<int> final_match(num_left, 0);
for(int j=0; j<num_right ajuste="" baseado="" em="" final_match="" for="" i="0;" if="" j="" num_left="" para="" return="" std::cout="" std::endl=""></num_right>
Uma implementação alternativa usando BFS também existe e, embora a lógica subjacente seja a mesma, a forma como os caminhos são explorados difere. ```cpp
#include #include #include #include
const int INF = 1e9;
int main() { int num_left, num_right, num_edges; std::cin >> num_left >> num_right >> num_edges;
std::vector<std::vector<int>> weights(num_left, std::vector<int>(num_right, 0));
for (int i = 0; i < num_edges; ++i) {
int u, v, w;
std::cin >> u >> v >> w;
--u; --v; // Ajuste para índices baseados em 0
weights[u][v] = std::max(weights[u][v], w);
}
std::vector<int> L(num_left, 0), R(num_right, 0);
for (int i = 0; i < num_left; ++i) {
for (int j = 0; j < num_right; ++j) {
L[i] = std::max(L[i], weights[i][j]);
}
}
std::vector<int> match_right(num_right, -1);
int max_dim = std::max(num_left, num_right);
for (int i = 0; i < num_left; ++i) {
std::queue<int> q;
q.push(i);
std::vector<int> parent_left(num_left, -1);
std::vector<int> parent_right(num_right, -1);
std::vector<int> slack(num_right, INF);
std::vector<bool> visited_left(num_left, false);
std::vector<bool> visited_right(num_right, false);
int current_left_root = i;
visited_left[current_left_root] = true;
while (true) {
int delta = INF;
int next_right_node = -1;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v = 0; v < num_right; ++v) {
if (!visited_right[v]) {
int current_diff = L[u] + R[v] - weights[u][v];
if (current_diff < slack[v]) {
slack[v] = current_diff;
parent_right[v] = u;
}
if (slack[v] < delta) {
delta = slack[v];
next_right_node = v;
}
}
}
}
for (int k = 0; k < num_left; ++k) {
if (visited_left[k]) L[k] -= delta;
}
for (int k = 0; k < num_right; ++k) {
if (visited_right[k]) R[k] += delta;
else slack[k] -= delta;
}
visited_right[next_right_node] = true;
int matched_left_node = match_right[next_right_node];
if (matched_left_node == -1) {
// Encontrou um caminho aumentante
int cur_v = next_right_node;
while (cur_v != -1) {
int cur_u = parent_right[cur_v];
int prev_v_match = match_right[cur_v]; // Salva o emparelhamento anterior de cur_v
match_right[cur_v] = cur_u;
if (cur_u != -1) { // Se cur_u não for o nó raiz dummy
// Encontre o nó direito emparelhado com cur_u para continuar a reconstrução
int next_cur_v = -1;
for(int node_r=0; node_r<num_right a="" ajuste="" ao="" baseado="" bfs="" break="" busca="" chegou="" continua="" cur_u="" cur_v="" de="" do="" else="" em="" esquerdo="" este="" final_match="" for="" i="0;" if="" in="" j="0;" l="" long="" loop="" n="" next_cur_v="node_r;" node_r="" num_left="" num_right="" para="" q.push="" r="" return="" sai="" std::cout="" std::endl="" std::vector="" total_weight="0;" true="" visited_left=""></num_right>
\*\*Questão 1: Emparelhamento Incompleto\*\* Para lidar com emparelhamentos incompletos, podemos modificar a representação do grafo. Se houver uma aresta enexistente entre \\\\(x\\\\) e \\\\(y\\\\), seu peso \\\\(w(x, y)\\\\) pode ser definido como 0. Se o número de vértices no conjunto esquerdo for maior do que no conjunto direito, vértices "fantasma" podem ser adicionados ao conjunto direito. Um emparelhamento de um vértice real com um vértice fantasma é equivalente a não emparelhar o vértice real. \*\*Questão 2: Restrições da Implementação BFS\*\* A implementação BFS geralmente pressupõe uma representação de matriz de adjacência, onde uma aresta é considerada existente entre todos os pares de vértices (mesmo que com peso zero se não houver uma aresta explícita). Isso ocorre devido à natureza da busca BFS, que pode não garantir a exploração da rota aumentante mais "ótima" em termos de ajuste de limites superiores, como poderia ocorrer com uma implementação DFS mais direta. Essa particularidade pode afetar o desempenho ou a correção em cenários onde arestas ausentes são cruciais. \*\*Questão 3: Resolução de Inequações\*\* Problemas envolvendo inequações, como \\\\(x\[i\] + y\[j\] \\ge w(i, j) \\ge 0\\\\), onde o objetivo é minimizar \\\\(\\sum x + \\sum y\\\\), podem ser transformados em um problema de emparelhamento de máximo peso. Ao aplicar o algoritmo KM diretamente, os limites superiores finais (top labels) obtidos para os vértices correspondem às variáveis de decisão \\\\(x\\\\) e \\\\(y\\\\) que minimizam a soma. Portanto, o somatório dos limites superiores no final do algoritmo KM fornece a solução mínima.