求解MCMF问题 matlab代码

以下是一个简单的MCMF问题的Matlab代码，使用了Ford-Fulkerson算法：

function [flow, cost] = MCMF(C, s, t)
% C: 图的邻接矩阵，C(i,j)表示从i到j的边的容量和费用，如果没有边则为0
% s: 源点
% t: 汇点
% flow: 最大流
% cost: 最小费用

n = size(C, 1); % 图的大小

F = zeros(n); % 流量矩阵
P = zeros(n); % 增广路矩阵

% Ford-Fulkerson算法
while true
% 寻找增广路
[P, f] = find_augmenting_path(C, F, s, t);
if f == 0 % 如果没有增广路，则结束
break;
end
% 更新流量矩阵
F = F + P * f;
end

% 计算最大流和最小费用
flow = sum(F(s, :));
cost = sum(sum(F .* C));

function [P, f] = find_augmenting_path(C, F, s, t)
% C: 图的邻接矩阵
% F: 流量矩阵
% s: 源点
% t: 汇点
% P: 增广路矩阵
% f: 增广路的流量

n = size(C, 1); % 图的大小

% 初始化增广路矩阵
P = zeros(n);
visited = false(n, 1);

% 使用DFS寻找增广路
[f, visited] = DFS(C, F, s, t, visited, inf);
if f == 0 % 如果没有增广路，则返回
return;
end

% 更新增广路矩阵
i = t;
while i ~= s
j = find(visited & (F(:, i) > 0));
P(j, i) = F(j, i);
P(i, j) = -F(j, i);
i = j;
end

function [f, visited] = DFS(C, F, i, t, visited, f)
% C: 图的邻接矩阵
% F: 流量矩阵
% i: 当前节点
% t: 汇点
% visited: 访问标记
% f: 当前增广路的流量

if i == t % 如果到达汇点，则返回当前增广路的流量
return;
end

visited(i) = true;
for j = 1:size(C, 1)
if ~visited(j) && F(i, j) < C(i, j)
df = DFS(C, F, j, t, visited, min(f, C(i, j) - F(i, j)));
if df > 0
% 更新流量矩阵
F(i, j) = F(i, j) + df;
F(j, i) = F(j, i) - df;
f = df;
return;
end
end
end

f = 0;