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

杨利霞

最大流：

注意Matlab 中的最大流问题是必须是单源和单汇问题，因此这里需要构建虚拟的源点S和汇点G。
clc,clear
" W0 P9 L% r! N) n7 ca = zeros(9,9);
a(1,[2:4]) = [20,20,100];
a(2,[5 6 8]) = [30,10,40];
2 X' Q& Z$ O$ W2 d# ua(3,[7 8]) = [10,50];
a(4,[5:8]) = [20,10,40,5];
& W  {: e; V3 \3 aa([5:8],9) = [20,20,60,20];
a = sparse(a);
[b,c] = graphmaxflow(a,1,9)
: H+ ?# w' z5 d9 X) O

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

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

clc,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)
* o, e7 [1 M3 }" C8 S

最大流量为11

自定义Matlab代码：

+ J& W- R3 U5 S/ H, t1 H" ]
最小费用求解
0 b/ V- f% j! z, |" D0 \8 U" ], a7 \
Lingo:

model:
sets:
nodes/s,1,2,3,t/:d;
5 u) H  J  ^; Uarcs(nodes,nodes)/s 1,s 2,1 3,1 t,2 1,2 3,3 t/:b,c,f;
endsets
: ?( y% X! q3 R9 Q+ F* V! l$ Edata:
b = 4 1 6 1 2 3 2;
c = 10 8 2 7 5 10 4;
d = 11 0 0 0 -11;
& r8 U/ }0 t8 h- J; e$ X" Venddata
n = @size(nodes);
min = @sum(arcs:b*f);
7 ?% G6 y) S) o9 S$ \' ^@for(nodes(i)sum(arcs(i,j):f(i,j))-@sum(arcs(j,i):f(j,i)) = d(i));
7 {" P3 l3 T7 i3 o@for(arcsbnd(0,f,c));
end
6 e7 D. n6 W& P7 f1 S0 E1
9 I5 g( K! T9 o" |4 z. k2
7 R. z2 J$ ^! n* ]8 G  l9 j8 j. ?3
4
1 r8 S& `+ E, F4 l% K9 @+ w5
1 U; h# a$ B6 m, G% v& ~6
7
& s- n8 C+ L7 G0 f. y+ }! p0 l8
9
! E/ ~2 j' n6 x; \10
9 v) Y1 v4 ?- z' Y6 n11
; e" a- n( l$ {0 G7 j12
8 ~7 V, Q0 W2 m- D( L/ I# I6 r13
  Y8 Z* t3 D5 q0 I3 g; `14
% F& R$ S: C6 j5 A15
Matlab实现：
8 w0 [) d; e  j4 U
. |' a) H+ f' g  [& B8 Z  @0 [
n = 5;
%弧容量
' |2 G# J5 T! \  K) y/ \; La = zeros(5);
a(1,[2 3]) = [10 8];
a(2,[4,5]) = [2 7];
4 P% S! E' J. _( V0 T: [  G# Ca(3,[2 4]) = [5 10];
a(4,5) = 4;
" [! X2 O4 Z3 g% z: v: d5 \8 ?C = a;
1 p0 g1 [) j- O5 w& x: \: _9 q8 @%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];
% e9 p) N  R; `8 N$ I/ S%弧上单元的费用
9 O& f# Q& h5 G3 Y2 H1 l5 ua(1,[2 3]) = [4 1];
a(2,[4,5]) = [6 1];
0 M. a4 E7 K5 j. x/ y: Va(3,[2 4]) = [2 3];
a(4,5) = 2;
b = 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];
%wf表示最大流量。wf0表示预定的流量值
! P: g1 m! r2 _1 bwf = 0;
5 ^" t1 E4 D) f9 |2 d8 |9 n* Kwf0 = Inf;
%取初始可行流f为零流
3 y* r% G7 Y, afor i = 1:n
    for j = 1:n
0 i, ~5 y7 }# {        f(i,j) = 0;
* m0 j4 W0 n& m" G3 j' c    end
2 O4 f% L# ]$ ?$ U; E4 S! \end
while (1)
    %构造有向赋权图
    for i = 1:n
  a  e2 e* u/ {! ], K" @2 z        for j = 1:n
: W: v4 p3 ~: r7 X$ t            if j~=i
                a(i,j) = Inf;
            end
        end
! G$ B! ~  t5 [    end
# E8 ]7 M" o- Y5 S    for i = 1:n
' e+ v2 O. |# _9 }- e7 q        for j = 1:n
4 D: B0 i  L( E  |- y5 S            if C(i,j) > 0 && f(i,j) == 0
3 j3 @7 h" j$ t+ |4 K& n                a(i,j) = b(i,j);
/ d+ s9 j; Q! r3 Q+ H/ ?2 ^            elseif C(i,j) > 0 && f(i,j) == C(i,j)
6 D1 G2 A$ w7 O5 n6 ~( K3 b3 @8 E                a(j,i) = -b(i,j);
3 ~, t0 [8 v8 \1 _3 C1 o            elseif C(i,j) > 0
8 C' l6 }% M0 t3 ^6 g& I  ]                a(i,j) = b(i,j);
                a(j,i) = -b(i,j);
            end
        end
8 i4 s8 {) }( i    end
    %使用ford算法求最短路，赋初值
    for i = 2:n
& \, W" s2 D2 \        p(i) = Inf;
        s(i) = i;
    end
    %求有向赋权图vs到vt的最短路,赋初值
0 i- ]+ p/ G( N. `  [' W" Q    for k = 1:n
        pd = 1;
        for i = 2:n
- Z9 N+ v) W, w0 g4 I5 X( @            for j = 1:n
: y/ r3 G1 u; M4 Y! C+ v- J; v                if p(i) > p(j) + a(j,i)
+ O! k" O$ d$ ^; G5 c6 m                    p(i) = p(j) + a(j,i);
" Z% ~0 ~6 K1 E5 w                    s(i) = j;
' x) F( s8 m7 b' \                    pd = 0;
                end
% q" }6 D/ \3 l0 w3 M- }            end
8 s+ E! Z% W4 `; P- x$ }4 |% i        end
        %求最短路的Ford算法结束
        if pd
            break;
  X# H" Y% }) x0 p( @5 Y        end
    end
    %不存在vs到vt的最短路，算法终止，注意在求最小费用最大流时构造有向赋权图中不会含有负权回路，不会出现k = n
    if p(n) == Inf
        break;
    end
    %进入调整过程,dvt表示调整量
4 n3 {9 p/ h& W, q6 N$ F    dvt = Inf;
. H' v/ W$ H5 l+ N# q    dvtt = Inf;
* l3 v2 ~; [. g    t = n;
. ]3 `7 g4 J% x6 R& h4 G, l    while(1)
        if a(s(t),t) > 0
( @  W) S& ~* F& n1 Z( ^- L% q            %前向弧调整量
6 B  U- U  k4 r& g7 n  X3 V' u            dvtt = C(s(t),t)-f(s(t),t);
% U' N* l, y! ]! B- K% B6 i            %后向弧调整量
        elseif a(s(t),t) < 0
            dvtt = f(t,s(t));
+ K: `& V5 @8 C# C: |% t        end
        if dvt > dvtt
            dvt = dvtt;
        end
        %当t的标号为vs时，终止计算调整量
/ W% A  n- p/ u2 ~5 S- T5 u$ b0 }        if s(t) == 1
            break;
* K# G! ~& M% ]" f. S4 m        end
        %继续调整前一段弧上的流f
        t = s(t);
    end
    pd = 0;
. M% V( m7 K+ M  f( \1 C2 @& ]/ X    %如果最大流量大于或等于预定的流量值
% Z, ]' Y' `$ Z( [    if wf + dvt >= wf0
        dvt = wf0 - wf;
( W+ x9 u  @+ s        pd = 1;
    end
    t = n;
    %调整过程
  i& D% v  G2 S/ k    while(1)
8 s# {1 U0 y+ x  H1 a    if a(s(t),t) > 0
+ a. n  T7 O$ n5 A) V: K        %前向弧调整
0 e8 a4 j( B5 X        f(s(t),t) = f(s(t),t) + dvt;   
% q/ R/ a$ P8 W. l0 a    elseif a(s(t),t) < 0
        %后向弧调整
        f(t,s(t)) = f(t,s(t)) - dvt;
    end
    %当t的标号为vs时，终止调整过程
    if s(t) == 1
6 X! X, [! _( a. u        break;
9 \& ?$ X) h) U6 ?) \    end
& z* u" L% f. e    t = s(t);
+ u) ]$ |# {7 Q  ^4 j) @* V& \    end
    %如果最大流量达到预定的流量值
    if pd
        break;
    end
    %计算最大流量
0 }5 {# n6 W. Y, }; }    wf = 0;
    for j = 1:n
        wf = wf + f(1,j);
4 e' h) p$ o1 t2 T9 K' v9 j: e, i. Q    end
: _% s0 c) B* o0 Wend
%计算最小费用
zwf = 0;
for i = 1:n
2 _/ X# d5 j+ d9 Q! b    for j = 1:n
        zwf = zwf + b(i,j)*f(i,j);
( c# W! M/ w- Y8 i  E    end
* J0 [0 G& x& S* d0 c$ Nend
( q7 S, n& A+ w* Z%最小费用最大流
7 d. M; |$ Y  v, d- ]' G$ k* ^f
%最小费用最大流量
wf
9 K: @2 q# l1 w) H* ~) B" P8 S%显示最小费用
zwf
3 ]  y0 b3 r. e$ x# J( R1
  N) Z  z. p' C! x: e2
3
4
( q8 i2 z# c# J0 V5
& L2 P3 ~% \$ b$ t; f5 L% P' E* O6
7
8
& h" \  T) {: D3 Q5 E9
10
' J# L# u3 @8 j0 G: D0 F: |11
7 C# G; x5 V% h4 P' e4 w12
8 A; E$ K6 N6 S0 [6 f13
14
0 j6 u! d0 s9 G; }$ N7 x9 \3 \' U7 {15
16
17
18
% i, k8 p& W$ W$ y1 ]! ^( O! s19
20
/ h# M" j& Y. d+ L21
1 y' k  ]: ]! Q/ J0 s. k8 s& u22
23
24
& Y9 ?. M8 n. J$ x25
' ]2 [; ?! E! E; k26
27
+ |6 |6 g, {9 `) E, V# ]28
29
) D- w2 I' T3 z, w30
$ u( w. J" I( V! k1 P. l& q6 u31
32
% _& `( `+ \: q& p: @3 e33
) Q- H/ d2 u, l3 W34
35
36
( W" o8 T5 ~1 ^/ }37
38
( q9 r9 U2 a3 O7 ]$ j39
1 i. ^: X+ D1 M. k  @40
& X0 @+ K# V- c; l$ J" t41
42
; r2 u1 C# @# M* Z6 R% Z$ z43
44
4 C$ Q3 A5 j0 u! C8 q5 P6 x2 T7 P45
46
" }0 Y5 x: `+ B- j; ~9 I+ @47
48
49
50
' |0 x! K, G, d6 n5 t/ }' ~# f9 O51
3 r7 m0 M- J# P' \+ T% m52
53
54
55
% L3 l5 f0 S  j% Y) m1 c9 ^56
. V, J" _8 p3 [* I  b( F9 v57
58
59
0 f# k1 z* J) l60
9 k/ L9 X7 r- `( Q! Z0 b4 P' [; l$ F61
+ [3 K! c8 |$ ~- n7 x62
63
, }* q8 R. P# c. Q3 `$ n, M5 G7 ^64
65
% R' Y! U& o( }4 }( @+ E! f66
67
" Q0 Y3 m2 R8 Z3 C0 {, \68
# E2 Y4 h$ I8 X- n/ ?69
70
. ~' w# b7 H" W+ W7 H* U71
72
! o8 O% u. |. y( H  E73
9 o9 ?  V/ j: h74
: a. _6 j; U; I2 C# }- w75
( M: v2 x% I5 e$ l3 S0 @' ^76
77
78
79
2 p& q) Q! ]! a* E8 l80
( b5 ?* X' s/ T/ A81
82
' q3 ?$ ]5 o1 o2 A4 j; k83
84
85
$ t( c' n# x. \& Q+ E) N% J3 w0 L1 X86
87
88
5 e0 u2 I0 i8 x( F* q89
90
91
% g2 j% C- Z9 y  w3 }8 C% ~92
( A/ K+ e% s; O' I% O0 x7 a93
% s! V! r7 _! ]* i# s9 C94
/ P5 J' j4 r( f0 h95
* q; r) \/ p7 P9 A96
97
& v3 g8 \/ x  }* s0 ~0 L98
99
! P* I( S8 p; m. u& F4 e100
% x# }$ X% X  C/ W3 Q1 n101
, m) i$ M7 R! _! w102
" F4 H9 S% e) `) L1 H, [  x" i; O" u103
; p9 g0 V4 H. x, V0 i3 k104
105
106
107
% z) w( O% [" U' j9 g0 R108
109
110
111
& T5 P$ R$ U, X1 @2 w  f0 {112
113
- a9 N* ?8 K* o9 \- P' i6 E2 `3 f+ a114
115
116
117
118
119
120
# v3 ?4 g4 J8 h3 |121
122
123
124
125
6 W% c( V. F1 I7 e) |* R5 _126
127
128
9 U8 V& E$ r1 e6 @129
130
6 a" e& P; `1 {( f) Z131
132
133
/ L7 J+ v3 r" \7 g# G134
135
3 C+ J. Y. ~  [+ R$ D7 H/ ]* Q136
& U. x% Z! T. w0 N' Z3 N137
138
1 g3 F: `; {! q1 Z9 f139
140
匹配问题：

最大匹配：


- {5 w0 @# }, |3 D! L' S: a代码实现：

5 z% A) E% I7 b# K1 ?+ A) bm = 5;
n = 5;
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];
$ Z+ j7 z) h7 X! t- OM(m,n) = 0;
for i = 1:m
    for j = 1:n
+ N, W% m2 l( H7 x& d    %求初始匹配M
        if A(i,j)
            M(i,j) = 1;
            break;
        end
    end
    %仅含一条边的初始匹配M
5 @3 X3 n7 c" A1 H; ^( M/ F, t    if M(i,j)
        break;
7 S$ [/ D0 e/ C0 s" M5 {. I+ [5 {    end
- q/ n% C9 _0 s6 o# Uend

while (1)
    %记录X中点的标号和标记
; V+ m' O; I9 a) k7 P, f    for i = 1:m
3 h3 _( v" C. L. }9 x9 D: A+ s        x(i) = 0;
    end
    %记录Y中点的标号和标记
    for i = 1:n
        y(i) = 0;
% V3 U4 _& }4 k8 l    end
, j1 a: G( ~; ]: B6 z1 R/ G1 D3 F! r    %寻找X中M的所有非饱和点
    for i = 1:m
% {' X+ S6 H2 B7 }        pd = 1;
        for j = 1:n
& Z2 c/ j/ ?/ L: L+ V. c            if M(i,j)
$ ~" s. Y1 D9 T                pd = 0;
            end
4 p' g- Q4 ?. ^/ X        end
+ b0 y5 o4 |2 v- p' E9 P        if pd
# I6 O& a" U/ T1 R            x(i) = -n-1;
        end
    end
    pd = 0;
7 a& ]) I; [, D8 p9 O' ?1 a+ v    while(1)
        xi = 0;
        for i = 1:m
; s2 h% q! F; b            if x(i) < 0
                xi = i;
! A' i, A3 C$ \# r                break;
! m" M+ N' _! T1 F                end
( q, H: ]3 w0 t7 a1 g, b5 E            end
  I9 ]4 t7 a. z' ^2 k) J+ w3 k7 G            if(xi == 0)
                pd = 1;
9 w# m8 g: s7 z- Z# O; G7 w8 [                break;
            end
            x(xi) = x(xi)*(-1);
            k = 1;
3 p0 H, R, E5 y& @  u  G            for j = 1:n
                if A(xi,j)&&y(j)==0
                    y(j) = xi;
0 `. _  w* v, V+ E                    yy(k) = j;
                    k = k + 1;
                end
9 z- B* P& a! E7 ?% w6 p1 Y            end
            if k > 1
                k = k - 1;
" a: y; s; ^* ?/ z" d3 @3 n  [- N                for j = 1:k
) e" ]4 A- x/ |+ M4 S' _                    pdd = 1;
                    for i = 1:m
                        if M(i,yy(j))
% X, m2 q' O- t4 F( U* U6 x7 X                            x(i) = -yy(j);
                            pdd = 0;
- A) L5 Y7 \: M3 g& E                            break;
                        end
                    end
4 l) |% S/ I; [. l( n/ t* T                    if pdd
& B, c5 O) V$ t* F                        break;
2 r* q- |( i" O1 L                    end
% w% @  e" Q$ d  U1 d                end
                if pdd
                    k = 1;
8 n$ B3 {( D# M' s                    j = yy(j);
3 ~# _( g1 A9 [+ R. p/ K) q                    while(1)
                        P(k,2) = j;
7 A7 C# {+ P3 _                        P(k,1) = y(j);
                        j = abs(x(y(j)));
                        if j == n+1
) r) m* s4 y1 Q4 }' Z$ P                            break;
                        end
4 C1 S- p+ O: V! r2 {) |( D                        k = k+1;
                    end
                    for i = 1:k
) S0 U4 {# h; ?* }  s+ i                        if M(P(i,1),P(i,2))
                            M(P(i,1),P(i,2)) = 0;
4 ]+ Z: _/ J, V. H; \$ P                            else
                                M(P(i,1),P(i,2)) = 1;
                            end
# v/ u+ {: v3 e                        end
* T* ~2 b- f3 t$ S3 v4 P8 [                        break;
$ h8 X5 X3 V0 Y/ L7 J                    end
                end
& K6 F( L& W7 h2 A0 O+ g! n9 C            end
            if pd
, f( R5 C$ w% ~1 E, S& {+ T3 R                break;
9 c% k0 x) E5 t) v, K( L% c# t; ^            end
        end
1
* Z2 O' w8 m+ z+ `* k; C% q& e2 }2
3
4
5
6
7
  W3 T( Y2 t# r4 k" J: o) ?; ^& ?8
7 F0 I, d4 }8 Q8 Z, }8 _' ]9
- y' M4 M& s: A: a6 ~0 ^1 x10
7 @9 X5 |$ M6 _* M11
. ^& r4 Z1 b: z( U- @4 l8 ?12
13
14
15
; v( ^/ G) Y3 v16
4 S! C- F7 G  E: ^0 D: B; K; E+ j17
+ X9 A5 M5 L; c18
* i+ `- X% r8 P" r7 T19
% J$ H9 M& m; Y) _: z5 z3 ~; W20
$ }4 z& c4 [( ]1 @# m9 Y21
22
, i( i3 B5 }5 S  P# P& X# W23
24
$ _! k9 `; b9 x: W& q8 X25
. L" ~% o) q& h1 y26
27
28
29
2 t7 @! |/ W) K9 ?/ e30
3 l  d. z+ W0 T) N0 ^  ^6 o31
. M: X" t9 l) b32
33
34
35
8 a* W: o% L  M. Y3 x: D36
4 o& f  n8 F/ |# A( r37
38
39
0 h% H% ^- P' u6 Q40
41
42
$ z+ w% ]6 j( E, l0 ?4 F# s# G43
44
45
46
47
48
49
50
7 l) \4 D$ W2 }6 a51
52
53
54
55
56
6 o4 [- y# G2 v. k4 h57
4 e% i8 O! I- T* L9 x58
59
( r. t6 z' B9 ^60
' e% G" M9 z/ W# S6 @& |61
. Z6 ?. U' t7 J$ E- d4 D) i62
63
64
65
66
67
68
69
70
7 u- ?* y; p3 h/ [) [71
; I& D, L% a* l* j72
; ?; J9 u# W0 x- D& F73
  [  o; U+ Y1 n74
75
( M: d" q" o0 \2 D8 ^# C76
! V; \2 z$ P1 o, e1 M3 K77
78
79
$ G+ ^8 u3 S/ G6 V" H/ f" A  q, s8 a80
81
- c& u) G+ E) Q6 a82
83
  S8 `8 s3 V& k84
* u0 m: |. R$ V- W/ R85
3 Z6 E" y2 c8 d) p4 X& w- ^7 D86
( \2 T( G- Q  R. h87
88
4 B' j. q' W, r3 }3 W* X! n% L$ }% z89
, W6 W1 \7 i7 ?4 M; c. N90
91
92
/ t+ T' H6 K) o* ?93
94
95
1 @# o! w4 A+ }+ f; g96
97
- I' d6 a1 u7 Z( G98
) ~3 w2 P+ r  r) Z' v1 s. f7 |99
( r. k2 ~5 O  O100
' k5 k* Q$ z2 N. P( x9 q6 P) L2 I1 t  v101
102
103
$ G! b2 ~; P" _7 o1 K% Z9 J1 e最佳匹配

( q6 B; X; V* t1 B* |代码实现：

n = 4;
A = [4 5 5 1;2 2 4 6;4 2 3 3;5 0 2 1];
M(n,n) = 0;
" z+ h& y5 \" m* Ufor i = 1:n
    L(i,1) = 0;
4 c! w5 B( I1 v' P+ t% f    L(i,2) = 0;
end
%初始化可行点标记L
6 w& x3 a, f5 H7 ?4 lfor i = 1:n
2 D, z  s( i+ V$ C7 ]8 X    for j = 1:n
( v2 }, }  h/ b0 K        if L(i,1) < A(i,j)
            L(i,1) = A(i,j);
0 r* k1 u0 g! |5 u1 n        end
    end
/ ^: w" k- T2 A% N! q# A# e- oend
" I) X, C# |! {%生成子图Gl
' k+ U9 x+ c/ Z( I% Lfor i = 1:n
    for j = 1:n
! P6 [# z8 b6 M! y        if L(i,1) + L(j,2) == A(i,j)
            Gl(i,j) = 1;
  R/ a, M, ~9 `            else
3 L" ]/ Y0 R5 \' k0 _                Gl(i,j) = 0;
        end
    end
- e: W' c9 {; T6 k! q! xend
5 P3 x& Y5 B) h: `' Z%获得仅含Gl的一条边的初始匹配M
8 w+ G, r" p& w# J; a8 z3 Rii = 0;
# ?3 E( x; S3 ?2 i0 b' e: a0 U  _* Ujj = 0;
for i = 1:n
3 \5 a! Q1 S! }3 E( ]& }    for j = 1:n
: H$ {7 H: m% R& [& Q9 k        if Gl(i,j)
  t; Y, U% Z  K            ii = i;
            jj = j;
            break;
# \( @6 ^9 q/ l9 m9 N8 |        end
    end
    if(ii)
5 h' t4 O5 w  r5 j* c        break;
    end
; Z' T9 }$ U6 lend
M(ii,jj) = 1;
; ~% W0 u* B" Z. L0 r2 v( F" |1 rfor i = 1:n
    S(i) = 0;
) ^( H* o) ]  @' K) I    T(i) = 0;
    NIS(i) = 0;
end

' m- A$ @6 \0 O8 Z! |
( m) W) O$ P* a5 ~while (1)
    for i = 1:n
+ E$ ~0 p  Z! p- r& B+ D% Z5 ?9 M        k = 1;
        for j = 1:n
% J, i+ g( u6 {7 _0 O" {            if M(i,j)
                k = 0;
                break;
# }! {4 d/ E; P) x* G  W            end
        end
" Z3 |8 j7 J: ]/ `, D        if k
. @. a$ Z* J- l* R" H            break;
        end
2 F' n( @* ^  h3 `3 ]    end
+ M9 j2 ~( y" @# J. v%获得最佳匹配M,算法终止
. s& e7 U1 Q8 I    if k == 0
/ a4 v5 @$ H" `        break;
    end
# ]0 F: R* e; \- C! \8 C* e8 b

/ m* {. X8 G* A%S = {xi}
; [% |( b, M# c+ j: W0 P$ {/ bS(1) = i;
9 p  H/ ]0 G* b9 G* Q( i6 [jss = 1;
) h3 T) D2 j6 fjst = 0;
" f1 T) l6 L+ G( Bwhile(1)
, O, P, e6 V& L7 v    jsn = 0;
    %选择NL的值
# i3 [2 e/ B% `    for i = 1:jss
1 Q9 w$ [* n2 M3 e4 v9 k        for j = 1:n
            if Gl(S(i),j)
9 q" o  N) S, b, M1 l5 N                jsn = jsn + 1;
* i7 F! }& ~% @( R% t                NIS(jsn) = j;
7 S! y, u: H. L0 i* b+ a                for k = 1:jsn-1
                    if NIS(k) == j
                        jsn = jsn - 1;
( C- d- j1 S/ C$ `                    end
                end
- s% V* ?! m5 Z; g' F6 q            end
5 D9 y6 v# W1 f: n. @+ @6 [3 t        end
+ W6 C% {. C* b/ Y7 W    end
, B. Q9 ~( j) {    %判断NL(S) = T ?
    if jsn == jst
% l( w8 v. x. q        pd = 1;
9 a8 b# B* ]) ~1 s5 N        for j = 1:jsn
7 G. p+ e/ K" ]            if NIS(j) ~= T(j)
                pd = 0;
                break;
% o( q4 e8 Q% S            end
2 Z" f6 ]% y1 ~, ]        end
# z3 M* W7 N0 @    end
" N5 ^0 O+ ^$ a2 h. g    %如果NL(S) = T  计算al的值
    if (jsn == jst) && pd
        al = Inf;
        for i = 1:jss
            for j = 1:n
8 W0 e6 d3 X$ W3 r; r9 {                pd = 1;
6 s6 o0 Q% g( |1 O5 \                for k = 1:jst
                    if T(k) == j
# z6 U3 y8 K- D, b) W0 P3 c( o                        pd = 0;
                        break;
                    end
4 e7 o6 G: e) y" c. O& Z                end
                if pd && (al > L(S(i),1) + L(j,2) - A(S(i),j))
; W/ U  G5 K* t* J9 H7 t. D                    al = L(S(i),1) + L(j,2) - A(S(i),j);
                end
            end
$ {' K6 d% I% w  D        end
        %调整可行点标记
        for i = 1:jss
5 k; b, G/ J9 @            L(S(i),1) = L(S(i),1) - al;
7 l/ d/ p% t2 \& r! }        end
        %调整可行点标记
        for j = 1:jst
            L(T(j),2) = L(T(j),2) + al;
- D! E! Y& o+ @9 s! \# }0 \; z        end
        %生成子图Gl
        for i = 1:n
            for j = 1:n
) F. Q" T, x: I3 l4 r$ A7 @                if L(i,1) + L(j,2) == A(i,j)
2 U+ Z$ s( Z8 k& M( {; E, `                    Gl(i,j) = 1;
                    else
! ]" x8 x: x& Z+ ^' v# d4 ^                        Gl(i,j) = 0;
                end
                    M(i,j) = 0;
0 k7 y& t+ }6 C% f; w1 {                    k = 0;
  y3 o, ?" t- ?& G            end
        end
        %获得仅含Gl的一条边的初始匹配M
, t) O. w. u9 t* `7 n, C        ii = 0;
3 w* i  g: |+ e8 o2 J8 y        jj = 0;
7 T1 ~1 r) Z2 p& _+ f- ^        for i = 1:n
+ x2 v; b* l+ p1 b* F            for j = 1:n
  t" ^4 ~- M0 z  U2 f                if Gl(i,j)
                    ii = i;
  Y' D# N) l, p                    jj = j;
                    break;
5 S5 i, R* [$ H                end
# {3 v2 [/ s6 s( L3 w; H            end
" @- d: ^( b, E, T0 [0 t            if(ii)
1 \4 k8 y9 \/ L                break;
9 U9 [; r6 X6 ]3 N            end
( r1 a; G, `1 E; Q6 J        end
        M(ii,jj) = 1;
$ Z9 y% |. C7 e* y" S3 r* `) O        break;
        else
            for j = 1:jsn
                pd = 1;
                for k = 1:jst
                    if T(k) == NIS(j)
                        pd =0
! G0 c& ^0 S1 R+ W3 a                        break;
                    end
                end
# M2 i1 v  u( \" D. ]) f. J7 S5 f                if pd
                    jj = j;
$ n7 {8 p+ X( q                    break;
5 B$ N# e" N% @                end
            end
            %判断y是否是M的饱和点
            pd = 0;
: t) U, k3 y6 [# x+ I  h# f3 l            for i = 1:n
! L4 {! O( o& K                if M(i,NIS(jj))
                    pd = 1;
3 g& U8 _$ z* i( p  Q6 d) c                    ii = i;
. r/ Z9 ?% o2 x3 a; y                    break;
3 b. p- |5 V1 |' L                end
            end
            if pd
' C" D* X4 m4 Q( |  j  {                jss = jss + 1;
                S(jss) = ii;
: t  q: u* l* T; B2 U4 \                jst = jst + 1;
4 V6 O  t4 ]+ T; N                T(jst) = NIS(jj);
                else
4 R, ~9 D$ @- X; Z9 ^5 c3 g                    for k = 1:jst
                        M(S(k),T(k)) = 1;
                        M(S(k+1),T(k)) = 0;
                    end
: {/ o$ o  ^) g  `1 b# e2 D                    if jst == 0
4 j6 d  ~5 r, r: t! Y' i                        k = 0;
                    end
" Q# ^, `' R+ c+ a! g7 b                    M(S(k+1),NIS(jj)) = 1;
                    break;
2 Q% I. ^7 }/ U# f. y                end
/ E6 ?! k& @- T" D            end
- w; u1 I* I" ^* w9 G- U4 T% ^        end
2 S( W' T# f0 e- R* P, u    end
6 B+ @4 Z( o- B! l0 g    MaxZjpp = 0;
    for i = 1:n
        for j = 1:n
, k$ {9 i! `1 H1 i1 a            if M(i,j)
                MaxZjpp = MaxZjpp + A(i,j);
# A. \, E: w( e            end
1 O! ^8 K  C0 m0 S5 g        end
4 e: l2 h( m5 B8 \# j    end
    M
    MaxZjpp
, H7 F: N" @% Z/ z* Q4 d
8 Q8 @4 Q( s3 d$ q- Y

% |) l# o5 h1 v1 o" S9 ^