Bipartite matching : Hungarian algorithm - YessineJallouli/Competitive-Programming GitHub Wiki

#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#define ll long long
using namespace std;
ll cost[405][405];

// the algorithm uses 0-based indexing for the graphs
// n and m are the numbers of nodes from the first and second set respectively
ll hungarian(int n ,int m) {
    ll INF = LLONG_MAX;
    vector<ll> u(n + 1), v(m + 1), dist(m + 1);
    vector<int> p(m + 1), way(m + 1), used(m + 1);
    for (int i = 1; i <= n; ++i) {
        p[0] = i;
        int j0 = 0;
        fill(dist.begin(), dist.end(), INF);
        do {
            used[j0] = i;
            int i0 = p[j0], j1 = -1;
            ll delta = INF;
            for (int j = 1; j <= m; ++j) if (used[j] != i) {
                    ll cur = cost[i0 - 1][j - 1] - u[i0] - v[j];
                    if (cur < dist[j]) dist[j] = cur, way[j] = j0;
                    if (dist[j] < delta) delta = dist[j], j1 = j;
            }
            for (int j = 0; j <= m; j++) {
                if (used[j] == i) u[p[j]] += delta, v[j] -= delta;
                else dist[j] -= delta;
            }
            j0 = j1;
        } while (p[j0] != 0);
        for (int j1; j0; j0 = j1)
            p[j0] = p[j1 = way[j0]];
    }
    return -v[0];
}

int main() {
    ios_base::sync_with_stdio(false);
}
⚠️ **GitHub.com Fallback** ⚠️