% lap(W) - Linear Assignment Problem
%
% select one element from each row of W,
% using at most one element from each column,
% to minimize the sum of the selected elements.
%
function [R, cost] = lap(W)

global HUGE_VAL;

[M N] = size(W);

R = zeros(2,M);

cost = 0;

for i=1:M
  [t,j] = min(W(:));
  r = 1+mod(j-1,M);
  c = 1+floor((j-1)/M);
  cost = cost + W(r,c);
  R(:,i) = [r; c];
  W(r,:) = HUGE_VAL;
  W(:,c) = HUGE_VAL;
end
