clc, clear;
% c = [2, 3, 5, 7; 3, 5, 2, 8; 9, 5, 7, 8; 2, 2, 3, 9];
c = [12, 7, 9, 7, 9; 8, 9, 6, 6, 6; 7, 17, 12, 14, 12; 15, 14, 6, 6, 10; 4, 10, 7, 10, 6 ];
% c = [4,8,7,15,12;7,9,17,14,10;6,9,12,8,7;6,7,14,6,10;6,9,12,10,6]; % end up with endless loop
%function result = Hungarian(c)
size = length(c);
%pre-operation
line = min((c'));
line = repmat(line',1, size);
c = c - line;
column = min(c);
column = repmat(column, size, 1);
c = c - column;
%%
[axis_line, axis_column] = find(c == 0);
%C = [axis_line axis_column];
result = [axis_line, axis_column];
% [x, y] = meshgrid(temp_line, temp_column);
% result = [x(:), y(:)];
%get the left position
%decode the matrix to three dimension
%test = cell(size, 1);
z = zeros(size, size);
for i=1:size
x = find(result(:, 2) == i);
temp_size = length(x);
z(i, 1) = temp_size;
for j = 2:temp_size+1
test = result(x(j - 1),1);
z(i, j) = test;
end
end
%%
%mark
%flag = zeros(size, size);
%this loop is aimed to finding the answer for sereral iteration
tempresult = result;
while true
%mark
markedLine = zeros(1, size);
markedColumn = zeros(1, size);
[tempAnswer, all] = fit(z, 1, (1:size), zeros(1, size), []);
left = setdiff((1:size), tempAnswer);
if ~isempty(all)
disp('all rolution');
for i = 1:length(all(:, 1))
fprintf('the %dth solution', i);
disp(all(i, :));
end
break;
end
%mark the row
%flag(left, :) = 1;
markedLine(left) = 1;
%this loop is aimed to find the possible zero
%find all marked lines
temp_marked = find(markedLine == 1);
for i = 1:length(temp_marked)
tmp = temp_marked(i);
while true
%%
%step1
%find the line(subscript)
tmp = find(tempresult(:, 1) == tmp);
erase = tmp;
%find the colum
tmp = tempresult(tmp, 2);
%find weather it is terminate
if isempty(tmp)
break;
end
%mark the column
%flag(:,tmp) = 1;
markedColumn(tmp) = 1;
%erase the line
tempresult(erase, :) = [];
%%
%step2
%find the line(subscript)
tmp = find(tempresult(:, 2) == tmp);
erase = tmp;
%find the line
tmp = tempresult(tmp, 1);
%find weather it is terminate
if isempty(tmp)
break;
end
%mark the line
%flag(tmp, :) = 1;
markedLine(tmp) = 1;
%erase the column
tempresult(erase, :) = [];
end
end
%%
%find the minimal number
line = markedLine;
column = not(markedColumn);
flag = (line')*column;
subscript = find(flag == 1);
min = findMin(c, subscript);
%add and sub
templine = find(markedLine == 1);
tempcolumn = find(markedColumn == 1);
c(templine, :) = c(templine, :) - min;
c(:, tempcolumn) = c(:, tempcolumn) + min;
temp = find(c(subscript) == 0);
temp = subscript(temp);
%for i = 1:length(temp)
y = fix((temp-1)/5) + 1;
x = temp - (y-1)*5;
%end
tempresult = [result; [x, y]];
%check the answer
for i = 1:length(x)
z(x(i), 1) = z(x(i), 1) + 1;
z(x(i), z(x(i), 1)+1) = y(i);
end
end
result = all;
