Hungarian Algorithm

The assignment problem pairs n workers with n jobs, using every worker and job exactly once, while minimizing total cost. A compatibility-only maximum matching ignores costs; Hungarian optimizes them in O(n³) for a dense square matrix. Negative costs are permitted. This lesson implements the potential-and-slack form, which grows an alternating search tree and changes dual potentials until another useful edge becomes tight.

Prerequisites: Bipartite Matching; alternating paths and basic inequalities. Difficulty: Advanced. Review: Bipartite Matching.

Build the idea

1. 1. Think in terms of lower bounds

   For each worker i maintain potential u[i], and for each job j potential v[j]. A feasible dual satisfies u[i]+v[j] ≤ cost[i][j]. Summing these inequalities over any perfect assignment bounds its cost below by sum(u)+sum(v). An edge is tight when equality holds. A perfect matching consisting of tight edges achieves this lower bound and is therefore optimal; this is the certificate behind the algorithm, not a greedy cheapest-edge rule.

2. 2. Add one worker to the matching

   owner[j] stores the worker assigned to column j. Column 0 is a dummy root holding the new worker, not a real job. Mark reached columns in used[]. From each reached column, inspect its owner’s edges to unreached columns. slack[j] records the best reduced cost cost[i][j]−u[i]−v[j] from the current alternating tree; previous[j] remembers which column supplied that candidate.

3. 3. Update potentials by the smallest slack

   Choose delta as the minimum slack to any unused column. Increase u for reached workers and decrease v for reached real columns; subtract delta from unreached slacks. Existing tight matched/tree edges stay tight and at least one new edge becomes tight. With negative input costs the first delta for a newly introduced worker can be negative; it establishes feasibility for that worker. Already processed workers keep feasible reduced costs. Follow the newly reached column; if occupied, add its owner to the search.

4. 4. Finish and reconstruct

   When a free real column is reached, previous[] describes an alternating path back to dummy column 0. Reassign owner[] along that path, increasing matching size by one. Repeat for every worker. The code prints both the minimum total and assigned[i], the job chosen for worker i. It directly sums selected original costs, avoiding dependence on dummy-potential conventions for output.

5. 5. Work the small matrix

   For costs [[4,1,3],[2,0,5],[3,2,2]], taking worker 1’s cheapest job 2 would compete with worker 2’s cheapest job 2. Alternating reassignment chooses jobs [2,1,3]: costs 1+2+2=5. A lower-bound certificate is u=[3,2,2] and v=[0,−2,0]; all selected edges are tight and the potential sum is 5. Other potential values may also certify the same optimum.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<limits>
using namespace std;
using ll=long long;
int main(){
    int n;
    if(!(cin>>n)){
        return 0;
    }
    vector<vector<ll>>cost(n+1,vector<ll>(n+1));
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            cin>>cost[i][j];
        }
    }
    const ll INF=numeric_limits<ll>::max()/4;
    vector<ll>u(n+1),v(n+1);
    vector<int>owner(n+1),previous(n+1);
    for(int row=1;row<=n;++row){
        owner[0]=row;
        int column=0;
        vector<ll>slack(n+1,INF);
        vector<char>used(n+1,false);
        do{
            used[column]=true;
            int currentRow=owner[column],nextColumn=0;
            ll delta=INF;
            for(int j=1;j<=n;++j){
                if(!used[j]){
                    ll reduced=cost[currentRow][j]-u[currentRow]-v[j];
                    if(reduced<slack[j]){
                        slack[j]=reduced;
                        previous[j]=column;
                    }
                    if(slack[j]<delta){
                        delta=slack[j];
                        nextColumn=j;
                    }
                }
            }
            // Make another edge tight while preserving earlier tight tree edges.
            for(int j=0;j<=n;++j){
                if(used[j]){
                    u[owner[j]]+=delta;
                    v[j]-=delta;
                }
                else{
                    slack[j]-=delta;
                }
            }
            column=nextColumn;
        }
        while(owner[column]!=0);
        // A free column ends an alternating path; flip it backwards.
        do{
            int p=previous[column];
            owner[column]=owner[p];
            column=p;
        }
        while(column);
    }
    vector<int>assigned(n+1);
    ll answer=0;
    for(int j=1;j<=n;++j){
        assigned[owner[j]]=j;
        answer+=cost[owner[j]][j];
    }
    cout<<answer<<'\n';
    for(int i=1;i<=n;++i){
        cout<<assigned[i]<<(i==n?'\n':' ');
    }
}

Complexity analysis

O(n³) time: insert n workers, reach at most n columns for each, and scan n candidate columns at each extension. O(n²) memory stores the dense cost matrix; potentials, slacks, ownership and predecessor arrays use O(n). Input costs may be negative; with n≤500 and |cost|≤10^9 all intermediate totals safely fit long long.

Example input and output

Read n (1≤n≤500), followed by an n×n complete integer cost matrix with |cost|≤10^9. Print minimum cost, then the selected job for workers 1..n. Ties may have several valid optimal assignments.

Input

3
4 1 3
2 0 5
3 2 2

Output

5
2 1 3

Worker 1 takes job 2 for 1, worker 2 takes job 1 for 2, and worker 3 takes job 3 for 2. Total is 5.

Practical applications

Use Hungarian for dense one-to-one minimum-cost perfect assignment. If there are more jobs than workers, a rectangular variant is possible; this lesson deliberately teaches the square case. For capacities, partial assignment or network constraints, use minimum-cost flow. For unweighted cardinality alone, Kuhn or Hopcroft–Karp is simpler.

Check your understanding

What certifies that a tight perfect matching is minimum-cost?

Put it into practice

Test a matrix with negative costs and compare against all permutations for n≤8.