答案選A：15+31=46
n=7;
C = [
0 28 7 0 0 19 0;
0 0 6 15 0 0 0;
0 0 0 0 0 12 0;
0 0 0 0 7 0 23;
0 0 10 0 0 0 18;
0 7 0 14 0 0 36;
0 0 0 0 0 0 0;] %弧容量C(i,j)
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記錄標(biāo)號(hào)
while(1)
No(1)=n+1;d(1)=Inf; %給發(fā)點(diǎn)vs標(biāo)號(hào)
while(1)pd=1; %標(biāo)號(hào)過程
for(i=1:n)if(No(i)) %選擇一個(gè)已標(biāo)號(hào)的點(diǎn)vi
for(j=1:n)if(No(j)==0&f(i,j)<C(i,j)) %對(duì)于未給標(biāo)號(hào)的點(diǎn)vj, 當(dāng)vivj為非飽和弧時(shí)
No(j)=i;d(j)=C(i,j)-f(i,j);pd=0;
if(d(j)>d(i))
d(j)=d(i);
end
elseif(No(j)==0&f(j,i)>0) %對(duì)于未給標(biāo)號(hào)的點(diǎn)vj, 當(dāng)vjvi為非零流弧時(shí)
No(j)=-i;d(j)=f(j,i);pd=0;
if(d(j)>d(i))
d(j)=d(i);
end;
end;
end;
end;
end
if(No(n)|pd)break;end;end %若收點(diǎn)vt得到標(biāo)號(hào)或者無法標(biāo)號(hào), 終止標(biāo)號(hào)過程
if(pd)break;end %vt未得到標(biāo)號(hào), f已是最大流, 算法終止
dvt=d(n);t=n; %進(jìn)入調(diào)整過程, dvt表示調(diào)整量
while(1)
if(No(t)>0)f(No(t),t)=f(No(t),t)+dvt; %前向弧調(diào)整
elseif(No(t)<0)f(No(t),t)=f(No(t),t)-dvt;end %后向弧調(diào)整
if(No(t)==1)for(i=1:n)No(i)=0;d(i)=0; end;break;end %當(dāng)t的標(biāo)號(hào)為vs時(shí), 終止調(diào)整過程
t=No(t);end;end; %繼續(xù)調(diào)整前一段弧上的流f
wf=0;for(j=1:n)wf=wf+f(1,j);end %計(jì)算最大流量
f %顯示最大流
wf %顯示最大流量(f的最后一列即流進(jìn)結(jié)尾節(jié)點(diǎn)的流量總和，即最大流量)
No %顯示標(biāo)號(hào), 由此可得最小割, 程序結(jié)束
代碼的例題請(qǐng)看淺談求解最大流的方法
例題2最大流問題
