Resolver el problema de asignación usando min-cost-flow

El problema de asignación tiene dos enunciados equivalentes:

Dada una matriz cuadrada $A[1..N, 1..N]$ , hay que seleccionar $N$ elementos de modo que se seleccione exactamente un elemento en cada fila y columna, y la suma de los valores de esos elementos sea la más chica.
Hay $N$ pedidos y $N$ máquinas. Se conoce el costo de fabricación en cada máquina para cada pedido. En cada máquina se puede realizar solo un pedido. Hay que asignar todos los pedidos a las máquinas de modo que el costo total se minimice.

Acá consideramos la solución del problema basada en el algoritmo para encontrar el flujo de costo mínimo (min-cost-flow), resolviendo el problema de asignación en $\mathcal{O}(N^3)$ .

Descripción

Construyamos una red bipartita: hay una fuente $S$ , un sumidero $T$ , en la primera parte hay $N$ vértices (correspondientes a las filas de la matriz, o pedidos), en la segunda también hay $N$ vértices (correspondientes a las columnas de la matriz, o máquinas). Entre cada vértice $i$ del primer conjunto y cada vértice $j$ del segundo conjunto, dibujamos una arista con capacidad 1 y costo $A_{ij}$ . Desde la fuente $S$ dibujamos aristas a todos los vértices $i$ del primer conjunto con capacidad 1 y costo 0. Dibujamos una arista con capacidad 1 y costo 0 desde cada vértice del segundo conjunto $j$ hacia el sumidero $T$ .

Encontramos en la red resultante el flujo máximo de costo mínimo. Obviamente, el valor del flujo será $N$ . Además, para cada vértice $i$ del primer segmento hay exactamente un vértice $j$ del segundo segmento tal que el flujo $F_{ij}$ = 1. Finalmente, esta es una correspondencia uno a uno entre los vértices del primer segmento y los vértices de la segunda parte, que es la solución al problema (como el flujo encontrado tiene costo mínimo, la suma de los costos de las aristas seleccionadas será la más baja posible, que es el criterio de optimalidad).

La complejidad de esta solución del problema de asignación depende del algoritmo con el que se busca el flujo máximo de costo mínimo. La complejidad será $\mathcal{O}(N^3)$ usando Dijkstra o $\mathcal{O}(N^4)$ usando Bellman-Ford. Esto se debe a que el flujo es de tamaño $O(N)$ y cada iteración del algoritmo de Dijkstra se puede realizar en $O(N^2)$ , mientras que es $O(N^3)$ para Bellman-Ford.

Implementación

La implementación dada acá es larga; probablemente se pueda reducir de forma significativa. Usa el algoritmo SPFA para encontrar caminos más cortos.


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(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;
}