数学建模--图与网络（2）

杨利霞

最大流：

注意Matlab 中的最大流问题是必须是单源和单汇问题，因此这里需要构建虚拟的源点S和汇点G。
6 P! k9 Q' V" q% f9 g( }1 O+ q5 ^clc,clear
a = zeros(9,9);
+ {) g! a2 k  K) e1 xa(1,[2:4]) = [20,20,100];
4 ]  B0 v6 w- j, A3 Wa(2,[5 6 8]) = [30,10,40];
& e; m" M6 i: Z  ia(3,[7 8]) = [10,50];
& M$ X/ _! @# f& ma(4,[5:8]) = [20,10,40,5];
a([5:8],9) = [20,20,60,20];
a = sparse(a);
[b,c] = graphmaxflow(a,1,9)

最大流拓展：最小费用最大流

仅仅是在求得最大流之后进行对最小费用的求解：

- r3 \7 P- R/ N8 G+ ~/ Aclc,cleara = zeros(5);a(1,[2 3]) = [10 8;a(2,[4,5]) = [2 7;a(3,[2 4]) = [5 10;a(4,5) = 4;a = sparse(a);[b c] = graphmaxflow(a,1,5)

最大流量为11

自定义Matlab代码：

- D9 ^5 `% @. U9 e. D2 E) \7 s最小费用求解
% n, x1 @# i9 U' B; ]8 Z
Lingo:

model:
sets:
nodes/s,1,2,3,t/:d;
# S$ U- @& W8 j( p7 I9 I) ]) aarcs(nodes,nodes)/s 1,s 2,1 3,1 t,2 1,2 3,3 t/:b,c,f;
* q5 L3 `& ^7 A( ~% x' Rendsets
data:
4 r4 q( i, e" c3 ub = 4 1 6 1 2 3 2;
. m3 a/ x" s: E6 k( R& jc = 10 8 2 7 5 10 4;
& _! X1 Z0 m+ X" Hd = 11 0 0 0 -11;
. i. c3 O6 K1 x! w- xenddata
) a, Q( ?$ R, Fn = @size(nodes);
min = @sum(arcs:b*f);
@for(nodes(i)sum(arcs(i,j):f(i,j))-@sum(arcs(j,i):f(j,i)) = d(i));
, B$ T3 X8 A% y$ f0 L1 k- I6 c9 K@for(arcsbnd(0,f,c));
# P; l$ [+ N) B* d9 send
; x+ X( K% H8 \3 e# I1
2
- U+ ^$ T  A0 d* U3
2 Z& ^7 s0 |9 j: J! y( C4
# P8 w' D2 V. e; t& Z  O9 [5
2 ~8 ~9 N, N4 _* I$ D$ n6
7
, m' Y- Y0 y$ f! k' a5 K8
% n( d( U( J  K7 o0 @# r' y2 f' W6 [9
) k: t& _) _3 `; Y10
11
: \6 r; U( M( N/ h& z% ]4 e12
13
- |1 V) W3 `$ J14
15
7 Z: P5 Q. }' r: L' E$ VMatlab实现：


) P+ b0 h$ M6 }! Mn = 5;
%弧容量
a = zeros(5);
a(1,[2 3]) = [10 8];
1 L' L5 |8 s' ]7 M( q0 _a(2,[4,5]) = [2 7];
, d9 J5 b9 J( H, A+ E2 B) N( ea(3,[2 4]) = [5 10];
  _$ E4 q* z, Ka(4,5) = 4;
, ^1 ]6 \- f. W2 NC = a;
%C = [0 15 16 0 0;0 0 0 13 14;0 11 0 17 0;0 0 0 0 8;0 0 0 0 0];
% w- ?$ f/ E, g%弧上单元的费用
9 G8 S$ c* {6 t# q: v2 ia(1,[2 3]) = [4 1];
a(2,[4,5]) = [6 1];
: N; z; Q9 k7 Y, n! g5 ea(3,[2 4]) = [2 3];
  j# v% |# e  x+ l) T+ va(4,5) = 2;
5 n9 _/ M- G/ [9 w. v6 yb = a;
%b = [0 4 1 0 0;0 0 0 6 1;0 2 0 3 0;0 0 0 0 2;0 0 0 0 0];
1 y' ^# T" V" C3 l! r( j%wf表示最大流量。wf0表示预定的流量值
5 o: ^5 z) R3 q, O% C+ [wf = 0;
wf0 = Inf;
%取初始可行流f为零流
4 r* q+ |3 h* e% Zfor i = 1:n
    for j = 1:n
- \* s4 q* I# |        f(i,j) = 0;
    end
end
: S2 M( D) v) j) B: R- F9 x$ ]while (1)
- B3 {" j! B# J; ~+ m0 h; e    %构造有向赋权图
* r' [. {% _& ?4 X$ z+ T' x) |    for i = 1:n
        for j = 1:n
            if j~=i
% Z6 n2 {2 d  ?/ @$ b* B; j                a(i,j) = Inf;
            end
5 S% f& r! s0 h$ k1 i0 X8 U        end
    end
    for i = 1:n
. }) U5 Q4 {$ ?! a9 Z6 e        for j = 1:n
            if C(i,j) > 0 && f(i,j) == 0
# j5 W1 g& o' t* F) d: e1 r. d) D                a(i,j) = b(i,j);
, X3 ?( V4 K% {' I            elseif C(i,j) > 0 && f(i,j) == C(i,j)
) s4 o1 D# A) {: e% v9 a+ V# l                a(j,i) = -b(i,j);
5 W) h& ?( r+ K# Z% b) d            elseif C(i,j) > 0
                a(i,j) = b(i,j);
                a(j,i) = -b(i,j);
            end
3 d4 c3 m7 ~+ z0 H2 d& [- v4 {        end
    end
' K' g( ^4 ~4 g4 X) w' t    %使用ford算法求最短路，赋初值
7 {1 h" _+ g) j; n: C- _    for i = 2:n
        p(i) = Inf;
        s(i) = i;
/ q. U& `) ^% p- L4 W    end
    %求有向赋权图vs到vt的最短路,赋初值
+ H, _& N! g- Z! A, _5 m    for k = 1:n
/ C% s; l8 {! w6 M7 f- a        pd = 1;
; |3 Y, B/ y/ k* G        for i = 2:n
9 x! y" G2 R6 e: y9 C            for j = 1:n
+ ]) j* E% \9 N( N$ ]% I                if p(i) > p(j) + a(j,i)
* R) T- ?% @) ]$ m                    p(i) = p(j) + a(j,i);
5 I# Q$ t# Z* }% N* C' `4 v                    s(i) = j;
" N; {& D% J$ b; Q2 d  g                    pd = 0;
% }  g: I0 V0 C7 e0 L( G                end
) E, f% Z* u4 [: I2 x! {            end
        end
% Z+ R, D* w: j  \8 d        %求最短路的Ford算法结束
        if pd
5 J- G4 F* d- `' Z5 t5 G5 n7 S            break;
) v5 O7 ?, a' |5 u0 X4 ~: s' s: P        end
% K% O8 B- Y0 q5 K, c$ e+ _. Y    end
' f+ }9 R( H, b) m" @! }    %不存在vs到vt的最短路，算法终止，注意在求最小费用最大流时构造有向赋权图中不会含有负权回路，不会出现k = n
    if p(n) == Inf
- L6 M1 u6 W" E( ]. U/ j5 S        break;
    end
/ O) n! m# \) a2 w/ m! ~* G: `    %进入调整过程,dvt表示调整量
0 ?8 O4 \3 M0 A: I! T% y5 E, g0 ?    dvt = Inf;
( Z. b% `4 o/ i$ N    dvtt = Inf;
    t = n;
; }+ q+ C9 {7 i. O+ N0 y    while(1)
        if a(s(t),t) > 0
$ l( ~4 X) i2 K/ O0 Y7 k            %前向弧调整量
( I) [/ k. |) d; |1 R3 e            dvtt = C(s(t),t)-f(s(t),t);
; a+ ^1 B. k6 _  p; ~" W$ m4 N            %后向弧调整量
        elseif a(s(t),t) < 0
" b% K7 G0 R1 h! ~            dvtt = f(t,s(t));
+ r+ j; m. J9 _) N' G% a, D/ a" r        end
7 j. ]# }& f5 b        if dvt > dvtt
            dvt = dvtt;
7 E0 j0 e  u  Y: Z1 s1 A% j        end
- f0 O  K1 Z5 d) G8 T; F7 n        %当t的标号为vs时，终止计算调整量
- {* ~0 y; H$ i+ t1 \        if s(t) == 1
            break;
( P4 a4 B' K& H8 c  r        end
        %继续调整前一段弧上的流f
        t = s(t);
    end
    pd = 0;
0 ^* t' N: }! [$ N+ ?( T$ V    %如果最大流量大于或等于预定的流量值
    if wf + dvt >= wf0
        dvt = wf0 - wf;
8 |* g7 P* f3 \$ V        pd = 1;
    end
    t = n;
    %调整过程
    while(1)
    if a(s(t),t) > 0
  h$ }2 y; I. d: w. F" n, k" y        %前向弧调整
        f(s(t),t) = f(s(t),t) + dvt;   
    elseif a(s(t),t) < 0
        %后向弧调整
        f(t,s(t)) = f(t,s(t)) - dvt;
" t0 J. S8 F3 H' f3 _, O& T    end
( U7 S" O5 S) N  y    %当t的标号为vs时，终止调整过程
    if s(t) == 1
        break;
    end
    t = s(t);
% ~% K& h" x9 b& p' W2 M! Z    end
$ C, {0 Y4 y8 p( l% y4 ^7 Y% W$ I- G    %如果最大流量达到预定的流量值
. L4 J3 P2 ?9 C8 x" q8 o2 F0 O$ j    if pd
8 q, `. \+ K- d& B- d        break;
. f% u5 z) ]$ A: N; `! x' }    end
    %计算最大流量
8 ~) o" k1 _" g    wf = 0;
    for j = 1:n
        wf = wf + f(1,j);
# U$ O/ u& E' t3 L! v7 `' V" D+ G  B    end
end
* t# r" F5 A: b) @' W& v%计算最小费用
zwf = 0;
for i = 1:n
    for j = 1:n
        zwf = zwf + b(i,j)*f(i,j);
, k8 r7 W( Q; j8 z. o    end
+ u9 q; Y! e4 O: E$ y" ~end
%最小费用最大流
f
%最小费用最大流量
# y- f) e! f5 S! Vwf
' Z+ q* C' D; {& x; i. C4 d%显示最小费用
zwf
( ?) B' n0 C; m1
+ }& [7 A' S  r3 m% P$ s) Z/ k  b2
9 a9 `+ f7 O- C1 e3
& T9 a6 k7 b) S2 Q: Z! ]/ S! U4
2 u2 S0 F, c" F9 y7 l5
6
! o+ t+ o' w3 a+ x5 ?$ U: P7
8
9
10
' x2 V" B' z& K  e" a11
# P5 Z. v& b( X. V4 t! u* K+ q12
  f5 d0 D' x; b! L( l! _! i13
% A2 n- \9 G' n+ D' B14
0 x! V( u' c; _* z/ p6 e1 [" H15
' n3 |2 G) Z  z; |* S0 O16
# U7 Z8 l) V, F5 ]4 f* d17
2 W$ ]  N! e6 M$ O+ J4 j18
# A3 q- N% G: `: V8 z% V19
8 A- }/ l: D" s( A* z20
* C1 p" Q/ I4 ~' B3 @  y2 E6 M( ~& a; I21
22
' M  H$ S. A3 x. d7 L. S/ h8 `23
24
) X* M3 ~0 b4 |0 v: c25
5 T5 G! Z' g5 Z$ ?1 o" V26
27
28
29
3 ]# r" t% b3 k, ~" ^30
31
1 F' c% o$ ^1 L( V32
33
8 `1 z: X) H6 ^8 b, S+ _3 a34
35
, i. z1 f0 F: A0 r8 S5 v8 w36
37
38
: A# S: G# b3 M) t: m2 f39
40
/ G, k- V2 ?  w9 D2 c" X41
2 I& o' W' A" u. }& k$ {42
43
9 V, V) W0 U: \! P44
45
' `" q; }* G& d  H9 E46
47
48
49
, E. e. s' Z  t# l9 e/ i; S50
9 }: {8 w! O. X51
52
53
54
55
56
57
" e4 C& e- S" ]: Z0 W58
! d* B5 {6 v7 I4 a$ Y59
2 p  t& \! \3 z+ [, o' h# l60
8 X! M8 {$ P) t0 t# w2 I' r61
: d% W3 |8 O9 U/ `$ C0 [/ U6 e& F4 B62
) y  D) q) e# I4 \# \0 a63
! `! {$ K- r4 {3 {% n0 {& i+ f64
65
6 e, i' z- J- q! S. h66
67
$ {7 F3 v2 N5 D( f' h9 @- r68
69
70
9 y& n% h3 Y1 \; ]3 Z71
1 U; t, n* v! |" \- i9 t4 y72
73
74
: o" A1 ^0 I2 P( }$ o75
+ a% e2 _+ H3 T1 k76
, t. n! @  {. r- O2 [1 v& A" i8 N77
9 F+ t! g; T9 [( h1 F# K78
79
80
81
. u8 v; e" m! b2 N+ g% @) O. ^  K82
83
84
" @% D6 G/ p9 O4 h' x85
86
9 a0 j7 M1 R5 L4 A87
88
4 b4 z$ \' S  l9 y/ F89
/ j( m! u$ m0 A% s90
91
3 f+ S5 p3 V* e1 a$ |4 {/ T5 r2 F92
, Q" ~8 r; c( d% d+ U93
94
95
96
97
98
99
2 {. }8 z; f( ]3 a100
9 d+ I$ C4 Q' q7 H5 S( w/ _/ T101
9 x( k9 E% \/ r4 V- C102
. v0 _. H. c  ?0 a103
104
105
  a9 H( i5 T1 a- @. R3 S106
107
108
109
1 ^& b( x. i. l4 j3 F* D110
' Q( u! b. T- M; d9 k. N& Q111
112
113
* Z* v" Q. s* C" V8 ]114
1 l# u$ Q+ W# p; ~& N  w: z115
1 N* q6 Z. F# k2 c" ?9 }) }116
/ J. J+ d% U. p( n& ?117
118
3 q+ m$ u) z# C7 z8 v% B) {& [- o119
/ V% q  X/ ?6 I: S. o9 ?" _120
/ F( ~$ X& G0 Y7 H" I! V121
122
123
- L$ z! ?/ O/ r& S5 b124
125
/ ?  ^+ m5 q' c; U# e2 U) O/ a6 U  s126
  ]' @7 A1 s, i0 g- l1 L! G$ ^6 Q  R127
128
. G2 y+ _, [* U9 G( C0 V9 |, e129
1 H- h! T. ^) `: D130
  j- ]4 Q. L4 l/ h- p131
132
3 n8 l7 _# M3 F) x133
6 G( T$ h: q5 ^& D- Z134
: Q; E# W  [! h1 @9 M135
6 a+ j  G" g  Z5 E) T. E& s136
0 q& h, a% u# d8 e137
! @' ?) E$ J/ W5 ]138
139
140
5 m. |2 f- L9 w4 w( y7 J9 Q匹配问题：

4 ]; v. F8 U' A2 C9 D- |, K3 K. T最大匹配：


代码实现：

m = 5;
n = 5;
6 z6 p2 [0 A, d+ [6 ]A = [0 1 1 0 0;1 1 0 1 1;0 1 1 0 0;0 1 1 0 0;0 0 0 1 1];
$ n/ n, q, U3 b8 YM(m,n) = 0;
for i = 1:m
    for j = 1:n
. L( F4 @: |. L" R! N# O; w/ `8 b% w    %求初始匹配M
' ?" _  t5 ^4 J$ ]! E. x! H( Y        if A(i,j)
            M(i,j) = 1;
            break;
, P4 H# h! y/ `7 ~: [- D        end
    end
$ J' b0 o, {, j( J! M' z8 H- F    %仅含一条边的初始匹配M
    if M(i,j)
        break;
, m/ b& L7 j5 x1 q; r1 h    end
0 ^  q, `" A" i9 G) c+ h2 cend

2 h5 N3 z. ?8 |while (1)
) b% a9 e: c5 n0 r* U7 N    %记录X中点的标号和标记
8 r" P& `( k# e2 {* P    for i = 1:m
; }, U) M# c9 U- [0 \        x(i) = 0;
  |8 W  P- ^7 R& w' D! B3 O    end
, J8 K6 S+ P8 @' O( `, i. ]' A    %记录Y中点的标号和标记
* e# w2 s) }9 Y5 S6 h7 f    for i = 1:n
; G: V% N( _' W2 b        y(i) = 0;
6 Y% r* W* g* e' j, C    end
    %寻找X中M的所有非饱和点
    for i = 1:m
        pd = 1;
+ E% {- a7 H% ^1 I/ ^        for j = 1:n
0 _6 f3 }# w+ }# D, Y9 E            if M(i,j)
2 n# O) C" R/ U& p9 _                pd = 0;
# a1 a$ z0 U& K- J- T& |0 o5 R            end
$ ]7 Q. D( a, W  O) }- b" G9 _4 @        end
        if pd
            x(i) = -n-1;
5 Y. K# {) e1 B* g) y! ?        end
4 X' j# A* T) g' w& T; o    end
1 U7 {. X+ v$ i( U    pd = 0;
; L6 E4 N7 O5 J! r: w  O( k    while(1)
  Q3 K5 z& p" Z$ q% e        xi = 0;
        for i = 1:m
; s& a* u/ }$ e8 e: L  @& C2 r! i            if x(i) < 0
4 M2 r% g/ I" [: E- ?9 U9 L                xi = i;
) f6 m" ~- |8 v3 j# m( u9 A                break;
                end
. e  c  W  l4 `8 D" `4 |            end
            if(xi == 0)
& ~$ M- O- l9 E) }2 w& N                pd = 1;
& ^9 q, T) u9 U+ W  ^1 E8 Z                break;
            end
            x(xi) = x(xi)*(-1);
            k = 1;
4 {- g) e7 J1 a- S" \% n3 [$ X            for j = 1:n
                if A(xi,j)&&y(j)==0
                    y(j) = xi;
                    yy(k) = j;
7 p8 I( z7 \& a+ p5 `                    k = k + 1;
                end
% A! z: r% t& ?- }6 h            end
# O% c; V! B. L7 J9 S            if k > 1
9 \7 a0 g/ u* B                k = k - 1;
                for j = 1:k
# y2 D1 ?" _  B$ g  J1 U                    pdd = 1;
' G$ O7 W( u, P6 q) z% L+ t6 C                    for i = 1:m
& C; }/ \! H) g" i; X& |* V                        if M(i,yy(j))
                            x(i) = -yy(j);
                            pdd = 0;
                            break;
7 Q/ i1 P; `  f                        end
                    end
! h, O3 s9 B. g8 e  G9 M' @5 h                    if pdd
  a6 [& Y' w* F2 F: m( t                        break;
" r, b* @/ V* ^2 s4 B* e                    end
4 h4 D; M) M9 R% a( g0 E6 p                end
                if pdd
5 X+ y3 `) A( w3 j- Z9 y3 `( V2 x                    k = 1;
                    j = yy(j);
- k4 v5 K. D8 H7 @6 }/ |                    while(1)
- G" E! @* ~8 K" J- S                        P(k,2) = j;
                        P(k,1) = y(j);
                        j = abs(x(y(j)));
                        if j == n+1
                            break;
7 h- p( y6 g# E+ p; k                        end
                        k = k+1;
- ~9 a8 X$ A# I( f1 X, d                    end
                    for i = 1:k
                        if M(P(i,1),P(i,2))
  D* y* r  v; _8 W6 _1 j                            M(P(i,1),P(i,2)) = 0;
% ]$ n: J4 x# ~. z2 {                            else
                                M(P(i,1),P(i,2)) = 1;
1 J1 s3 v  b" K7 r& Z                            end
                        end
0 G; e8 {0 b7 X( C" f; H1 R                        break;
: y8 h2 c6 \9 p( T9 _                    end
; e- u" x' w+ k$ J0 [                end
* a4 }, X, x: ?& h            end
- h- c( N7 f) R            if pd
                break;
5 V7 W4 |8 v/ y$ |) U" d* k            end
        end
1
; j/ y3 ]1 m4 {5 h2
3
4
1 h. y1 a$ S& ?; O' O7 Z; f5
6
/ k# e$ Y0 A0 l* C. i9 G  k7
8
( O) R9 C6 Y" R7 o9
10
11
12
13
14
8 V. m1 o4 U5 i% C$ C6 K2 B15
/ a9 g3 L: V4 y6 [% j. l16
17
) y) u4 O$ c: ]' m$ \+ J: \18
3 M: d8 L$ k# b4 P7 g4 {) h19
4 P; S' r4 |& g" o: n& R  Z20
; E  f0 Y8 ]# P( d21
22
: H" `2 ^5 z; T# P. g+ k23
24
3 J0 V! H# a; I25
26
27
2 s$ i6 v8 u- y8 J+ u28
29
30
' c* Q5 o" I- j. k8 s% C9 a: G31
2 s4 X3 j/ ~- |% }32
0 }  i; P0 A" H5 ^. j% L# G: b33
  H$ k/ M+ ^5 p34
35
  u, z, Z4 i* m# V% {* g/ V+ |6 q36
37
- _: y! x5 |7 H38
/ u+ K7 U5 E3 |9 g39
40
" e4 e; u( `+ l4 S8 `) J  l41
42
43
44
45
) \( K, e8 L% h+ B$ V& l# {. L46
47
* n% c$ `. B: [48
49
  b  V0 H/ h# X/ v  q% c% J50
51
52
53
8 [  g- w& ]% Z, h# I! a9 e, t54
55
56
57
0 d( J& \5 w) M6 u- E58
59
60
1 `3 O5 y1 R( B61
8 y* Y( H! n6 x* _! L  L62
0 R. N& W% @; I7 Q/ n  _/ j63
5 h9 R; E2 @0 }' ]. g& {4 v" z64
! J% o2 q/ `- e9 b) J; p. g8 p65
66
/ R8 \+ U+ P2 r8 ^2 w% m2 Z67
68
69
70
4 D" o# N1 p' g# ^8 X: v71
$ Z8 _) u( Z& Q& {( v5 `# E9 k72
73
1 h+ F* F* |$ x! X- u74
75
6 A8 ^% Z# S/ l76
3 h! f6 e" d, h6 N# Q" O' C6 h77
78
+ k& l; P8 W3 k' B79
80
81
3 C+ t. X0 e* l! L0 h82
83
' I/ F  {! ^- T% N0 Z84
: I" y3 w" o- m( h1 [! K85
86
87
88
89
8 ^% `1 q) R( J) i* a# k90
91
92
  R6 A" Q) w" |& y93
2 f4 ]2 a# q: s94
95
96
3 w$ Y" e# o1 S1 c. E1 F97
  ^6 i" z8 ^* Z98
99
100
- y' y0 J( C8 a* f' U101
, N) r0 R6 q9 V) C% |$ M102
% k0 t8 I% ^* B8 K/ w103
最佳匹配

代码实现：

n = 4;
A = [4 5 5 1;2 2 4 6;4 2 3 3;5 0 2 1];
; m6 z+ c: O+ B! }, M$ @M(n,n) = 0;
$ a  j6 s, e& c; e  R  M: d4 ?for i = 1:n
    L(i,1) = 0;
$ B" ]) D- L* u. S! {1 H4 r    L(i,2) = 0;
end
: n' i0 j" u! z. d, s6 v. {+ H  d4 \%初始化可行点标记L
0 C; O2 B7 H, K8 ?for i = 1:n
    for j = 1:n
        if L(i,1) < A(i,j)
9 [5 z+ S. V7 Y% }            L(i,1) = A(i,j);
        end
; H+ Q& s; r+ Y- J  ~7 x    end
2 ~' V. ?$ t; `# ?  Nend
0 e; ^# I$ \* k5 X3 w9 Q9 ]) _& ~: N%生成子图Gl
- j+ t' {6 f$ @for i = 1:n
2 k) u& N" w) E    for j = 1:n
        if L(i,1) + L(j,2) == A(i,j)
            Gl(i,j) = 1;
            else
5 D2 N! W4 i6 E# P( h7 s4 }                Gl(i,j) = 0;
        end
% ^# q! J$ ~: j4 K& f; q( d& z; O5 B    end
end
! k. \/ J# o7 h. x% E%获得仅含Gl的一条边的初始匹配M
ii = 0;
( h+ h  N8 P6 I0 ^3 T4 zjj = 0;
0 T9 N8 A8 |2 q6 v& D  k4 \for i = 1:n
    for j = 1:n
        if Gl(i,j)
1 @# E4 D& n. {$ c            ii = i;
$ j9 j+ y8 K& \/ E. u            jj = j;
! m+ u3 ~1 Y; j( r# K9 J8 V            break;
        end
    end
  O; ]. T; `% m  v    if(ii)
        break;
* d. l" u, x! X' J$ B+ l! Z" l    end
, ~7 u3 R( y  yend
M(ii,jj) = 1;
" y! x" ^2 N7 C! r* z# Bfor i = 1:n
3 z3 ?  L: }3 A, u6 M* B4 Z% ~$ \    S(i) = 0;
8 f. o4 C' X. W    T(i) = 0;
    NIS(i) = 0;
end

) c* z7 u( W! O: G+ V
while (1)
  P( v/ \4 q' x+ w/ b. J    for i = 1:n
! t. D# l( ~  ]# C+ `4 N8 _        k = 1;
        for j = 1:n
            if M(i,j)
7 K: L. ]( H$ ], e                k = 0;
$ X2 w& k; |+ s; ?& j3 K                break;
            end
        end
        if k
            break;
) }9 x0 S4 A1 j" r& c8 i        end
* a2 X3 Z: q- [    end
8 M0 l( v& @/ ?, x" G0 R/ v0 B%获得最佳匹配M,算法终止
; g6 ^6 Q7 q( A    if k == 0
8 i$ s# B+ X3 B* [        break;
    end
1 B- L3 c' J$ ]! S
+ r% g. ~2 L2 b2 Q4 W
%S = {xi}
4 n4 N  M& {7 r9 `/ l$ n! IS(1) = i;
jss = 1;
2 }. t+ t# [3 f1 A: o0 rjst = 0;
/ P5 d  Q" o3 f- `: M0 N( S* i, @6 k9 }while(1)
    jsn = 0;
    %选择NL的值
    for i = 1:jss
: B) O; q9 D9 C9 i. w        for j = 1:n
            if Gl(S(i),j)
) ]4 ^5 G& l2 g$ `3 g& m" U. b                jsn = jsn + 1;
                NIS(jsn) = j;
" D3 L& Y; v. I7 k4 Z5 X* ^; g+ f/ f" |                for k = 1:jsn-1
& G( B$ g2 t, h: `                    if NIS(k) == j
, `- `; n0 b) F. H) k                        jsn = jsn - 1;
" Q% d& [8 _6 `                    end
                end
            end
        end
    end
    %判断NL(S) = T ?
% h3 R# Q; \" g; M# ~* [% @9 w    if jsn == jst
        pd = 1;
        for j = 1:jsn
            if NIS(j) ~= T(j)
                pd = 0;
! i& c" C2 J" q4 f( W( R2 m                break;
9 j9 Z% f" J. n            end
0 T$ G4 E" @9 u. @        end
9 L- R) Q1 k3 ^6 T- T  z0 _2 P! X, C: ]    end
    %如果NL(S) = T  计算al的值
    if (jsn == jst) && pd
8 S* P% h+ g2 I& S; k        al = Inf;
& j- z0 H/ D! s6 e) m5 j) j        for i = 1:jss
            for j = 1:n
, j; D" l8 O# V2 ^/ e! L                pd = 1;
                for k = 1:jst
9 a: y3 R) d( A  ~; u                    if T(k) == j
                        pd = 0;
                        break;
                    end
5 w; T& C8 n9 q# n                end
+ S6 f) @# g8 q- j1 X  v                if pd && (al > L(S(i),1) + L(j,2) - A(S(i),j))
                    al = L(S(i),1) + L(j,2) - A(S(i),j);
3 A% y, e, d6 W$ L! ]                end
! n0 e2 y" O: W( d, ]. `; r            end
        end
        %调整可行点标记
        for i = 1:jss
            L(S(i),1) = L(S(i),1) - al;
        end
: P- ^+ u2 Y$ L4 S! H  |- G        %调整可行点标记
        for j = 1:jst
- ?! v1 o/ L; k            L(T(j),2) = L(T(j),2) + al;
# V) c9 p% ^. {" K8 g& R        end
2 M/ c. N5 |% p9 @* }) ]/ T6 w2 a4 a        %生成子图Gl
        for i = 1:n
% L2 ~4 F5 P) ?" Z( _            for j = 1:n
                if L(i,1) + L(j,2) == A(i,j)
                    Gl(i,j) = 1;
                    else
                        Gl(i,j) = 0;
                end
                    M(i,j) = 0;
                    k = 0;
            end
        end
4 v) ?7 {6 u3 \% Z: k, i1 k        %获得仅含Gl的一条边的初始匹配M
! P- k& N1 ^, f        ii = 0;
* {2 T  }. B" F. i        jj = 0;
5 e. I$ z" \3 f# p        for i = 1:n
$ z3 F) O7 j( `            for j = 1:n
/ p/ S2 z1 _! o. ?3 h1 N! \8 w/ |                if Gl(i,j)
  o$ r6 c" j- U9 V                    ii = i;
                    jj = j;
! d. o" T9 q6 {6 h8 f% o                    break;
                end
  o/ F+ ?# T- ]' A, f            end
            if(ii)
( ]3 u+ J# o" }3 T4 ^                break;
            end
        end
        M(ii,jj) = 1;
        break;
5 K/ I! \6 J! I$ }) I* i+ _        else
            for j = 1:jsn
                pd = 1;
8 K2 k* w: G( {; n1 @; {( G                for k = 1:jst
) X  R2 o- `$ i8 m, n+ g                    if T(k) == NIS(j)
                        pd =0
                        break;
1 q, O1 _! u) Y5 ]% ]                    end
                end
                if pd
* T' E: w7 y7 m$ ]" W  M: q                    jj = j;
: g; W6 {' I. [% i& w/ b9 j                    break;
# g: z/ `) Q0 {9 u* B/ M/ c                end
0 N* a/ d2 ~% w8 b! q            end
            %判断y是否是M的饱和点
/ n' N+ a6 L( @- ^; u            pd = 0;
            for i = 1:n
( P1 y) _4 x  G                if M(i,NIS(jj))
2 }: n4 t2 B4 H& Y' [                    pd = 1;
( q4 E% @# X- R: |- {8 |* \                    ii = i;
                    break;
( w" H7 i( J+ D3 M; B& [$ n  P5 W                end
. `- B' c; C% c            end
            if pd
                jss = jss + 1;
* [& {( S, l4 [2 G4 @# ^                S(jss) = ii;
1 E& u3 e9 B4 Z( a7 p  @" I9 Z                jst = jst + 1;
! N/ D8 O" [8 O9 T1 s) U; e& j                T(jst) = NIS(jj);
                else
/ n0 d/ `4 z& S                    for k = 1:jst
                        M(S(k),T(k)) = 1;
& t" o6 U9 |0 u! d" g                        M(S(k+1),T(k)) = 0;
6 c6 {1 M) M+ W/ ]% f                    end
% {: n+ h; L$ @4 e3 U) }: |                    if jst == 0
                        k = 0;
, T4 C1 u" G* X% Z2 M* y% x  J                    end
                    M(S(k+1),NIS(jj)) = 1;
                    break;
                end
6 E- g5 y* C1 n3 A; u( m            end
5 s7 k5 I9 c% c6 i' j  }        end
    end
    MaxZjpp = 0;
    for i = 1:n
: ~5 k" [" U" J# I; d        for j = 1:n
            if M(i,j)
7 c" [# q# ?* Z& X                MaxZjpp = MaxZjpp + A(i,j);
            end
        end
    end
. B7 z& j  d* d2 O) B) r    M
. a; ?1 q' b8 f/ j, @! k% F    MaxZjpp

6 U( Y8 {6 |# D% \: U+ c- \6 b

3 m/ N1 m1 g& p' H$ ]