Solução usando o fluxo de custo-mínimo

O problema possui duas instruções equivalentes:

Aqui, consideraremos a solução do problema com base no algoritmo para encontrar o fluxo de custo mínimo, resolvendo o problema em $\mathcal{O}(N^5)$.

Descrição

Vamos construir uma rede bipartida: existe uma fonte $S$, um coletor $T$, na primeira parte existem $N$ vértices (correspondentes as linhas da matriz ou pedidos), na segunda também existem $N$ vértices (correspondentes às colunas da matriz ou máquinas). Entre cada vértice $i$ do primeiro conjunto e cada vértice $j$ do segundo conjunto, traçamos uma aresta com a largura 1 e custo $A_{ij}$. Da fonte $S$ traçamos arestas para todos os vértices $i$ do primeiro conjunto com largura 1 e custo 0. Traçamos uma aresta com largura 1 e custo 0 de cada vértice do segundo conjunto $j$ para o coletor $T$.

Encontramos na rede resultante o fluxo máximo do custo mínimo. O valor do fluxo será $N$. Em seguida, para cada vértice $i$ do primeiro segmento, há exatamente um vértice $j$ do segundo segmento, de modo que o fluxo $F_{ij}$ = 1. Finalmente, essa é uma correspondência individual entre os vértices do primeiro segmento e os vértices da segunda parte, que é a solução para o problema (como o fluxo encontrado tem um custo mínimo, a soma dos custos das arestas selecionadas será a mais baixa possível, que é o critério de otimização).

A complexidade dessa solução do problema depende do algoritmo pelo qual a busca pelo fluxo máximo do custo mínimo é realizada. A complexidade será $\mathcal{O}(N^5)$ usando Dijkstra ou $\mathcal{O}(N^6)$ usando Bellman-Ford.

Implementação

A implementação fornecida aqui é longa, provavelmente pode ser significativamente reduzida. Ela usa o algoritmo SPFA para encontrar os caminhos mais curtos.

const int INF = 1000 * 1000 * 1000;

vector<int> assignment(vector<vector<int>> a) {
    int n = a.size();
    int m = n * 2 + 2;
    vector<vector<int>> f(m, vector<int>(m));
    int s = m - 2, t = m - 1;
    int cost = 0;
    while (true) {
        vector<int> dist(m, INF);
        vector<int> p(m);
        vector<bool> inq(m, false);
        queue<int> q;
        dist[s] = 0;
        p[s] = -1;
        q.push_back(s);
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            inq[v] = false;
            if (v == s) {
                for (int i = 0; i < n; ++i) {
                    if (f[s][i] == 0) {
                        dist[i] = 0;
                        p[i] = s;
                        inq[i] = true;
                        q.push(i);
                    }
                }
            } else {
                if (v < n) {
                    for (int j = n; j < n + n; ++j) {
                        if (f[v][j] < 1 && dist[j] > dist[v] + a[v][j - n]) {
                            dist[j] = dist[v] + a[v][j - n];
                            p[j] = v;
                            if (!inq[j]) {
                                q.push(j);
                                inq[j] = true;
                            }
                        }
                    }
                } else {
                    for (int j = 0; j < n; ++j) {
                        if (f[v][j] < 0 && dist[j] > dist[v] - a[j][v - n]) {
                            dist[j] = dist[v] - a[j][v - n];
                            p[j] = v;
                            if (!inq[j]) {
                                q.push(j);
                                inq[j] = true;
                            }
                        }
                    }
                }
            }
        }

        int curcost = INF;
        for (int i = n; i < n + n; ++i) {
            if (f[i][t] == 0 && dist[i] < curcost) {
                curcost = dist[i];
                p[t] = i;
            }
        }
        if (curcost == INF)
            break;
        cost += curcost;
        for (int cur = t; cur != -1; cur = p[cur]) {
            int prev = p[cur];
            if (prev != -1)
                f[cur][prev] = -(f[prev][cur] = 1);
        }
    }

    vector<int> answer(n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (f[i][j + n] == 1)
                answer[i] = j;
        }
    }
    return answer;
}