查看: 2464|回复: 0

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

字体大小: 正常放大

杨利霞

5273 主题	82 听众	17万积分

TA的每日心情

	开心 2021-8-11 17:59

签到天数: 17 天

[LV.4]偶尔看看III

网络挑战赛参赛者

自我介绍: 本人女，毕业于内蒙古科技大学，担任文职专业，毕业专业英语。

群组: 2018美赛大象算法课程

群组: 2018美赛护航培训课程

群组: 2019年数学中国站长建

群组: 2019年数据分析师课程

群组: 2018年大象老师国赛优

电梯直达

1^#

发表于 2018-10-30 11:25 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

最大流：

注意Matlab 中的最大流问题是必须是单源和单汇问题，因此这里需要构建虚拟的源点S和汇点G。
clc,clear
a = zeros(9,9);
a(1,[2:4]) = [20,20,100];
a(2,[5 6 8]) = [30,10,40];
a(3,[7 8]) = [10,50];
a(4,[5:8]) = [20,10,40,5];
a([5:8],9) = [20,20,60,20];
a = sparse(a);
[b,c] = graphmaxflow(a,1,9)

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

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

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)

最大流量为11

自定义Matlab代码：

最小费用求解- h( e3 @5 s) n4 u2 U
5 x1 q  J/ o( D, {8 H5 N3 R) G' o
Lingo:
; ?; o/ V2 x% ^; t4 N- e5 F0 I3 A4 Z* m
model:
! ?2 V. B( w3 Y$ Dsets:
, H+ Q- u9 e8 o7 Qnodes/s,1,2,3,t/:d;
0 F0 C$ @( Y0 |arcs(nodes,nodes)/s 1,s 2,1 3,1 t,2 1,2 3,3 t/:b,c,f;( E- V) d2 m, V) C0 \! F9 h
endsets+ F$ L  e, F% z7 \- j+ s. P- v
data:9 L9 ^3 c/ Y& m0 G) p! U
b = 4 1 6 1 2 3 2;. M% B1 D& c# C" g$ h
c = 10 8 2 7 5 10 4;
/ h# G9 Q3 C; a: M9 Yd = 11 0 0 0 -11;
6 Y" H: v# A; j$ b) E7 Yenddata
0 p* I: \/ i: {0 r- p: tn = @size(nodes);
8 Z. Y( _; t' G( Zmin = @sum(arcs:b*f);, X$ p7 J3 u) T% Y9 s4 `% ?
@for(nodes(i)sum(arcs(i,j):f(i,j))-@sum(arcs(j,i):f(j,i)) = d(i));5 ~: t7 h9 c) u3 u! F! S
@for(arcsbnd(0,f,c));& [$ G1 {. f9 d
end9 `; V: F# o0 V8 g1 t: [
1
5 c( M4 p& o1 G26 A0 R, y/ }% p( e9 y& F0 ?
3! d3 U" V) {% w3 o( w) W
4) C# ]  h+ D: i; s. W. [3 E
5
" v5 }6 F" N- E4 v7 ]7 d& ?6; K- \# o3 d! _: w# d3 P9 G5 r3 F
7
9 ~6 X, E" E- N7 K0 |* x. G+ g8
8 v' L! ?- W2 u8 I4 x3 }8 g$ q1 [3 i9
1 X$ x& x- P2 x/ \" f% @5 e10
$ i+ \# r8 T: ]4 G' V$ o" s11% A/ F( F2 r/ Z! E8 W" V- ^; H
12
* Q- s% X% J+ ?% Q; `137 R3 u6 U1 ~6 l, i5 n$ _+ ]
14
9 m$ |$ q! G9 F2 D) a153 W% M# I! i% D6 Y8 i% Q9 {
Matlab实现：
. k" r7 h6 J. ~* |
+ h3 H2 }9 p) K4 k2 ~5 r  b; o4 w: k+ O6 ^
n = 5;
; c- e0 d. }* s) T% E7 @%弧容量" y6 r- ]; P1 c6 @
a = zeros(5);
6 l# s  F2 `; c" s/ ha(1,[2 3]) = [10 8];9 c% m- A9 B7 I9 h' n+ _
a(2,[4,5]) = [2 7];# o& d$ a  ?4 ?; }5 g8 ]
a(3,[2 4]) = [5 10];
5 U# q( O$ `2 z+ ?0 W* h& Aa(4,5) = 4;# H+ i, k4 h( c7 K/ z+ F! U
C = a;
: H& m+ x# c% Z# U%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];8 m! d6 }6 K* Z2 n" s0 b
%弧上单元的费用
/ [. k& ?6 A( }* xa(1,[2 3]) = [4 1];
4 z  B7 q: y* _1 F( Aa(2,[4,5]) = [6 1];
( K; S/ n  q% [$ {7 n9 H( ba(3,[2 4]) = [2 3];" _5 I5 b" n" B% O
a(4,5) = 2;& X9 p7 E& U4 ^0 M8 T0 B; V1 o$ ~
b = a;
( T1 ^. U- R# G%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];/ U0 s9 a* Q/ }' Z* n5 t
%wf表示最大流量。wf0表示预定的流量值
! ]  `3 F% _% e% d0 Z8 ]3 mwf = 0;
9 t4 e, I9 {- B: F3 t% a" t! Iwf0 = Inf;
5 d) p- w8 z0 m, w+ H4 C( C%取初始可行流f为零流% H4 T  r  `4 A
for i = 1:n
  |' o( c0 s- U for j = 1:n
5 V3 n! ]1 _5 R; F8 b8 U       f(i,j) = 0;+ G# p4 x/ m* b' ?  s2 ]+ n
end
- a) ]; J5 S: E$ N8 C2 k  V3 L0 W$ hend
0 V3 F+ {/ w: ~; r9 ]1 v; N: `: y- dwhile (1)5 j6 P. f% q( Q2 _, J
%构造有向赋权图0 L& q$ I9 D7 r' {8 Q* E1 b6 f
for i = 1:n$ I3 H( b0 ?3 B5 K: u) G7 h
      for j = 1:n
7 J8 d: n/ H5 g; B          if j~=i. x6 W9 B8 n" _6 Z! ~! a4 _
            a(i,j) = Inf;7 ^+ v! v# A) Y6 t. j* c, h2 g
         end
1 x' R: I& t/ C9 l       end
+ S! o" u( T9 @3 Y+ ` end2 t  e2 w2 l  y& C6 i
for i = 1:n0 E& U9 Z/ g2 Q* a6 B+ U
      for j = 1:n) _8 o9 X" o% V8 T6 O+ W6 Q
         if C(i,j) > 0 && f(i,j) == 0# I3 |+ f9 S5 r! h% C& q
            a(i,j) = b(i,j);2 ?5 u( n6 P  J
         elseif C(i,j) > 0 && f(i,j) == C(i,j)
# y6 C: |! H2 g) x             a(j,i) = -b(i,j);: {. R3 z! `4 A; j( Z- P
         elseif C(i,j) > 0
4 S6 ]8 I) Y5 u+ ?( `( e1 ]# e: H* ~* h             a(i,j) = b(i,j);6 G; i" y2 ?9 [: r: r) q$ [. W
            a(j,i) = -b(i,j);
% T/ S( J/ ]) M* y3 i8 V6 _* C          end5 {7 I3 D! M5 T! O6 ^
      end# h* e' V% P/ g6 K
end8 M/ i' I0 G5 K* k$ L/ c8 o
%使用ford算法求最短路，赋初值0 w6 p6 v& D  b8 X! F  l! A7 c
for i = 2:n
) `( ^& m) c% h. ?; t) O: J% N9 T# K) Q       p(i) = Inf;
' D( V  K$ y( v# I* F8 R6 m       s(i) = i;
) H# N0 h8 [2 P5 ^ end
%求有向赋权图vs到vt的最短路,赋初值" [5 x1 }7 M$ C7 k# C1 m
for k = 1:n2 `1 K4 F1 J) {; l
      pd = 1;
1 M2 K6 ~) m8 G- Y: c       for i = 2:n
3 H- H' {  f$ W8 a5 m  t( O          for j = 1:n
, ]2 n1 w: Z* {, H. H1 X             if p(i) > p(j) + a(j,i)
) P* m: t2 [3 g                   p(i) = p(j) + a(j,i);2 q9 v( [3 b! p+ C
                  s(i) = j;
% \" k& G. l- t+ D' d9 m                   pd = 0;2 x, q, H- Z/ v5 \2 \
            end
# S  s3 Q) i% ^5 _, e& K          end
" i; L0 F. ]3 Z0 ~       end; C! N; h3 p1 C6 N4 C, G- {3 O9 q
      %求最短路的Ford算法结束
7 }  E% h! D0 \. H* |0 L0 e       if pd
8 N/ T! t2 t- C6 k5 w. E: F          break;8 v3 o" e8 S2 b- d+ x3 C9 }5 s' ~6 z
      end
9 l3 ^) O. _; h, F end- _% ~- a3 w  O3 y
%不存在vs到vt的最短路，算法终止，注意在求最小费用最大流时构造有向赋权图中不会含有负权回路，不会出现k = n
- J) n  p: Z5 |( m& @ if p(n) == Inf/ ]: v( y) j5 T, P  ~. g7 ^
      break;* S" u8 d" j5 y+ p$ x
end
& A: @* q( t( Z; b/ j0 O %进入调整过程,dvt表示调整量
' [2 t0 w3 G9 V dvt = Inf;" D* Q- B" o. w& \+ |# T/ m  z
dvtt = Inf;2 t8 R+ y3 W$ k) \- `5 d
t = n;
; P! R+ r9 D5 D; W while(1)
: v7 T  U4 y, ^       if a(s(t),t) > 0
1 n+ x3 l0 j7 F. I7 {+ I' ]5 p          %前向弧调整量
' G, ^2 C( K- e1 P          dvtt = C(s(t),t)-f(s(t),t);
7 z) `' Y) g% b          %后向弧调整量
! }0 ?0 |! S4 B0 g! w       elseif a(s(t),t) < 0
1 ^; |+ \) F6 U4 [. Y) D" Q          dvtt = f(t,s(t));* u( C2 f3 R4 i0 s# r4 i; v
      end
% B/ r& K( f9 H7 _( B# N7 Q       if dvt > dvtt
; ?. m5 D% a* F3 F& T          dvt = dvtt;
/ W2 O  l1 [9 w9 d. P4 Y       end
+ S# v! n; m/ S' N. f. Q) Q       %当t的标号为vs时，终止计算调整量
* V# l; f/ J  N8 Z7 N& U0 t- {       if s(t) == 16 ]& S! E+ ~' d3 i9 X3 {
         break;
3 Z; S% z7 \3 X* I) A       end9 l- Y( |# Z$ D  o& v
      %继续调整前一段弧上的流f
! b$ Y1 v  }  y6 c# n. j       t = s(t);9 b8 G9 k7 s9 `. \, u5 W! g; ]
end) ?( Y. I9 o! C" h- E* G
pd = 0;# D9 Z; ]6 l3 E8 u  |
%如果最大流量大于或等于预定的流量值# t& N+ i0 M( p* @# S1 o' d
if wf + dvt >= wf05 l8 G* r  Z# x2 L
      dvt = wf0 - wf;# ]5 T7 _" K8 i3 P4 i- E
      pd = 1;. s  R' v/ T/ |4 c8 X% n: m- F
end
$ s3 J$ P8 o3 i, M' F: x( G t = n;
" W4 d" s8 J0 i9 e; C %调整过程
7 d. J$ t1 F& y1 z7 w8 J) `+ v: ~ while(1)0 P6 c& k. L- l; W1 t+ D  Y7 R
if a(s(t),t) > 0  I' A- o* V& f3 u
      %前向弧调整9 }  h2 M% B! p4 b( U: {5 _* S' `
      f(s(t),t) = f(s(t),t) + dvt; # B0 o( |7 ]) }+ l
