zgl.m

增广路的程序 挺简单的 大家看说明就能看懂

%去年写的了 ，程序不算复杂，大家可以参考一下 了解MATLAB的基本编程思想


function [x,wc,bh]=zgl(c,x)
en=length(x(1,:));
vb=cell(1,en);%标号内容
bh=zeros(1,en);%是否已标号
jc=zeros(1,en);%是否检查过
gbf=zeros(1,en);%是否gai标记
csw=zeros(1,en);%标号的点已将流量传输至下一点
%yt=zeros(1,en);% 端点的上一源头
vbh=cell(1,en);%候补标号内容
for i=1:en
    vbh{1,i}=[0,0];
end
%for i=2:en
 %   for j=1:i-1
  %      if x(i,j)&&yt(1,i)~=0 
   %         yt(1,i)=j;
   
         %end
    % end
   %end
%yt(1,1)=-1; 
gbf(1,1)=1;
vb{1,1}=[0,inf];
bh(1,1)=1;        
for i=1:en
    for j=i:en
        %if x(i,j)c(i,j)&&c(j,i)==0&&x(i,j)~=0&&gbf(1,i)&&bh(1,i)
       if x(j,i)>0&&gbf(1,i)%&&bh(1,i)
            %gbf(1,j)=0;
            % end
            gbf(1,j)=1;
       end
   end
     for  j=1:en
        if x(i,j)<c(i,j)&&gbf(1,i)%&&bh(1,i)
            gbf(1,j)=1;
         end
     end
    
        
       % if (x(i,j)<c(i,j)||c(j,i)~=0)&&gbf(1,i)==0
        %   gbf(1,j)=0;
        % end
        %end
end



for i=1:en
    jc(1,i)=1;
    for j=1:en
        if x(i,j)&&gbf(1,j)&&~bh(1,j)
            jc(1,i)=0;
        end
    end
end

wc=1;
for i=1:en
    if i==1&&jc(1,i)
        gbf(1,i)=0;
    end
    if ~jc(1,i)&&bh(1,i)
        wc=0;
    end
end
%wcq2=1;
%for i=1:en
    %if c(1,i)>x(1,i)
     %   wcq=0;
     %end
    %if c(i,en)>x(i,en)
    %    wcq2=0;
    %end
    %end

%if wcq2
 %   wc=1;
 %end
        
if wc==0
    for i=1:en
        if bh(1,i)
            for j=1:en
                if x(j,i)>0&&~bh(1,j)&&gbf(1,j)%&&~csw(1,i)
                    t1=x(j,i);
                    t2=vb{1,i}(1,2);
                    t=min(t1,t2);
                    vbh{1,j}=[-i,t];
                    %bh(1,j)=1;
                   % if t==t2
                    %   csw(1,i)=1;
                    %end
                end
             end
            for j=1:en
              %if yt(1,i)<yt(1,j)
                 if x(i,j)<c(i,j)&&~bh(1,j)&&~csw(1,i)&&gbf(1,j)
                    t1=c(i,j)-x(i,j);
                    t2=vb{1,i}(1,2);
                    t=min(t1,t2);
                    %vb{1,j}=[i,t];
                    %if vb{1,j}(1,1)
                        if t>vbh{1,j}(1,1)
                            vbh{1,j}=[0,0];
                           vb{1,j}=[i,t];
                           bh(1,j)=1;
                        end
                       
                    
                        %end
                    if t==t2
                       csw(1,i)=1;
                    end
                end
            end
            
            for j=2:en
                if vbh{1,j}(1,2)~=0
                    vb{1,j}=vbh{1,j};
                    bh(1,j)=1;
                end
            end
              %else
             
          end
        end
    
    
    if bh(1,en)
        i=en;
        while bh(1,i)&&i~=1
            j=abs(vb{1,i}(1,1));
            if vb{1,i}(1,1)>0
                x(j,i)=x(j,i)+vb{1,i}(1,2);
            elseif vb{1,i}(1,1)<0
                x(i,j)=x(i,j)-vb{1,i}(1,2);
            end
            i=j;
        end
    end
end
%x,wc,bh