matlab写一段最大流模型解决工作指派问题的代码，具体采用的是二分搜索算法

以下是使用二分搜索算法解决工作指派问题的 MATLAB 代码：

function [max_flow, assignment] = max_flow_assignment(cost_matrix)
% cost_matrix: n x n 的代价矩阵，n 为任务/工人的数量
% max_flow: 最大流量
% assignment: 长度为 n 的向量，表示任务分配给哪个工人，-1 表示未分配

n = size(cost_matrix, 1);
capacity_matrix = zeros(n+2, n+2); % 构造容量矩阵
for i = 1:n
    for j = 1:n
        capacity_matrix(i+1, j+1) = cost_matrix(i, j);
    end
end
for i = 1:n
    capacity_matrix(1, i+1) = 1; % 源点到任务的边的容量为 1
end
for i = 1:n
    capacity_matrix(i+1, n+2) = 1; % 任务到汇点的边的容量为 1
end

assignment = -1 * ones(1, n);
max_flow = 0;
while true
    [aug_path, aug_flow] = find_augmenting_path(capacity_matrix);
    if isempty(aug_path) % 找不到增广路，结束循环
        break
    end
    max_flow = max_flow + aug_flow;
    for i = 1:length(aug_path)-1 % 调整容量矩阵
        u = aug_path(i);
        v = aug_path(i+1);
        capacity_matrix(u, v) = capacity_matrix(u, v) - aug_flow;
        capacity_matrix(v, u) = capacity_matrix(v, u) + aug_flow;
    end
end

for i = 1:n % 生成任务分配结果
    for j = 1:n
        if capacity_matrix(i+1, j+1) == 0
            assignment(i) = j;
            break
        end
    end
end

end

function [aug_path, aug_flow] = find_augmenting_path(capacity_matrix)
% 使用二分搜索算法找到一条增广路
% 返回值：
% aug_path: 增广路
% aug_flow: 增广流量

n = size(capacity_matrix, 1) - 2;
left = 0;
right = 1e6;
while left < right
    mid = floor((left + right) / 2);
    [can_reach_t, path, flow] = dfs(capacity_matrix, 1, n+2, mid);
    if can_reach_t
        right = mid;
        aug_path = path;
        aug_flow = flow;
    else
        left = mid + 1;
    end
end

end

function [can_reach_t, path, flow] = dfs(capacity_matrix, s, t, limit)
% 深度优先搜索，返回值：
% can_reach_t: 是否可以到达汇点
% path: 从源点到汇点的路径
% flow: 该路径的流量

n = size(capacity_matrix, 1) - 2;
path = [];
flow = Inf * ones(n+2, 1);
visited = false(1, n+2);
visited(s) = true;
stack = s;
while ~isempty(stack)
    u = stack(end);
    stack(end) = [];
    if u == t % 到达汇点
        can_reach_t = true;
        break
    end
    for v = 1:n+2
        if ~visited(v) && capacity_matrix(u, v) > 0 && capacity_matrix(u, v) <= limit
            visited(v) = true;
            stack = [stack, v];
            path = [path, u];
            flow(v) = min(flow(u), capacity_matrix(u, v));
        end
    end
end

if ~can_reach_t
    return
end

path = [path, t];
flow = min(flow(t), limit);
end

注意：这里的二分搜索算法是对最小费用流问题进行二分搜索得到的，实际上可以直接使用 Ford-Fulkerson 算法求解工作指派问题。