查看: 2492|回复: 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代码：

最小费用求解
, a: q, l; A4 j% ^9 ~6 Y4 Z8 i" _# U1 [, P, p7 r5 t
Lingo:& m# J' i: [  M; e+ Y% {$ C* V

$ B: j7 d' b) T0 [$ Ymodel:
' N2 `/ U# X7 Y+ q0 k9 D  Rsets:% o. c0 |4 W, R$ Q! U  B
nodes/s,1,2,3,t/:d;+ p# S4 d* P3 _' ^; x
arcs(nodes,nodes)/s 1,s 2,1 3,1 t,2 1,2 3,3 t/:b,c,f;
" x& y1 z9 N" Tendsets
4 }. d, Y0 R. s( ndata:
; C5 c! w  z3 Hb = 4 1 6 1 2 3 2;0 F) ~$ v7 O3 i% N3 G% P
c = 10 8 2 7 5 10 4;
3 x, P+ K: i0 |4 ed = 11 0 0 0 -11;* k, }+ [8 F( q* y9 I
enddata
! B7 \6 e0 Z. [6 K* c7 Hn = @size(nodes);
$ L; s* p" b8 z+ y" d9 ]6 a- mmin = @sum(arcs:b*f);
+ k9 _$ O) Z9 T6 A3 t2 k@for(nodes(i)sum(arcs(i,j):f(i,j))-@sum(arcs(j,i):f(j,i)) = d(i));$ U. {/ O4 ~1 P: {$ \
@for(arcsbnd(0,f,c));4 s2 `) I9 l8 Y. {" m
end' P0 d, m& E* o5 T: ?$ {
1- ]& l- M4 }; c; S+ E) }  W* P* K
2: m8 Z* D7 {3 H3 V; r: R& U$ S
3
; A) |) s+ v3 H* z& C4
) B- J* L+ A( z7 a5
% e; S! w, n. D6
& j: A; J* Q/ |0 v7% d0 ?6 o2 f! U( G" t4 J
84 s" u4 C6 e4 a) [0 B* s3 n* {
9
  s8 S2 j, ]0 J6 B' f, w, w10
; D) a& D! v  x( K1 @110 B% ^4 i# O+ |) f
12) [: g6 p$ r' M4 x
13
0 o. b: q! e) P) z% D14
! L. P7 W! F1 c* j15
3 f1 F1 ]- \- C: t  d: j2 S; E# k- eMatlab实现：
+ @5 H) o( I; R* G! V. C% v; d7 q$ M+ I9 u- q
' Y8 k- f- Z" D1 G5 _) W% n+ m& T
n = 5;6 n4 g: q; h: M5 O* S' e
%弧容量  I$ F4 J. n5 z) I/ G
a = zeros(5);
* M1 A$ {1 |' Q) e' s. _a(1,[2 3]) = [10 8];
/ V; e# k+ L# J2 @' G! Wa(2,[4,5]) = [2 7];
2 R7 ]8 V. I  n: P( va(3,[2 4]) = [5 10];5 d; B  a' A. I. n
a(4,5) = 4;
" z4 i: j# w1 H7 l0 c9 \/ |1 A0 LC = a;4 U% X, d( C2 ~, o) B% M# c0 H
%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];4 `' U3 B3 @7 m
%弧上单元的费用) a' j( p* d' s( q$ e
a(1,[2 3]) = [4 1];% C- t4 [, X4 h. z& o$ R
a(2,[4,5]) = [6 1];5 ^# n1 Y2 l4 e0 B5 u
a(3,[2 4]) = [2 3];. `7 Q1 m1 `  G
a(4,5) = 2;2 Z" Z( y& Y& ]( X
b = a;
/ z. i" P( u) Q  J! {: X%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];
4 d8 d/ D4 ^2 K2 K% B/ c5 B2 V# C%wf表示最大流量。wf0表示预定的流量值5 n/ @) {/ V8 z1 V+ d4 A7 O0 S9 f5 r
wf = 0;
, k" g* h% K# @, S& fwf0 = Inf;. X6 @- R' e$ z: V9 F
%取初始可行流f为零流0 s& d0 Z% T# A' U" \: O5 y( F* J
for i = 1:n9 f/ W) }  Y) P' c
for j = 1:n
! r1 @4 L$ x; z( @0 C- s5 v       f(i,j) = 0;+ E7 I0 R: o3 I( Z: F% h; K( A: S: [
end
3 M- C( h2 _% P; `8 Q% xend
& p' R  H7 I  m+ F& N( l: ]  qwhile (1)) N; }2 m* M7 \2 o& {
%构造有向赋权图
# l) X* @- _( {9 _5 G" r3 v. Q2 G8 A for i = 1:n
" k: }7 [  E" f5 g1 \       for j = 1:n
, H2 n  E5 g6 ~2 r7 ~3 C          if j~=i
2 b! p+ l4 @4 \- t/ Q7 o* A             a(i,j) = Inf;
3 w0 r- g# @, D          end
/ g5 I7 F0 f" Q       end' }, f; L3 Y2 t4 I% S
end
1 G% O  Q+ {( j9 z1 m for i = 1:n
: s, H( @- v+ C# h7 z; x( m       for j = 1:n; x" W1 M$ T. N- P) f9 S5 t! D% G3 {
         if C(i,j) > 0 && f(i,j) == 0
: X% c8 B" w! w, y& O# J             a(i,j) = b(i,j);
; C/ A9 L( t* U8 n  _          elseif C(i,j) > 0 && f(i,j) == C(i,j)
: R& G  j! k( g             a(j,i) = -b(i,j);9 R5 O' v! ~5 @! c
         elseif C(i,j) > 0
* m9 H" c( h2 W/ H! w, V  L* r             a(i,j) = b(i,j);3 {0 s+ B7 i0 W: s* ]
            a(j,i) = -b(i,j);/ z: R+ {3 l, E! l4 m2 W
         end
8 u$ g- H9 U7 ^% U! S! G1 Y       end
/ t8 ]$ P' H$ Y, P1 e; ^5 Y end
$ M0 L+ E  g0 ` %使用ford算法求最短路，赋初值
for i = 2:n$ a, r( O3 t$ @5 x5 `, q& b
      p(i) = Inf;
; b! D* g+ y' q- D       s(i) = i;
+ H  ^' l" C3 \ end
/ Y" c3 S( ^' ^; A4 ]' p( ?8 O) n %求有向赋权图vs到vt的最短路,赋初值
$ h+ L$ Y) h: ~. W3 g3 L for k = 1:n  e. W( U7 e! ?1 m! {+ o$ }) S  U
      pd = 1;
7 I4 s% w! g6 i% w5 g% A       for i = 2:n
0 _' o4 W- ]) R1 L/ [0 X1 x* I          for j = 1:n3 E7 c" e& u& t# w! I
            if p(i) > p(j) + a(j,i)
0 G4 q! x/ q5 c% E! e) }                   p(i) = p(j) + a(j,i);" V8 F! k1 x' N( m% E# O8 M8 s8 z0 ?% I
                  s(i) = j;
. u3 Y' a- z- O: ?. O                   pd = 0;
1 C; |. b2 S4 Q) j# t: t( z4 O             end
7 N& s1 T) z$ |' {8 Z) A# G          end. w2 x& @2 K# |; r
      end4 q3 I, t7 C6 h: p
      %求最短路的Ford算法结束. c0 t0 r5 D5 ~3 y# h3 x# s
      if pd
+ [: t* p" m7 l( A" R& [! h7 W) ]3 H3 y          break;
3 }' C) b0 J# K; e0 x) h       end# Y% s4 o- v7 }5 h  r
end; R$ z% v: m, ]7 }/ W. K) Q5 @
%不存在vs到vt的最短路，算法终止，注意在求最小费用最大流时构造有向赋权图中不会含有负权回路，不会出现k = n
% G! [% R2 t9 Z0 R) n; P if p(n) == Inf, E/ [; y5 E" h9 j6 l
      break;) z# O6 A, ^) f7 z) {
end/ L; V' ?" j: @- {
%进入调整过程,dvt表示调整量3 t6 w3 v" L6 M, H9 F2 u3 u% B
dvt = Inf;
; g- o6 a0 d4 L' a) f dvtt = Inf;4 N$ V4 w6 l9 K) R& t  b
t = n;
. Q& n1 n1 U- U while(1)
% S3 A% M  Q* n! g# ]& E$ \       if a(s(t),t) > 02 N5 f8 J! N; ]
         %前向弧调整量
: }! Z2 A# K4 _9 k. Z          dvtt = C(s(t),t)-f(s(t),t);
& M; A3 \6 [. j' }          %后向弧调整量! S# r' v8 `% ]6 U
      elseif a(s(t),t) < 0/ ~+ \8 p- m& ?0 D$ Z. ]2 D
         dvtt = f(t,s(t));  ?* C; g8 x+ v$ _1 e/ H4 L/ F6 b
      end
- A5 ]3 D5 V1 v6 C  J       if dvt > dvtt0 u" r; E4 V2 i
         dvt = dvtt;
9 H4 H3 ~9 T- N; `. R       end
, {" a3 w8 N  j7 C# p       %当t的标号为vs时，终止计算调整量; q, w0 W* D) c9 b3 B  f% N
      if s(t) == 1
0 K4 Y4 b: \* W, x$ ]# g7 n          break;* ?  ?5 k; W5 o' B1 F1 _; U3 j/ C
      end
& q7 x9 C; N% }5 x       %继续调整前一段弧上的流f
2 N2 [& h) w7 d, C       t = s(t);. [" Y6 d# F% a) L
end
/ O+ Q" k; L1 @- T0 i3 K" f, e pd = 0;
+ \9 |& B2 ^( M' u" K0 w; W3 { %如果最大流量大于或等于预定的流量值
0 D9 Z7 g9 W# I, p  Y+ {0 M* P if wf + dvt >= wf0
) X  e5 \5 M( A$ i$ F       dvt = wf0 - wf;+ |4 J+ J# G; d# r
      pd = 1;* ~# k5 u9 X6 h+ ?6 E4 s% k
end: P, u6 I9 g0 u# G
t = n;6 ^, J# K! H. l
%调整过程9 F" g! C- s: p; Y4 y7 _0 T. W
while(1)' j8 H* V) v. x1 l4 B' K
if a(s(t),t) > 09 B# V6 u7 f7 l. X; B# u( ~% O( n
      %前向弧调整0 h1 S" ]/ ^6 C% F. R4 t, w
      f(s(t),t) = f(s(t),t) + dvt; 9 B  K1 V! d7 T2 ?2 O
elseif a(s(t),t) < 0
, ?5 P% D$ N, ?       %后向弧调整; T$ l# B; D; Z# _' B1 K
      f(t,s(t)) = f(t,s(t)) - dvt;
. G: y8 _: e7 Q. P end : v6 w5 L; I9 x2 `* x3 `5 y+ o0 \
%当t的标号为vs时，终止调整过程* y) B  e2 I2 m  I5 g
if s(t) == 1
) u- ?7 F9 i2 ?' q. G% L& B% t       break;
2 i# b- L% M/ [ end) k  v" P5 o' x7 S4 X6 e& v
t = s(t);( a* N' k. G& `  w3 E& d8 E& X
end! B; }  y: z; k; y
%如果最大流量达到预定的流量值
: o% f/ ?6 Y% c: U if pd& p7 a- j- ^; G$ x7 X0 T
      break;0 _1 _, T' ^, F; e7 X5 z  c
end5 w5 K4 N8 n, Q8 `
%计算最大流量
; f0 w0 I8 x; U& c! S wf = 0;
0 F2 p. G# V+ E) e- y for j = 1:n
( V  |/ t% {, d- s& O4 j       wf = wf + f(1,j);
0 `  ?2 ]1 R" C4 u( J6 n end
, O6 I! U' w& x# {9 F; Lend+ k* j" a. h2 Y* d1 i
%计算最小费用5 e4 J3 K( `% c
zwf = 0;
$ ]; n! U' t4 A( efor i = 1:n
" V7 e* o5 M5 e$ K/ e0 y  ? for j = 1:n  R. _: d+ n  b
      zwf = zwf + b(i,j)*f(i,j);
2 G3 G0 g1 t. r& v& b6 R end
' C% ~- N, z" i, {' X7 O6 M$ T8 S; Oend4 K% b4 j5 ]$ ]8 P$ u5 z
%最小费用最大流
: s5 A6 @- m8 g4 y  d1 k# o: gf
' s# c9 L6 \9 r% b1 ~- {. p7 N%最小费用最大流量6 }$ ]8 @! d4 x/ @! a1 b- D* M
wf
- I! W( S1 R1 x4 S, s3 k%显示最小费用- l- e$ q( A* a1 ?% y
zwf( R; s2 M5 n1 `
1/ J, r/ N! h1 ^. r
2  T' v0 y& F  c$ B/ Z% e; z) Y
3- i8 U; w6 A# U; H5 a+ V
4
7 i8 N, O9 F- i2 ]3 m- ?59 p+ c; c7 Y8 G) |% y8 G$ M4 l
6/ C8 E3 x2 r8 o7 z2 a
7
( s* g5 `) |- A) [8) X2 q) r( Z! K. z
9
7 }* f+ a0 B9 `. K/ I! q10. U2 _+ Y2 Y+ V1 Z7 l
115 m3 _1 j4 P9 i. R8 }" P4 l2 E
12
- A. A- H. s( x+ E13
( u1 v& ?- I; v5 V' W) @6 A14
) @  m8 \9 p, ?) U( A0 m, q15, H; a4 b2 X; d2 ~
16
17
3 T1 L6 }' ^. Y" z181 D" }, ~* v/ b  r9 v
19# ^8 h; V+ g* O3 ]
20
& R( \' p: k3 S; o21
3 O" Y% w0 Q# A6 ]# n: y& g22
0 y: z) P3 n& s( m6 _) k5 T2 R  i23
' Q4 }6 S, J; p. V  F! ?24
  F$ c3 w9 W, @7 f) v8 p$ E. n7 E251 n# h1 |7 B$ [$ c