elseif a(s(t),t) < 0
. l( ^: u! Y: p2 m% r9 U       %后向弧调整
0 M( O$ C$ Q& p! E       f(t,s(t)) = f(t,s(t)) - dvt;1 G# S, o) d; B" g9 e
end 9 ^7 E( K# d' n! n
%当t的标号为vs时，终止调整过程
2 r7 D6 _# K/ p2 D; I5 f if s(t) == 1
: h0 F/ g; k9 A. [$ N$ S1 S+ K4 V       break;; a5 Q6 r8 |' w0 S! L
end
2 n( K5 E/ {/ \- g t = s(t);
( q1 R8 s9 u1 ]: s6 p end9 A9 {+ K4 `/ M# A* k: Z
%如果最大流量达到预定的流量值% f. e6 C" z9 b9 {7 W2 y
if pd( L; R) L' f, w" e( t
      break;
8 x; W, ^6 s+ H0 e end
2 U, o4 D7 t  @" }1 E5 T* J9 e! v+ i %计算最大流量8 q, f! i3 r6 k. i6 D
wf = 0;4 Q" q; K# G) T5 `+ K+ K5 P
for j = 1:n
0 @; L( b, z- |/ }) C0 S       wf = wf + f(1,j);3 r( c( p! `2 C
end
+ u  _4 g3 Y8 vend
5 e3 N2 J# }3 X. T4 P0 {$ u%计算最小费用
( `+ B! c7 s/ \; r2 d. m0 o5 Ozwf = 0;
; v! ]" F7 l) {% q' ?  efor i = 1:n% e& _( `5 {/ ]3 I
for j = 1:n
& L/ _! D$ F& \9 ~       zwf = zwf + b(i,j)*f(i,j);
- U: ~7 A$ M0 F2 [' e2 O( y end
& ^  v7 i) P; E( ^9 g7 ?+ F' ?: qend5 h4 Y" l" V1 a; j4 o
%最小费用最大流* ~) W- B2 f# E& g- z
f: W0 v. P( h  b" z  a( X( E4 V" \
%最小费用最大流量9 f' m8 n1 E4 }; I" x* s- j& o& |: B
wf5 o1 y/ E1 }& p" U% S' E
%显示最小费用
; v6 c7 k. ~8 J# M' Azwf
  H& ]6 D5 O! W9 Y- Y" V1
/ Q* z+ o7 Z& L2/ f) @7 \6 q2 D5 ?3 I9 \4 M! u
3: k2 B. z' h# z
40 x5 O8 |3 u8 l5 z
5
: F7 Q* ^# u% p) L8 _* S6$ \' r5 ^2 G7 y7 o
7
! {9 s2 k1 t; S7 j# ]" @: d1 U86 q7 t$ B( z) f6 I' X# i" b
9
! _- @2 P# }( K# x3 g4 d10) ?' K; e5 |4 h! F, @' O
11
0 G$ J3 c: T# Q" Q# P  h& [122 g8 n  Z4 q* [) n: d4 e
13( Z! d0 J# y; @
148 s# `* f; ^& l3 f0 A' A
157 c& m7 V5 k# b
16
& ?+ p3 R) r* s171 Q2 [6 {7 ~' J# r4 s5 r
18
% y& a  W5 U) K19
* S6 f) _8 `8 t: {206 R) N! s& @/ o% K3 T8 I; s4 h2 l
217 g1 O- A/ P! ~
22
% W- R# V/ m4 z! M$ Y0 S23- R  ]- N" X1 G( V; T! k5 E! b
24" W, w. ~0 v4 Z( o. j9 i7 I2 O
251 m' `1 K8 k1 g
26: [7 Z. E7 [! Q. V  n
275 G/ i. t- D  A
28' M% Y- z$ P% d, C8 S2 L
29
+ U* y& [$ O: K0 D4 G30
! z# \! O) \+ |8 x7 i( |31
4 g; Y" E5 ^1 [; R2 G32
) ]9 c2 P, F) \5 m* w4 Y+ h33* H7 E4 S/ ^! }8 U# |
34
, D& ~2 r$ @" [4 c" F35
) ?2 Q. j; A8 u$ W367 p, L0 M- p  I
37
1 P2 E8 u+ f; g0 }8 c381 K- U  ?9 |  \& G
39
% z1 o2 Q& u" U0 Q! }40/ e3 j$ ~" E3 W" {" g/ t
41( @  Q3 Y. ?) M3 _' E
42
/ L! ~- Z/ a0 G0 Z43
& e7 h( }$ {6 O0 m444 ~/ F: o+ S$ _" J' J' ]
45
" p  c# k; I& j. J, S2 i46/ S( }' d, o8 O8 e) g8 X
47+ ]3 N0 J/ w( \" B5 B* R. o* U& v; a
48" S7 d% X$ T" {) }0 }  \* P
49
/ X. E# D( N# L6 @# `4 e500 j# n) C$ `) C
510 `" Z- ?0 X3 k% y/ \
529 f6 p1 Y' B1 R/ B  z& R
535 r3 i. u+ j: Y9 F  z8 y
54
0 A/ m- `8 z1 w2 j553 l# s. s+ d% S9 n4 [
56
& \: n5 |; I  `2 V; G57& l: D6 }- y3 G/ W
58
% k) X' a2 c* _3 |: w59
+ K7 y" E6 t* j; h' m+ J60
0 i- ~8 Z- T% S5 L3 O* x61
& J6 {& x; {3 R7 e- W625 |0 N; z$ I* }5 N' Z
634 M" i8 C7 R' }3 c2 o
64
) Z6 _4 W# `' l# ?658 G( I2 D2 L. |  F" p; _/ Q% k$ E/ U9 v
66: f4 e; W8 u  ~) _$ I
67
, u% d1 f, Y3 C" `- x68; r) h; Y6 }8 m% Y1 L
69
8 ^! ]! d& M% V) s/ B70( z, `9 h$ c5 R% B
71
$ ?3 @5 F( O& f1 ^72
+ e6 z+ V! O% @: W2 u731 x& c4 c' ^0 @" H
747 `) z5 s, a* K( o- O% ]
75- S2 o# O  p! {  F
76
# x' k  t' q9 w) H  \5 g77# {, ^$ `$ p" j4 l# _+ \* ]- x$ S1 M
784 w% S; s5 i( i8 w
792 H7 J" [" m. _: m" |3 f
804 T0 r, t$ i/ Y; C+ e
81
6 j% }6 j: U+ ^+ E* Z% W82
' {! J% o* W; Z& T4 Z83. T  T- D4 {' R6 k. ]9 Y3 {/ `
84: P: {9 v9 }$ [! l' `1 F
85$ o# \4 v& x0 S
86
5 C' @. M3 k2 |5 K" W# P8 H874 i2 t" s/ F+ e
883 e4 p# |+ A% e2 E% Y' z
895 m& S" }4 I& C; K
90
+ o9 E/ o+ I. h1 c5 f91
" w! m/ ^; D9 k. `+ C$ J92/ q- ?+ U) |2 A" }  r- ^4 m
93) x+ L6 S- B0 M( y" j
94! i+ L6 ~9 x2 T. K4 d+ h, j% Z
950 y3 B2 G* M2 `. d- x
96/ z6 O+ {, N+ @( _8 k% n- C
97. H" D3 v# g/ }% x
984 n1 H7 y. Z# L; t3 G" f) s* X7 M
99; ^; O6 i0 d: Z& H$ E/ E! r) f
100
3 i" \9 p1 p- Q5 O! B101* Y9 d& O) ?) H7 C
102, L) t8 z8 c$ ~8 J9 d- f
103
9 r- S( p* y3 p# x  S5 D104
; O, F' t5 Y# |  z& P" b6 r2 R105, {( X1 f8 x% @! u& V/ P5 T' \7 x1 ?
106. W3 f5 v$ K% \; s
107# l$ h! A2 T# p# z" y  t
108
/ k1 T9 O: ~) w# [8 ]109
* j- O4 s1 k. F4 a1 y# S110
8 X) |( Y( Z, v0 x111
; h5 s. o7 ]( H8 Z1 q1126 f: h6 n/ F4 F
1131 I1 v- c' l. T7 W7 k4 e# K
1142 I# o9 M% _9 ~* I9 E3 [2 `
115& v( ]0 C# o, o
116
7 ~. g* `2 m  T+ h0 [- A117( x& q/ z* b% j' ]* V
118
& e& F: o! w: x- s4 {8 U119
% m1 z) D: u5 h  s* ~# Q! F1207 |1 O2 N) T5 \9 E& Z+ h
121
' j/ m, @5 b* ]+ h1225 |, k' [1 ]: @$ |8 Z
123
% Q$ o# P' i$ Z- D124$ r) \! p6 r/ e% F$ Z# G
125
7 _  O9 t9 h- `. t  s126
2 I9 t8 c* W) @2 K* x: R$ D127
  I& ?, E! G5 M! Q5 Q: N! I& o7 d' [128, N2 L  x/ ?' p- ]& e# u
