Problem 17: Hungarian Algorithm for Assignment Problem
Problem Statement: Given a cost matrix for n workers and n tasks, compute the minimum cost assignment using the Hungarian algorithm.
Input
First line contains n. The following n lines each contain n integers representing the cost matrix.
Output
Print the minimum cost assignment.
Examples
Input:
3
9 2 7
6 4 3
5 8 1
Output:
10
Solution Explanation
Method 1: Use the Hungarian algorithm by iteratively adjusting labels and finding augmenting paths to minimize the overall assignment cost. Method 2: Utilize a primal-dual approach that maintains dual variables for rows and columns and adjusts them as you build the matching.
Solution in C++
#include
#include
#include
using namespace std;
int main(){
int n; cin >> n;
vector> cost(n, vector(n));
for(int i=0; i> cost[i][j];
}
vector u(n+1), v(n+1), p(n+1), way(n+1);
for(int i=1;i<=n;i++){
p[0] = i;
int j0 = 0;
vector minv(n+1, 1e9);
vector used(n+1, false);
do{
used[j0] = true;
int i0 = p[j0], delta = 1e9, j1 = 0;
for (int j=1;j<=n;j++){
if(!used[j]){
int cur = cost[i0-1][j-1] - u[i0] - v[j];
if(cur < minv[j]) { minv[j] = cur; way[j] = j0; }
if(minv[j] < delta) { delta = minv[j]; j1 = j; }
}
}
for(int j=0;j<=n;j++){
if(used[j]) { u[p[j]] += delta; v[j] -= delta; } else { minv[j] -= delta; }
}
j0 = j1;
} while(p[j0]!=0);
do{
int j1 = way[j0];
p[j0] = p[j1];
j0 = j1;
} while(j0);
}
cout << -v[0];
return 0;
}