26
+ h( U( e- q) O, E; Y2 y27! y3 s4 s: _. x' J) `' a- m
28
/ H; Q% ~1 B' c% z  V29
4 E& y3 F* W4 @0 H4 K4 ?30
5 P7 Z4 d/ g" x  t31
4 e8 T. K3 k" l9 R9 [1 R7 Q! s* u32
+ p0 a  E- ?' T5 F33
2 g4 n- d. _9 a1 ~34
$ z' S: G/ `1 R9 R- Y3 j35* _% _; z5 l% m- O2 d/ J+ R: Z
365 _$ B) w1 _1 \9 E
37
% z1 ~) h$ x2 f' ?2 r385 T1 j& M; w; ]: p& Y0 r
39% e6 ]9 R$ o) b
40
3 y7 O: m; s) x41
4 C+ o1 U8 L0 O. s+ [42& I8 b6 A( f. X0 H9 r" l4 O; v
434 ]6 Z3 s6 S* H% N% v# p. g
44& x. l, b, f7 b
45) V: b4 g3 }1 d1 Z  o
46+ {- I* S4 O! X0 ?  I
47# l9 k6 Y% ?" y% B+ k& Z, |
48! c6 o0 `" I' @! g6 z/ r! p& N  L4 R* |
49
- M% Y! L/ L; _4 q) c2 [509 q. L" W8 R$ e0 Q
51! \+ ~; M% t) ?2 x
52- {2 |) I) }% y( {; p  y$ K% ~0 a6 v
53
0 e/ ?+ m, ]* R# X- X7 h54: G4 J5 p3 J) I
55) i6 g5 Y6 _1 O
56+ _# r: |" w  m6 H+ e4 {
57# S8 F% H+ i0 D2 r$ V5 H5 [9 V
58
6 y* i) x& C% a- {) v: `6 |59/ D/ `" D. e! |# F6 ^3 b3 d/ ?
60
: B# |8 ]4 y' G. k% u. T7 M61; s- [/ t$ e) Y1 @, R& J/ ^/ u  {
62
/ z. n- x2 t% \+ ]5 d0 G3 j& m630 N: ]3 N+ b3 ^  U' w9 G
64
* [6 d, {7 H/ f. E3 l' y: n5 M65  p' }2 h1 g4 X3 z( A0 U& }/ ?1 X' K$ G
665 q: t- ?6 y' d0 H
67; |: I9 s6 C7 q# q5 t
68; E& y4 s; L$ `' w
69
5 |: k0 Z* f% p- B' N' j4 u! Q0 n4 ?70
: X1 Y( a4 `. K& T8 p! X71
3 r8 k9 Z- u+ l3 y6 P72
/ f. H/ T6 w6 b' N& u7 |: G& p73
3 g7 \0 y7 y1 ?5 A6 N74* \; b& c" ^. _9 X# |; _
75
! Q1 q+ |- ]: j! |1 h, W& W& S2 o76' {2 Y; T: v% R$ R+ X
77
" O. K$ T" a. O6 U! V4 j784 n8 l/ `3 O% W; ?+ [: Y
79, f* Y. k* v9 R6 E9 Q9 C
80
4 [! o# T( Q5 c$ j; K* r81( K9 D2 w0 O4 w1 \% M" ~: Z
82) [) \7 Z: W; |; a
83
8 d' W; m2 z$ O; \* D# e+ D" S84
2 c  c+ Q0 h  Y2 I1 T, \& Z85) k2 ?$ H- V/ Z9 i
862 S4 O: j( {! n) r$ W1 c8 ~) O
87. H5 _- d3 X. p) G( x' [
882 c6 t& ]! [5 J- D- D
89
1 E3 s# M4 k3 N  U$ _4 w3 P1 o908 F% Y! p! I  \8 p/ q! C# m# I
91
4 _- A: }# M2 [6 c$ x925 s  r3 ]8 ]% j! N
93
" _. X+ v! P7 u# L9 b' {94
' `! N7 `. m; [) y% q95- @- @4 [+ i- C! v9 T3 E# Q
96
' R, A9 M% r/ N& k- Z: B972 d* M& X, R0 B  d) |  }' p# ?* D, h
98
! z$ V; s/ k+ c* ^5 _9 `( Q9 e991 e! |  }: W: l2 H
100
8 H% |4 K0 V5 `3 S& t$ A101
/ }& [7 j0 E: ?102
$ O* f; E9 O! Z# p9 u$ A103
, h0 b, @7 A9 M1 X+ u104" Z# o- |4 }  O  i3 `2 D6 \
105% f+ h, k+ b# |! w8 ~
106
1 h* e( A7 u2 p7 I, w1076 p4 s) c! e6 t; b0 t1 X+ h
108% y! X0 R; D& _* P! \- F3 b8 ]
109
) D" F) k; S3 \1 a1 W110
; z4 F" G! i5 h1115 v4 l6 z. k* L( v
112) V4 E: w1 ]0 J8 Z, Q
113
% B/ v" ?3 O! V  B! q# j114. w& G( D$ h* h: W( Y
115
6 ~% O! }+ t% H9 b+ U. [116+ W9 J! N6 Q+ p3 @/ A
117
8 M" Z. ?; q7 j+ B& `- c118, d* }# j' y, N& [
119
. g# }0 U" c: J1200 E6 w7 U) P+ I* D1 n0 c. ?+ B
121
4 ]9 }( U" L! K. y. |- m122+ I+ [+ E6 E7 Y- I8 E
1234 Y. G4 q) S: Q4 I5 K/ b; Z" z
124
+ b1 H8 O# S7 Z. f" C125* E! q; e" A0 P7 m6 g  _: f: y& }
1261 z1 U% g3 O  F( y+ W
127
+ Q, D& G7 e$ V% `( O1284 ]6 D; \( [; I9 T6 i" G# x7 _+ Z
1292 n+ m) G- n0 P5 ]. I
130
& t# K7 m/ u2 {131
/ W; n$ ~3 Q! B: d9 B6 B132& C6 C9 t; s- A: X' v5 n. h( u
133& Y1 ^5 M( w2 E4 O! S. h: |
1341 `2 o7 A! D4 ]# i4 q) s3 {
1352 B( R$ M: {; d: m
1360 p5 B. j9 D' ~( u
137
3 {% q( b3 b2 y" _138" h) w$ u% R5 J5 _7 Y3 K2 g' r% J8 W
139  k' B1 a- H" \" C1 \
140
( R! S3 H& L& _7 C6 Z! @$ ?匹配问题：7 c- \. ]% a, [

5 T  w2 F, O7 G8 P" c最大匹配：8 Z0 X# n0 f. r
+ R* b4 J% s5 ~" |, l

代码实现：

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