最大流算法clc,clear,M=1000;c(1,2)=3;c(1,4)=3;c(2,3)=1;c(2,4)=20;c(3,6)=3;c(4,5)=10;c(5,1)=4;c(5,3)=2;c(5,6)=13;n=length(u);list=[];maxf=zeros(1:n);maxf(n)=1;whilemaxf(n)>0maxf=zeros(1,n);pred=zeros(1,n);list=1;record=list;maxf(1)=M;while(~isempty(list))&(maxf(n)==0)flag=list(1);list(1)=[];index1=(find(u(flag,:)~=0));label1=index1(find(u(flag,index1)...-f(flag,index1)~=0));label1=setdiff(label1,record);list=union(list,label1);pred(label1(find(pred(label1)==0)))=flag;maxf(label1)=min(maxf(flag),u(flag,label1)...-f(flag,label1));record=union(record,label1);label2=find(f(:,flag)~=0);label2=label2';label2=setdiff(label2,record);list=union(list,label2);pred(label2(find(pred(label2)==0)))=-flag;maxf(label2)=min(maxf(flag),f(label2,flag));record=union(record,label2);endifmaxf(n)>0v2=n;v1=pred(v2);whilev2~=1ifv1>0f(v1,v2)=f(v1,v2)+maxf(n);elsev1=abs(v1);f(v2,v1)=f(v2,v1)-maxf(n);endv2=v1;v1=pred(v2);endendendffunction[f,wf,No]=MaxFlowMinCut_Me(n,C)%利用Ford--Fulkerson标号法求最大流算法的MATLAB程序代码%f%显示最大流%wf%显示最大流量%No%显示标号,由此可得最小割%n节点个数%C%弧容量最大流算法for(i=1:n)for(j=1:n)f(i,j)=0;end;end%取初始可行流f为零流for(i=1:n)No(i)=0;d(i)=0;end%No,d记录标号while(1)No(1)=n+1;d(1)=Inf;%给发点vs标号while(1)pd=1;%标号过程for(i=1:n)if(No(i))%选择一个已标号的点vifor(j=1:n)if(No(j)==0&f(i,j)d(i))d(j)=d(i);endelseif(No(j)==0&f(j,i)>0)%对于未给标号的点vj,当vjvi为非零流弧时No(j)=-i;d(j)=f(j,i);pd=0;if(d(j)>d(i))d(j)=d(i);end;end;end;end;endif(No(n)|pd)break;end;end%若收点vt得到标号或者无法标号,终止标号过程if(pd)break;end%vt未得到标号,f已是最大流,算法终止dvt=d(n);t=n;%进入调整过程,dvt表示调整量while(1)if(No(t)>0)f(No(t),t)=f(No(t),t)+dvt;%前向弧调整elseif(No(t)<0)f(No(t),t)=f(No(t),t)-dvt;end%后向弧调整if(No(t)==1)for(i=1:n)No(i)=0;d(i)=0;end;break;end%当t的标号为vs时,终止调整过程t=No(t);end;end;%继续调整前一段弧上的流fwf=0;for(j=1:n)wf=wf+f(1,j);endendn=6;C=[030300001200000000300001000420013000000];[f,wf,No]=MaxFlowMinCut_Me(n,C)最大匹配算法A=[1101001110101010110000011];A=[1001001110000111100100101];A=[1101001110101010110000011];A=[1001001110000111100100101];A=[1001001010010011110000111];m=5;n=5;M(m,n)=0;for(i=1:m)for(j=1:n)if(A(i,j))M(i,j)=1;break;end;end%求初始匹配Mif(M(i,j))break;end;end%获得仅含一条边的初始匹配Mwhile(1)for(i=1:m)x(i)=0;end%将记录X中点的标号和标记*for(i=1:n)y(i)=0;end%将记录Y中点的标号和标记*for(i=1:m)pd=1;%寻找X中M的所有非饱和点for(j=1:n)if(M(i,j))pd=0;end;endif(pd)x(i)=-n-1;end;end%将X中M的所有非饱和点都给以标号0和标记*,程序中用n+1表示0标号,标号为负数时表示标记*pd=0;while(1)xi=0;for(i=1:m)if(x(i)<0)xi=i;break;end;end%假如X中存在一个既有标号又有标记*的点,则任取X中一个既有标号又有标记*的点xiif(xi==0)pd=1;break;end%假如X中所有有标号的点都已去掉了标记*,算法终止x(xi)=x(xi)*(-1);%去掉xi的标记*k=1;for(j=1:n)if(A(xi,j)&y(j)==0)y(j)=xi;yy(k)=j;k=k+1;end;end%对与xi邻接且尚未给标号的yj都给以标号iif(k>1)k=k-1;for(j=1:k)pdd=1;for(i=1:m)if(M(i,yy(j)))x(i)=-yy(j);pdd=0;break;end;end%将yj在M中与之邻接的点xk(即xkyj∈M),给以标号j和标记*if(pdd)break;end;endif(pdd)k=1;j=yy(j);%yj不是M的饱和点while(1)P(k,2)=j;P(k,1)=y(j);j=abs(x(y(j)));%任取M的一个非饱和点yj,逆向返回if(j==n+1)break;end%找到X中标号为0的点时结束,获得M-增广路Pk=k+1;endfor(i=1:k)if(M(P(i,1),P(i,2)))M(P(i,1),P(i,2))=0;%...