1299 Y/ T) Q: A: k1 i% a: ^( q" {7 s: v) q
1305 B! u8 Z+ L. I
131
/ i7 h8 L( h  O5 ~' V132
+ r% s2 F- |/ Z1 V( `4 w9 Y% f& }! B133
3 W, q7 N5 D2 a: ~# }: o# @134$ F% A1 w$ z: Q4 B
135
3 e6 w5 P/ U" C. p136
* }& A! f. P& Y, X137
, w/ |% a; |' m" r' N138, I+ h4 b/ n; h8 e" S% O6 W
139
$ D- C8 |+ N2 Z" m6 {8 f140
: s% {7 t7 O$ A( C8 J匹配问题：/ D% O( \1 L& }5 ]2 |, f# I
' ?5 H2 Y" e' b  |
最大匹配：
: q7 f9 u- n+ z# X, p+ B; V3 v: I7 t3 C' K7 f/ \& v/ N

代码实现：

m = 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;
for i = 1:m
for j = 1:n
%求初始匹配M
      if A(i,j)
         M(i,j) = 1;
         break;
      end
end
%仅含一条边的初始匹配M
if M(i,j)
      break;
end
end

while (1)
%记录X中点的标号和标记
for i = 1:m
      x(i) = 0;
end
%记录Y中点的标号和标记
for i = 1:n
      y(i) = 0;
end
%寻找X中M的所有非饱和点
for i = 1:m
      pd = 1;
      for j = 1:n
         if M(i,j)
            pd = 0;
         end
      end
      if pd
         x(i) = -n-1;
      end
end
pd = 0;
while(1)
      xi = 0;
      for i = 1:m
         if x(i) < 0
            xi = i;
            break;
            end
         end
         if(xi == 0)
            pd = 1;
            break;
         end
         x(xi) = x(xi)*(-1);
         k = 1;
         for j = 1:n
            if A(xi,j)&&y(j)==0
                  y(j) = xi;
                  yy(k) = j;
                  k = k + 1;
            end
         end
         if 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
                  if pdd
                     break;
                  end
            end
            if pdd
                  k = 1;
                  j = yy(j);
                  while(1)
                     P(k,2) = j;
                     P(k,1) = y(j);
                     j = abs(x(y(j)));
                     if j == n+1
                        break;
                     end
                     k = k+1;
                  end
                  for i = 1:k
                     if M(P(i,1),P(i,2))
                        M(P(i,1),P(i,2)) = 0;
                        else
                              M(P(i,1),P(i,2)) = 1;
                        end
                     end
                     break;
                  end
            end
         end
         if pd
            break;
         end
      end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
最佳匹配

代码实现：

n = 4;
A = [4 5 5 1;2 2 4 6;4 2 3 3;5 0 2 1];
M(n,n) = 0;
for i = 1:n
L(i,1) = 0;
L(i,2) = 0;
end
%初始化可行点标记L
for i = 1:n
for j = 1:n
      if L(i,1) < A(i,j)
         L(i,1) = A(i,j);
      end
end
end
%生成子图Gl
for i = 1:n
for j = 1:n
      if L(i,1) + L(j,2) == A(i,j)
         Gl(i,j) = 1;
         else
            Gl(i,j) = 0;
      end
end
end
%获得仅含Gl的一条边的初始匹配M
ii = 0;
jj = 0;
for i = 1:n
for j = 1:n
      if Gl(i,j)
         ii = i;
         jj = j;
         break;
      end
end
if(ii)
      break;
end
end
M(ii,jj) = 1;
for i = 1:n
S(i) = 0;
T(i) = 0;
NIS(i) = 0;
end

while (1)
for i = 1:n
      k = 1;
      for j = 1:n
         if M(i,j)
            k = 0;
            break;
         end
      end
      if k
         break;
      end
end
%获得最佳匹配M,算法终止
if k == 0
      break;
end

%S = {xi}
S(1) = i;
jss = 1;
jst = 0;
while(1)
jsn = 0;
%选择NL的值
for i = 1:jss
      for j = 1:n
         if Gl(S(i),j)
            jsn = jsn + 1;
            NIS(jsn) = j;
            for k = 1:jsn-1
                  if NIS(k) == j
                     jsn = jsn - 1;
                  end
            end
         end
      end
end
%判断NL(S) = T ?
if jsn == jst
      pd = 1;
      for j = 1:jsn
         if NIS(j) ~= T(j)
            pd = 0;
            break;
         end
      end
end
%如果NL(S) = T  计算al的值
if (jsn == jst) && pd
      al = Inf;
      for i = 1:jss
         for j = 1:n
            pd = 1;
            for k = 1:jst
                  if T(k) == j
                     pd = 0;
                     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
         L(S(i),1) = L(S(i),1) - al;
      end
      %调整可行点标记
      for j = 1:jst
         L(T(j),2) = L(T(j),2) + al;
      end
      %生成子图Gl
      for i = 1:n
         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
      %获得仅含Gl的一条边的初始匹配M
      ii = 0;
      jj = 0;
      for i = 1:n
         for j = 1:n
            if Gl(i,j)
                  ii = i;
                  jj = j;
                  break;
            end
         end
         if(ii)
            break;
         end
      end
      M(ii,jj) = 1;
      break;
      else
         for j = 1:jsn
            pd = 1;
            for k = 1:jst
                  if T(k) == NIS(j)
                     pd =0
                     break;
                  end
            end
            if pd
                  jj = j;
                  break;
            end
         end
         %判断y是否是M的饱和点
         pd = 0;
         for i = 1:n
            if M(i,NIS(jj))
                  pd = 1;
                  ii = i;
                  break;
            end
         end
         if pd
            jss = jss + 1;
            S(jss) = ii;
            jst = jst + 1;
            T(jst) = NIS(jj);
            else
                  for k = 1:jst
                     M(S(k),T(k)) = 1;
                     M(S(k+1),T(k)) = 0;
                  end
                  if jst == 0
                     k = 0;
                  end
                  M(S(k+1),NIS(jj)) = 1;
                  break;
            end
         end
      end
end
MaxZjpp = 0;
for i = 1:n
      for j = 1:n
         if M(i,j)
            MaxZjpp = MaxZjpp + A(i,j);
         end
      end
end
M
MaxZjpp

zan