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

杨利霞

最大流：

注意Matlab 中的最大流问题是必须是单源和单汇问题，因此这里需要构建虚拟的源点S和汇点G。
2 Z7 x6 G3 j6 s! \/ Bclc,clear
a = zeros(9,9);
( ], v# [1 @5 Y. fa(1,[2:4]) = [20,20,100];
a(2,[5 6 8]) = [30,10,40];
9 }/ g9 V1 B/ x, P: K. V: h# Da(3,[7 8]) = [10,50];
a(4,[5:8]) = [20,10,40,5];
a([5:8],9) = [20,20,60,20];
8 N/ H1 i  ]0 L* da = sparse(a);
! P" e0 d6 [5 r[b,c] = graphmaxflow(a,1,9)

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

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

% g2 w) L" @9 d* X: j: e/ Yclc,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)
1 l) D1 w7 S8 u3 t

最大流量为11

自定义Matlab代码：

3 l  f0 Z  @, O& @) C/ ~
& A/ T; \" j5 z9 J( d最小费用求解
+ r. {2 j3 H1 h( B" m% o& A
Lingo:
. ]$ U, p% _9 W5 L' M  o  l
0 O" |" e4 u4 N. J+ A0 Y* r. d( Lmodel:
3 b/ a( ^7 h$ J8 z6 t' Psets:
' A* I* `- M7 \+ d# v9 T" @nodes/s,1,2,3,t/:d;
arcs(nodes,nodes)/s 1,s 2,1 3,1 t,2 1,2 3,3 t/:b,c,f;
, P" s' k& w9 v$ z' P' F+ X% eendsets
* `8 Z8 S& e+ ~0 {; adata:
; n! R, F; L# I3 ~! ?5 w) j0 pb = 4 1 6 1 2 3 2;
+ l0 ~# }( o2 i. ^c = 10 8 2 7 5 10 4;
d = 11 0 0 0 -11;
% \0 P+ b9 q! \! D# [! A; Genddata
7 y) U6 T: f" d3 R6 n4 _) e$ cn = @size(nodes);
5 m3 E3 u+ b: C, ]$ {/ D9 p. `min = @sum(arcs:b*f);
, |: m& q  y+ w- G0 n@for(nodes(i)sum(arcs(i,j):f(i,j))-@sum(arcs(j,i):f(j,i)) = d(i));
, c; y" |$ V0 \6 B! N- w5 o@for(arcsbnd(0,f,c));
, R& |: a9 B9 n. i3 X- u( j3 Uend
1 f4 g) \3 M8 U) b1
2
8 F9 V  A9 M+ H1 w- n8 ~. I" J/ l3
4 V" `9 N$ ~5 ~# Z4
5
6
7
& L; ?+ E3 R; Z: M  I  g8
$ n8 R; z+ G& e( A/ R  R9 \) P9
. d$ h$ b( L* |% ~3 g' c' ~0 o10
11
# z1 m0 c) w& r; K12
13
14
% b+ o4 y. [; E/ |5 @15
5 b9 w* T0 @4 k* vMatlab实现：
2 E$ w- _) A9 X  u4 Y# G

n = 5;
%弧容量
a = zeros(5);
a(1,[2 3]) = [10 8];
4 f8 N( m( O* T& Na(2,[4,5]) = [2 7];
* K/ Y, u+ R! P/ _a(3,[2 4]) = [5 10];
a(4,5) = 4;
C = 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];
3 I+ `* q2 `3 J4 i. Y$ k: J" y%弧上单元的费用
a(1,[2 3]) = [4 1];
; U+ T8 f- O9 j. Ha(2,[4,5]) = [6 1];
$ G( k( z7 I' P! Ga(3,[2 4]) = [2 3];
a(4,5) = 2;
b = a;
9 P. o8 f. x, F* S) T% 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表示预定的流量值
wf = 0;
6 ^/ w% \: c6 q1 P0 Y0 h: lwf0 = Inf;
%取初始可行流f为零流
9 G, i" i' a! `/ x* E7 @+ u, o0 {! dfor i = 1:n
/ f  p' G) B0 J    for j = 1:n
$ U6 f8 |# i6 |0 [( P; g  X        f(i,j) = 0;
; X% r+ `; Q' F* b+ o* R7 `( ^    end
; A: {1 q( J$ V) G7 Mend
while (1)
% o* X/ O/ e4 z8 |    %构造有向赋权图
    for i = 1:n
        for j = 1:n
            if j~=i
                a(i,j) = Inf;
2 Z) P' A% {3 L: K! }9 X            end
        end
    end
, }+ h! L/ D) p( ^0 z  w0 [    for i = 1:n
  E9 o9 K2 K* r) l- @' e+ r        for j = 1:n
            if C(i,j) > 0 && f(i,j) == 0
                a(i,j) = b(i,j);
            elseif C(i,j) > 0 && f(i,j) == C(i,j)
) _( v3 ~& K0 \. ?& \# {  d                a(j,i) = -b(i,j);
/ M0 _, L  l* C0 B* p; U% M" d            elseif C(i,j) > 0
                a(i,j) = b(i,j);
" e6 C1 T( c. N* d& |+ R# H                a(j,i) = -b(i,j);
6 b: l/ @8 x9 o8 y( V8 t! P            end
' q4 F6 u: G: f        end
    end
    %使用ford算法求最短路，赋初值
" Y1 u8 F6 `$ B' e# Z0 K    for i = 2:n
        p(i) = Inf;
$ |  ~: L* T' D& m        s(i) = i;
% T: }5 g* T, _1 \2 Z4 ?9 V    end
    %求有向赋权图vs到vt的最短路,赋初值
    for k = 1:n
% N8 b6 B3 P8 i4 U        pd = 1;
        for i = 2:n
            for j = 1:n
                if p(i) > p(j) + a(j,i)
5 ]/ k) |4 Q, U: `& w8 U                    p(i) = p(j) + a(j,i);
% ?& X: M4 I! _  T                    s(i) = j;
8 Z! |5 Z6 S% Q7 K7 R% j2 a7 ]                    pd = 0;
5 ], N) H) J% K                end
! f  F- `' T  g1 s+ B            end
2 a- o6 Q5 I7 h        end
" i6 N" D/ J" f1 d4 E5 }6 [( Z/ ]! x        %求最短路的Ford算法结束
; r/ n. K, c7 R+ W3 y        if pd
            break;
        end
" H3 |' O( o/ P" J    end
    %不存在vs到vt的最短路，算法终止，注意在求最小费用最大流时构造有向赋权图中不会含有负权回路，不会出现k = n
% |1 j3 G2 }1 p+ l    if p(n) == Inf
" M2 j% z9 w; b0 ^. y! X6 }* Y        break;
    end
: D' R& O* p* a. I' V    %进入调整过程,dvt表示调整量
    dvt = Inf;
    dvtt = Inf;
" J( ?) F- q* ^! u5 y% K    t = n;
    while(1)
        if a(s(t),t) > 0
: q/ u" \1 Y  p% e; G4 @, S" E8 M            %前向弧调整量
& m1 H2 Y/ A. U5 M4 W            dvtt = C(s(t),t)-f(s(t),t);
, s: ~# ~: U& }1 _            %后向弧调整量
/ V; s/ q5 S  o1 M; J' Z5 y( a        elseif a(s(t),t) < 0
            dvtt = f(t,s(t));
        end
2 a0 x9 u0 b( g* H5 r        if dvt > dvtt
& c4 b( a3 I' [* Q, Z; x6 H6 \2 p3 h1 Z& |            dvt = dvtt;
        end
. b3 ?2 }/ e' Q0 p        %当t的标号为vs时，终止计算调整量
3 o; y' V) y# N) g+ Y, H6 I& ?& P/ Y        if s(t) == 1
            break;
0 a8 S9 H& C: a  _, |        end
! X$ g4 o1 {9 V6 p0 R2 O0 P        %继续调整前一段弧上的流f
        t = s(t);
    end
    pd = 0;
    %如果最大流量大于或等于预定的流量值
7 I/ P/ g: G3 k  g( ]    if wf + dvt >= wf0
) c/ b: p, ~. w  \6 w7 f        dvt = wf0 - wf;
        pd = 1;
    end
. c8 W: v1 ?" |    t = n;
    %调整过程
7 v  N. w6 S5 u/ z' a0 \    while(1)
9 u2 j7 p! T6 A8 R    if a(s(t),t) > 0
* ?0 H/ R4 ~) x4 a        %前向弧调整
6 p% T& E7 V" J0 ?0 t8 c: X, M        f(s(t),t) = f(s(t),t) + dvt;   
    elseif a(s(t),t) < 0
  H) P$ |, I! C8 E1 `        %后向弧调整
        f(t,s(t)) = f(t,s(t)) - dvt;
( i$ x5 d8 b5 B. z/ a    end
    %当t的标号为vs时，终止调整过程
7 ]# f: g8 c$ ]! q* d5 Z    if s(t) == 1
        break;
    end
) |; t" T! W$ b$ z+ L# d    t = s(t);
    end
    %如果最大流量达到预定的流量值
) S" G. f7 G6 V" e# ?3 r" @  R    if pd
5 O1 N0 ~$ P1 q7 p0 O        break;
    end
- G) }# V  L7 {    %计算最大流量
    wf = 0;
, O- Q- ]8 _. O7 A- B: }    for j = 1:n
( u. d& L1 V( o( o        wf = wf + f(1,j);
- L9 V: Y- O$ T6 L& W- H! W    end
3 Q5 _6 l/ c/ g. B: u% cend
%计算最小费用
zwf = 0;
for i = 1:n
* d$ e( F- r7 j    for j = 1:n
  B9 B5 Y! C) `% N, J& u' e5 |        zwf = zwf + b(i,j)*f(i,j);
    end
end
. w" W$ a. \. z. a- B; u0 \1 Q' D%最小费用最大流
f
) G( O9 `% O0 m; W4 d, `8 \' D%最小费用最大流量
* s4 T, o1 B' K' Twf
& k/ l  Z+ D2 r# [%显示最小费用
7 H6 p* F. n. }. O. Y/ bzwf
- t, I; @8 }: S4 d1 V0 n1
2
3
. x8 M! L: h$ A9 U6 s9 A4
5
6
& x2 f: M. ^/ P0 h% i/ A  J2 J7
0 t+ ^6 s+ `& w/ W8 R3 N! j8
9
2 U; r- B* P# ]1 K- f3 Z8 W0 _10
11
12
% Y! X% l) }' u2 l( X13
/ P5 F' T2 N) ^2 [6 O6 V) \14
: o4 d) \. h8 b: K% |. u6 J15
16
4 D5 o4 _$ m3 R5 S$ I  \: z: }5 C17
18
, e2 {0 w# \" V5 A; M5 @# C/ `19
20
6 a. Y! U9 }& ?8 ~% Y( Z) _21
22
23
, {1 l. ^! X5 e9 C5 w1 u4 w8 q24
( X! _+ i+ d3 R25
26
2 c0 T# B" U" _; j' B! v27
28
& M, a% u( N% I& V29
6 y( e' \* S( h) n/ J' b30
31
32
% `' J# }% _) f% Y33
5 h) R6 c: Y+ n! Q34
3 X1 R' z. n: L- |35
36
37
  s# {/ F; L) D. W38
6 L& a: z, T' I: s) P3 W+ c39
40
4 X2 r* B+ [0 i' w- P. Q41
42
" A2 U% U( x1 `6 Z6 F43
) {! e- e( u: Q/ h' D44
45
46
47
) T  P, W, T. c48
49
! v( h: |/ P" L; Z50
* F1 e: h- {- z! ?6 W51
9 `: k# w/ Q' s! [* {8 q% C' O5 g52
/ }. T, G& s$ f: h6 M$ x  h- ?53
% c- K* G, @& m2 d$ k$ u54
8 {: ]' N+ B( e, R  P. Y55
% x2 p" b9 R% i  G* j: |56
' _: U6 ]" \. w; ~57
58
59
60
61
4 b& ]4 V6 l& {4 Y. n62
* x9 S8 ?7 x2 ?, e$ C" ^63
# W9 C) r6 D# H4 y% s( ^64
# }9 Q" `7 |% p- X. L65
66
67
68
69
70
  y6 f$ g" v4 r0 _9 _  Q# Y71
% T5 p# J: I) C# K, F# R6 r5 l: o# c72
73
74
75
+ a2 z$ y  ]3 W/ o: e( V# }% [76
7 S0 `4 L' k5 ~. I, R77
78
; g6 v6 F% H4 c79
4 [7 D1 Z8 {3 M# ?5 f9 N6 e80
81
) x* j! C% m9 ~1 B1 d3 T82
; u/ U# q2 a9 K83
- C( Q. Q2 t( E84
; }) C6 T' Z0 Q) `; o85
86
87
9 H/ Y4 i! c. m0 H4 z) C( v/ G$ D88
: ^/ D+ d# p. a, T' R89
90
0 [' o- K: v2 C( g) G% o% i91
: F+ N9 Y4 [' u3 L( N2 G92
93
' ?2 |/ X9 y; l4 P) v  ^94
4 [: `; _- o' q$ A* I: k95
96
& D+ Z3 `6 J, C7 y97
/ e. ^+ O9 p5 x6 A/ m98
: O% y' C! `$ G0 G, V9 z99
100
6 X% U) B! r' |101
) A7 |: H6 q* q# q% Y. j9 u6 E102
103
: v' B) b# B" l  R/ S8 v" O7 B104
105
106
107
108
109
110
111
# t5 T2 e) R: J& {- z0 d* I) o112
113
+ t( Y& f9 Q$ V3 G; M114
115
9 C( n' ~$ F, r4 ^116
117
118
8 R0 K4 D6 E" H% _9 b  r+ g* P119
3 e$ s6 J4 z# E, T0 `120
2 C: X( F4 B8 u$ |  w* x! L+ {2 ]121
122
123
124
# B' C+ b% [  m  W- r% \: p9 z! {125
126
127
128
8 j8 r, G  r: V& o5 ]. a8 h8 m129
130
131
" O+ j2 Z9 e' p132
133
: z% I8 Z2 r% ^2 K134
135
136
137
138
139
140
匹配问题：
$ ]5 Z/ `6 P  E6 |# A2 J7 O8 y
最大匹配：

- V& G( U, R  y7 O' J
' `! ?) [- N  u  W( B代码实现：

# G+ Y6 e4 g8 I+ Q+ Pm = 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];
M(m,n) = 0;
7 ~; o+ m/ d! o6 P$ }( nfor i = 1:m
) \0 W# C/ r4 f7 f    for j = 1:n
    %求初始匹配M
        if A(i,j)
            M(i,j) = 1;
6 [7 g$ F: S% f7 [: W            break;
        end
8 b. M" s9 |7 o$ _! n4 {' Y    end
. l4 p  K$ C: {6 D& M    %仅含一条边的初始匹配M
/ F. @) U4 X8 q4 U2 q+ E    if M(i,j)
        break;
    end
end
/ W7 n6 @- ~' ^9 k
while (1)
* s, i7 A: K  w: {2 ^1 V    %记录X中点的标号和标记
4 o4 I0 k6 i9 q+ u0 u    for i = 1:m
7 P; I3 T0 z7 o7 s* T1 w! K1 E) U+ ?        x(i) = 0;
    end
% N. l0 Q  |: F9 R    %记录Y中点的标号和标记
    for i = 1:n
2 w$ r3 ]# d7 D        y(i) = 0;
, M" w8 {: E& d- _    end
    %寻找X中M的所有非饱和点
$ S" B' G& C; S( R4 \  n    for i = 1:m
        pd = 1;
        for j = 1:n
            if M(i,j)
                pd = 0;
            end
: x% B# E* `5 i, b" a        end
        if pd
. V3 }* w% q1 E' a# }            x(i) = -n-1;
# E6 n% \5 l$ E# Y$ o' f3 ^        end
    end
    pd = 0;
    while(1)
; m. K$ H" l0 U, E7 I. I        xi = 0;
        for i = 1:m
            if x(i) < 0
                xi = i;
5 N7 G# a% x& `. n3 |5 f0 M                break;
4 Z9 h* x5 m! X( s9 b                end
            end
            if(xi == 0)
                pd = 1;
                break;
            end
            x(xi) = x(xi)*(-1);
            k = 1;
' \! \8 z4 V5 x& W+ h            for j = 1:n
                if A(xi,j)&&y(j)==0
                    y(j) = xi;
                    yy(k) = j;
1 Z, @& c3 D  ^0 \                    k = k + 1;
* `6 w9 j3 \7 Z  ?! N+ ~                end
. [. m! F( _# a3 |) q            end
6 y. q; W8 o0 v5 [" R+ S7 v            if k > 1
! Z) g" g! h: b0 B5 |  m& Q/ y                k = k - 1;
! T7 J, x" R4 B( a( x1 \6 x. J! c9 w                for j = 1:k
: x! \" X  I2 e' ^% a- \                    pdd = 1;
) l" u& h' @6 D, e  N0 n+ B                    for i = 1:m
3 t# {$ s) t% _1 e" W" g: Z) N                        if M(i,yy(j))
                            x(i) = -yy(j);
                            pdd = 0;
" K& {. z7 o5 l) n6 l$ G* s* A. A                            break;
. |3 [/ O2 t3 F                        end
                    end
* q: y* n# q' j: H; z                    if pdd
/ x6 ]& {4 j, L5 {# }                        break;
4 Z& Q1 O+ `/ ]: y$ I                    end
3 l+ N6 A( B# Q2 G7 x3 |. }                end
2 a  A* x: W6 u                if pdd
                    k = 1;
" E& ^5 f1 i0 P0 v8 n4 _                    j = yy(j);
                    while(1)
; x2 @+ g3 j* `# `                        P(k,2) = j;
9 }; A0 B$ y& i  p$ O% P$ `+ S+ `, o                        P(k,1) = y(j);
                        j = abs(x(y(j)));
                        if j == n+1
0 p; Q, E+ U  J" `. i+ B, e4 p                            break;
                        end
                        k = k+1;
, R  u  @4 V7 V' R$ r. j% Q                    end
( v- |$ H% ^- v& U) @$ c( ]$ a. `                    for i = 1:k
                        if M(P(i,1),P(i,2))
                            M(P(i,1),P(i,2)) = 0;
) `( R0 \0 o8 k8 k3 o7 j& X9 ~$ w) h                            else
                                M(P(i,1),P(i,2)) = 1;
                            end
                        end
                        break;
                    end
' C6 d8 O' l* K  ~5 `                end
7 @( {- c+ |' a9 m            end
            if pd
- q/ U$ D. D$ q+ {9 D2 f                break;
            end
        end
1
3 F8 X2 Y" L8 U0 r& I2
; \& E8 P' p' j* n( `+ T3
) q" P' c( ^4 B6 a; K) |5 g5 Y4
5
6
7
8
  }+ O) J/ Q4 L( D4 x, r9
10
11
12
0 t% _' X+ I% a' x1 M13
% r8 t4 Y: Y( J4 i  h9 A14
( e8 d; s0 b7 ?) d- d. M( Q15
16
17
" G6 c# ~/ V8 x$ W6 Y- a# n' R18
8 \/ c3 U& S- y/ _19
20
  F& b! |: I) c. ]: |/ d21
22
23
! R  i1 b. |6 l! p7 r% K24
25
% L  h% T8 M7 J* \0 s2 ^) j! x26
* g$ \; K% r1 _, ~$ [27
  y. N. U( d" p6 ?! h8 y28
29
( }. Q) w" n: ]1 m3 _30
31
32
33
; E+ W7 d. M4 W! ^' k34
3 _9 }1 R$ `* H! @, ^: a35
. A) j2 i1 `1 L% T; v36
37
" @8 I" s; K' C  O( I/ |2 Z38
1 ]7 d: r/ a3 A  T39
! Y5 Y3 \; ?, f0 p# z. e+ K40
) M$ o4 N1 s3 h41
42
: i+ I: k7 Y" j* T; G43
# @) c9 n  b+ `, D44
45
46
47
48
49
2 U: D% I$ B" X, R% g" {50
51
8 w6 y4 I3 k5 d1 x3 W) v52
53
54
6 ~) \, F1 H3 r* e+ a# `55
6 }3 x# z+ d* V$ s+ N56
/ m" F  C1 p0 C/ \8 W7 `! p57
58
4 i8 @) X$ G4 x59
- T( D; _7 X7 q* {" s2 u; q7 R8 o60
$ f3 l! y! t! P8 t61
62
63
64
65
: s+ g) Y6 t, T: V" i3 l66
67
" L2 o4 {  b- n68
69
70
6 Q' N  ^0 r1 ]71
72
73
74
75
76
6 A& \4 \7 P9 u, ]# Q  i77
78
. O# c) j  }$ E1 z6 I$ G79
5 x9 N. I7 r+ A7 f80
8 g( r3 u; p/ j2 `: ]81
82
83
' _( s5 F% B! H, t84
) d4 a- T5 t/ w6 g9 f4 H4 c85
) y; p% G. a+ A. {7 Q6 }86
' e6 J& k, Q7 M. w8 ?, C) ]7 L87
88
( l+ f  \, v) m: ~" H& U; u89
90
2 e$ E2 A$ O' j2 G+ b1 V) ^91
92
93
94
- Z% a+ m( L; E# e' c95
96
97
98
99
/ t+ b4 ~  o3 I$ v( H100
; W) k2 h  _7 M5 e$ Q" F( s101
102
103
% ?6 ^% |# ^0 S3 x/ h最佳匹配

# ?& G! x/ p; E$ f代码实现：
! X# f  `* ?) B9 |
8 f4 O3 m1 w4 n" an = 4;
* K' z+ c7 F1 E' i0 {A = [4 5 5 1;2 2 4 6;4 2 3 3;5 0 2 1];
- Q' ]9 `! m& B7 j% ^9 ]2 W; \9 IM(n,n) = 0;
for i = 1:n
8 n8 B: s/ o2 U% B; d- j/ q8 q) U    L(i,1) = 0;
    L(i,2) = 0;
7 G1 {* {# \* J+ B; Xend
. C9 ^- S; s% \4 H  k- `%初始化可行点标记L
% G) ?5 \- g# O0 N: yfor i = 1:n
    for j = 1:n
; H1 o0 ?' V$ |! j" _+ Z        if L(i,1) < A(i,j)
6 ?" f& o2 a  K5 Y8 X) |3 c1 ^: t# e            L(i,1) = A(i,j);
/ i, e& `/ a3 t6 ^8 I$ t& P        end
/ C( w6 _# b, E6 D  k8 \1 z    end
/ J2 H/ w4 C: z9 Dend
9 b5 i0 A3 v  T# w( k* Y2 G  E%生成子图Gl
for i = 1:n
! M9 ?% [$ W( S* y1 |    for j = 1:n
        if L(i,1) + L(j,2) == A(i,j)
            Gl(i,j) = 1;
! ~( ?% n& [0 S7 i) ^0 G            else
                Gl(i,j) = 0;
        end
    end
! ~3 U+ X# ?. W; z7 e# yend
, s$ I: b5 [& {  ^# `3 G/ J+ q%获得仅含Gl的一条边的初始匹配M
+ |9 {- v+ k6 Q4 A7 v: [$ }+ jii = 0;
jj = 0;
, g: k; ?0 O/ `: N$ kfor i = 1:n
    for j = 1:n
        if Gl(i,j)
! H+ j( a- ~/ d  P4 z/ T1 [$ U3 n            ii = i;
9 C9 ?! }: k/ j" u            jj = j;
            break;
  A' S2 L0 n+ n; x2 ]        end
    end
    if(ii)
        break;
8 c  I! @' h. N0 t+ z    end
, U8 @! L& d: }4 M2 nend
5 ?, J$ M/ M- uM(ii,jj) = 1;
& `. \3 u. b' f# f7 Pfor i = 1:n
    S(i) = 0;
$ o8 X( A; x9 ?1 f$ `+ G    T(i) = 0;
    NIS(i) = 0;
0 F% K# K# k) Z5 ]  _' o% C% |end


, {4 ~/ O' E- ]) O9 Lwhile (1)
    for i = 1:n
6 C# K3 L0 H: x8 W        k = 1;
        for j = 1:n
3 ]& S9 r3 w$ L0 O/ Y0 C            if M(i,j)
                k = 0;
                break;
. c7 M" i' h3 j            end
        end
) s: O: x% Z, r9 M: y( G! `, ~        if k
            break;
        end
8 o( u8 V  e! _" z& }$ v    end
  Z1 U$ b+ i* `( s/ A) a$ d%获得最佳匹配M,算法终止
4 m. }* P* G" d* R    if k == 0
        break;
! p5 l& }. {: G& Q0 q$ ^* N4 Y    end

1 `* f. t; w1 y8 Y$ }9 O# x; d
" N0 }: k$ ?! j( ~6 ?& a8 d%S = {xi}
S(1) = i;
$ l# w* b8 ~7 h) Y4 Bjss = 1;
) R/ [$ I/ w) V) ~; ?5 l; Ljst = 0;
% g) I  x: W; J0 Twhile(1)
    jsn = 0;
/ T7 R, n$ D' @7 G    %选择NL的值
3 M( t" _, M6 y0 x# W! R    for i = 1:jss
        for j = 1:n
) U7 p# X- p8 R0 W' N5 ^3 r            if Gl(S(i),j)
                jsn = jsn + 1;
9 P$ H6 [" b+ l2 ?6 \3 W                NIS(jsn) = j;
( T+ W5 W9 a  F  f6 E                for k = 1:jsn-1
# R5 T7 w, T6 }4 w7 G' _                    if NIS(k) == j
+ @1 k+ Z' X# ?' x: R/ O& _5 e                        jsn = jsn - 1;
                    end
                end
            end
+ }) T, A! H3 G! Z- c        end
) c, Z; u& ~  Q# _    end
    %判断NL(S) = T ?
    if jsn == jst
  G6 w) y4 C+ S9 E0 z3 w0 U        pd = 1;
7 J) a1 W8 n- j' w, ^3 X        for j = 1:jsn
/ C- `' D+ v3 o8 A7 J5 x            if NIS(j) ~= T(j)
                pd = 0;
, j* C' S: N5 g# ~" e6 w                break;
            end
$ u: {6 n# f, M( m+ h0 B' f        end
0 _$ \6 K7 d1 O    end
    %如果NL(S) = T  计算al的值
0 Q- m) N" X. P0 @( S    if (jsn == jst) && pd
& s6 r( D. M2 p8 z: f: |! b1 @* N        al = Inf;
        for i = 1:jss
            for j = 1:n
                pd = 1;
                for k = 1:jst
                    if T(k) == j
                        pd = 0;
. l! [$ G0 q. o+ f' m! [' O                        break;
                    end
                end
                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);
                end
            end
        end
        %调整可行点标记
        for i = 1:jss
7 L5 q& U1 S( x% M7 [4 x/ E            L(S(i),1) = L(S(i),1) - al;
        end
. _( h' S: l/ c0 g# Y# \        %调整可行点标记
; x: V) O; p# O7 v4 U& V1 f        for j = 1:jst
            L(T(j),2) = L(T(j),2) + al;
        end
        %生成子图Gl
        for i = 1:n
) J5 D' r7 s0 z5 z5 i* M5 v% W- p            for j = 1:n
0 D2 \: a; c% ~4 b  I                if L(i,1) + L(j,2) == A(i,j)
                    Gl(i,j) = 1;
* ~; {0 R3 r* g8 k                    else
& Y1 M% S" y! T0 I; t                        Gl(i,j) = 0;
9 l" p$ e5 E& c$ S7 }                end
                    M(i,j) = 0;
                    k = 0;
" L2 L. ?" x  ]            end
4 p1 J# V3 ?" \& Q! d, h- _        end
& y# ], D2 z% o1 S! z        %获得仅含Gl的一条边的初始匹配M
        ii = 0;
( M5 |" g; J+ f- V1 ?7 ^        jj = 0;
4 X1 M' o3 m+ _8 R: F; k3 ]3 `+ w        for i = 1:n
            for j = 1:n
                if Gl(i,j)
+ l9 H1 M5 u; {' s4 @" z; k% O                    ii = i;
                    jj = j;
  p2 E$ [2 t0 d2 t) \* u8 Q                    break;
# v" J4 [. c  }0 M9 j                end
            end
            if(ii)
                break;
            end
        end
; |1 b- J# o7 A1 O% q6 k        M(ii,jj) = 1;
        break;
        else
* s8 _6 q( c% k- K* K. k3 M# _, r            for j = 1:jsn
                pd = 1;
7 w/ F, Y5 o% L$ k                for k = 1:jst
                    if T(k) == NIS(j)
6 a' e" d8 `) ]0 }                        pd =0
7 y8 r' J% ~5 ]& o2 m. i& w                        break;
3 c6 [' v4 a! N) [5 y8 f                    end
                end
' u+ ^, T) y" _5 M0 a                if pd
                    jj = j;
                    break;
                end
7 w2 c* s6 Q  f9 K$ P1 B. G            end
( t+ C8 `& i0 a( v            %判断y是否是M的饱和点
            pd = 0;
. z3 o! M  L+ O2 T, G            for i = 1:n
, L* r. K8 p. z" A( ~- Y# I' `                if M(i,NIS(jj))
                    pd = 1;
# E) v7 p( \6 h  L8 ^                    ii = i;
3 ]6 z- M9 j; A7 z                    break;
: p6 D( j! B5 ^- x6 |, J                end
# J6 M; N4 B$ v5 m0 R/ t0 A            end
+ p  Q8 W; }+ u1 I            if pd
  p$ h; M9 ?# Q! @8 `' F                jss = jss + 1;
4 u- p" H' P- w: k# q& n                S(jss) = ii;
& g, B7 O& b+ M                jst = jst + 1;
                T(jst) = NIS(jj);
" p7 @# Z  y5 J" R) d% {  U                else
* k# e$ ^$ p/ P, J6 C) o- `  W9 m$ J                    for k = 1:jst
                        M(S(k),T(k)) = 1;
) R8 w" U' |2 }2 @+ V! N4 V" N                        M(S(k+1),T(k)) = 0;
                    end
5 G# T$ Y, `$ {' E5 q) [3 h% l                    if jst == 0
                        k = 0;
) f! m; y- H* L, k                    end
" n8 {0 f* l" o/ A                    M(S(k+1),NIS(jj)) = 1;
                    break;
) z8 h; |* n; n2 b  g& N. q                end
            end
! `$ R3 G, e/ k3 h) V        end
    end
    MaxZjpp = 0;
, j; {  f* g3 g( Q: a* |, Q) f0 B    for i = 1:n
' i6 U+ e0 |$ Z2 t1 T        for j = 1:n
/ {6 ]- ]+ T4 j5 A            if M(i,j)
- }( o  [) c9 e4 A; i5 G1 \                MaxZjpp = MaxZjpp + A(i,j);
; P- s6 W" @- K7 G3 W1 z! Y: }            end
        end
6 D% w( ?- a& c# H6 K    end
; X3 S+ ~' b2 B) G: e- r; d$ t3 w    M
' ~5 P3 P7 o5 h9 Q! j: c* q0 J    MaxZjpp
$ e5 w0 Q$ F) ~8 p1 H& j
: {; w5 X+ [% g& l6 G3 Z: a/ A
3 g+ P  x$ M5 ]" H
/ k* F8 t, ?7 \  m, V8 ~