个人写的运输问题算法，还望指教

plgatc

<>/*************************************************************************
                         表上作业法解运输问题        

& [# b: x0 q  F0 e- |! a8 ^$ {6 G 编程环境：VC++6.0     
9 _1 Q/ d. d% M' h" g8 D" @% r1 F 程序说明：
Vogel法求初始解，位势法检验是否最优，递归搜索闭回路改进解。
! p0 u" f7 k6 s1 j# q *************************************************************************/
#include &lt;stdio.h&gt;
2 g! ]' _  B2 R& F#include &lt;stdlib.h&gt;</P>
' Z! T% \, x  p+ t/ Y7 l% r<>#define MAX 100
#define M 999999</P>
<>int status; //1唯一最优解，-1无穷多最优解</P>
$ }( E' S0 w: x4 y<>int num_a,num_b;
double a[MAX],b[MAX],temp_a[MAX],temp_b[MAX];
double u[MAX],v[MAX],pu[MAX],pv[MAX];
2 l$ g6 Y! s2 n9 E, Hdouble ab[MAX][MAX],temp_ab[MAX][MAX];
8 d$ o* W  \, Q, _double base[MAX][MAX];
int pbase[MAX][MAX];
, M8 z, ?. _  J$ y/ {  ^struct element {
int r;
& \) v& W7 \& f* w" F int c;
double value;
};
( B  P6 i& j' P0 Nenum direction {mid,up,down,left,right};</P>
" r$ [2 p% U  I5 f/ o- ~<>void create();
void banner();
. }. N/ M- T. {& j/ g5 j) v/ }double dabs(double d);
' W7 C$ K/ i' ~- a7 M$ gvoid findinit();
void computeuv();
5 v9 D$ k( K  lint check();
8 M1 X% }' r! }& y; B$ g& dint  circle(enum direction dir,struct element cir[],int *t);
void improve();
% W; D# @0 K1 g" z1 lvoid output();</P>
<>void main() {
banner();
create();
printf("\n按回车确认后开始求解");
getchar();
getchar();
, N7 p& |6 |! H% B findinit();
improve();
3 u2 p/ y% O) l; y switch(status) {
case 1:
  output();
  puts("\n原问题有唯一最优解。\n");
9 V& W; s+ a% }5 ?  puts("\n按回车结束");
  getchar();
  exit(0);
  C% W' {- i5 s) k case -1:
  output();
  puts("\n原问题有无穷多最优解。\n");
  puts("\n按回车结束");
  getchar();
  exit(0);
6 r, U2 a' y1 }* v1 x0 C }
}</P>
<>void banner() {
) o$ O  z! E7 N% K" q printf("\t\t****************************************\n");
printf("\t\t         表上作业法解运输问题\n");
, O, ]! ^) H# R" K. Y, T6 a% T printf("\t\t                              Thunder\n");
' S' S: O+ n/ T1 g printf("\t\t****************************************\n");
0 |1 G1 B1 i& w  L printf("\n");
) Q, s+ {. O. ^. y& j}</P>
, s' H( c% d0 r5 j9 o0 m<>void create() {
. b  I; _" S) _0 Y int i,j;
double sum_a,sum_b;
& h5 J. {: T3 U( w: G: I2 p. R char confirm;
while(1) {
  printf("请输入产地个数：");
  scanf("%d",&amp;num_a);
- R0 x2 U0 N/ ?2 l5 g. i  for(i=1;i&lt;=num_a;i++) {
6 j5 |" g! }; U  u   printf("A%d产量：",i);
. o+ I# V  h1 j   scanf("%lf",&amp;a);
  }
, e. \9 `" v" [) ]4 l* G6 ~  for(i=1;i&lt;=num_a;i++) printf("A%d产量：%lg\t",i,a);
  printf("\n正确吗？：(y/n)");
  getchar();
/ n" n; t* a) Z& d) I' U  confirm=getchar();
( P  `; |/ `2 A+ Y5 ~5 D  if (confirm=='y') break;
& i' o) n, W9 I- T; ?8 d! t8 J  else if(confirm=='n') continue;
, m1 p) U6 Z  R2 o }
while(1) {
" d2 m/ v, L  f9 L3 }9 _  printf("\n请输入销地个数：");
  scanf("%d",&amp;num_b);
5 n0 H4 _& \( J) I- ?# O3 H0 S  for(i=1;i&lt;=num_b;i++) {
   printf("B%d销量：",i);
/ G1 |# ?. }( q6 @8 c   scanf("%lf",&amp;b);
' l$ B  E" _. R3 f  }
, D( l; u2 w( Q( l( C0 R9 a  for(i=1;i&lt;=num_b;i++) printf("B%d销量：%lg\t",i,b);
0 \4 S0 L% V* a* n) }# d: X3 l  printf("\n正确吗？：(y/n)");
* X5 a" \. f, O, J  getchar();
  confirm=getchar();
  if (confirm=='y') break;
8 b! r1 F: o# {* w9 z, L, y  else if(confirm=='n') continue;
6 Y) B/ E6 J7 Z6 e# h3 s7 Z' n/ a }
putchar('\n');
for(i=1;i&lt;=num_a;i++) {
  for(j=1;j&lt;=num_b;j++) {
$ m3 ]2 ~$ c: [/ g   printf("A%d到B%d运价：",i,j);
4 |# V3 D' g: i4 N" l8 i+ A   scanf("%lf",&amp;ab[j]);
  }
  for(j=1;j&lt;=num_b;j++) printf("A%d到B%d：%lg\t",i,j,ab[j]);
+ J) N+ W! H, `6 {: ?* j& Y  printf("\n正确吗？：(y/n)");
  getchar();
: F. q6 F3 U* x  j+ B$ {, K$ I( Y* Q  confirm=getchar();
; ~4 l3 p# q3 X+ v7 D  if(confirm=='n') i--;
1 D- V7 \9 M5 J! `8 C" Q8 E  putchar('\n');
" r- a5 m7 ~6 z. g( R5 `/ y }
/ [' s3 G1 U* b  M2 ? //处理产销不平衡的情况
5 b  n: ?8 N) `+ Z  [; V& K sum_a=sum_b=0;
for(i=1;i&lt;=num_a;i++) sum_a+=a;
4 p$ D. g+ I, l0 c  T$ @ for(i=1;i&lt;=num_b;i++) sum_b+=b;</P>
<> printf("总产量：%lg\t总销量：%lg",sum_a,sum_b);
if(sum_a==sum_b) printf("\t产销平衡。");
else if(sum_a&gt;sum_b) {
2 o: N) p; r/ n/ @8 J' R1 K  printf("\t供大于求，增加假想销地B%d。\n",++num_b);
( E+ y" i1 Y6 Q0 C9 x: p! G  b[num_b]=sum_a-sum_b;
  l" }) ^$ J5 M% N' |% I! }! m4 C  for(i=1;i&lt;=num_a;i++) ab[num_b]=0;
}
6 |% w! X$ m, B  O3 m4 L2 J else if(sum_a&lt;sum_b){
  printf("\t供不应求，增加假想产地A%d。\n",++num_a);
  a[num_a]=sum_b-sum_a;
) v' w2 Q9 C/ D7 k  for(i=1;i&lt;=num_b;i++) ab[num_a]=0;
# B3 M+ Q- k3 u0 z, L8 d' h+ k }
//求解前的准备
for(i=1;i&lt;=num_a;i++)
! u" F9 C8 D1 C* Y7 V  for(j=1;j&lt;=num_b;j++)
, T& l, ?& ?- `% |+ ?: Y& r; [4 R. }   base[j]=pbase[j]=0;
for(i=1;i&lt;=num_a;i++) temp_a=a;
for(i=1;i&lt;=num_b;i++) temp_b=b;
% k7 p* v( ]. m  ] for(i=1;i&lt;=num_a;i++)
+ i/ w. k5 R+ {3 p) |% c for(j=1;j&lt;=num_b;j++) temp_ab[j]=ab[j];
//回显问题
printf("\n\n原问题为：\n\n");
   printf("产量：\n ");
* R; o# S) B* u9 I for(i=1;i&lt;=num_a;i++) printf("A%d:%lg\t",i,a);
printf("\n运量：\n ");
for(i=1;i&lt;=num_b;i++) printf("B%d:%lg\t",i,b);
printf("\n运价为：\n");
for(i=1;i&lt;=num_a;i++) {
  putchar(' ');
% X6 o3 A. e/ q  U: h7 O9 a- J  {  for(j=1;j&lt;=num_b;j++)
3 m; T8 t/ H/ c) b# ^   printf("A%d-&gt;B%d:%lg\t",i,j,ab[j]);
. S& |1 ?/ M' B4 k' g" {& v9 v  putchar('\n');
5 {, r( B6 x. V/ @* h }
}</P>
<>double dabs(double d) {
* X5 f; j1 q7 g- }" G if(d&gt;=0) return d;
/ y0 T' M- ^% k# J8 j- S  I: T6 _ else return -d;
}</P>
3 P( j# m0 v. s9 i7 Y2 g6 ]<>void findinit() {
+ E$ `8 _1 S: ^+ L$ b int i,j,k;
, E7 l6 @$ B' l* a double r_penum[MAX],c_penum[MAX];
8 r5 ?+ O' D/ H+ W/ M+ H4 @) g struct largest {
5 ~7 ^0 c% B9 `. b* \3 ~0 R% Y  char rc;
( X/ |' q8 J2 Y- y$ _, w  int num;
0 A2 \" i$ @/ N  T- k8 m* x! s  double value;
};
struct largest lar1,lar2;
) w. L" C; [4 |, Y8 L. D! a int r=0,c=0;
double a1,a2,b1,b2,temp;</P>
<> for(i=1;i&lt;=num_a;i++) {
' ?: b2 {+ U6 ^( n2 V6 V  temp=temp_ab[1];
$ N4 Y, @' W$ u  W: p3 u# z" E  for(j=1;j&lt;=num_b;j++)
- V* R7 V" C/ x" D' U$ Q$ A% y   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
! u$ D* w% U0 n4 E  a1=a2=temp;
* m$ C3 n6 L% _/ l  P  for(j=1;j&lt;=num_b;j++)
   if(temp_ab[j]&lt;=a1) {
7 B. R) `. M, G' N    a2=a1;
    a1=temp_ab[j];
2 d$ S5 m& ^$ Z. a) ?2 V: I: J   }
   else if(temp_ab[j]&lt;=a2) a2=temp_ab[j];
* I' n. T1 g, G5 T% e9 l  r_penum=dabs(a1-a2);
}</P>
2 T8 v! \( \% Y- \<> for(i=1;i&lt;=num_b;i++) {
  temp=temp_ab[1];
  for(j=1;j&lt;=num_a;j++)
   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
& I3 S8 n4 |5 s8 [: L3 T  b1=b2=temp;
  for(j=1;j&lt;=num_a;j++)  
   if(temp_ab[j]&lt;=b1) {
( |! G* e( P2 S1 D' j& R1 ], H    b2=b1;
    b1=temp_ab[j];
4 ]! m& W$ o/ O  ?) i   }
7 R% C/ \. ^! v# c  T/ P/ T1 h   else if(temp_ab[j]&lt;=b2) b2=temp_ab[j];
  c_penum=dabs(b1-b2);
( @  X. M/ S8 D: N }
+ l0 |& s; ]5 u6 i& @% i- W, A  T /*
9 U0 N" g* i; [% ~4 N( Y# n8 j for(i=1;i&lt;=num_a;i++) printf("pa%d=%lg ",i,r_penum);
! ^& s/ K7 G7 E putchar('\n');
) S' u# H" R9 o% _" @ for(i=1;i&lt;=num_b;i++) printf("pb%d=%lg ",i,c_penum);
0 F; ?! u% ^  s! g- j- X0 z */
; ]3 F6 Y4 ?3 b temp=r_penum[1];
for(i=1;i&lt;=num_a;i++) if(r_penum&lt;temp) temp=r_penum;
) @1 S$ q, M  f5 l7 P. e for(i=1;i&lt;=num_b;i++) if(c_penum&lt;temp) temp=c_penum;</P>
<> //考虑了有两个罚数相等的情况，大于两个相等只取其中两个进行比较
lar1.value=lar2.value=temp;
lar1.num=lar2.num=1;
lar1.rc=lar2.rc='r';
, {1 u" ^2 D" W for(i=1;i&lt;=num_a;i++)
  if(r_penum&gt;=lar1.value) {
3 J5 ?0 k) @# w' Y1 R1 H% Y   lar2=lar1;
5 U! i3 S8 m- z( g& `5 p   lar1.rc='r';
   lar1.num=i;
   lar1.value=r_penum;
  }
% l4 N* W6 B7 b; H  else if(r_penum&gt;=lar2.value) {
* W, o" c; \8 o   lar2.rc='r';
" ~- N: R- E/ M# k$ ~   lar2.num=i;
6 Z" [9 A5 r' v$ v/ T1 a' r   lar2.value=r_penum;
! A* e# X3 R+ s" ?' l  }</P>
' W1 C. D& v3 s<> for(i=1;i&lt;=num_b;i++)
6 \. t6 A# \; |6 c9 J  if(c_penum&gt;=lar1.value) {
& ?. d: L$ J' a   lar2=lar1;
' c# F' \. p& s   lar1.rc='c';
/ q7 o1 r' M( T% s! r/ u   lar1.num=i;
   lar1.value=c_penum;
! }- A) k5 ]$ E4 O) Z  }
9 F2 S7 t2 E! q" e6 X; j" d, C( O" G  else if(c_penum&gt;=lar2.value) {
   lar2.rc='c';
7 @, n  R1 v$ S- o6 H   lar2.num=i;
- c- g* v2 W& j   lar2.value=c_penum;
4 k9 O( p: I( ^8 m# d* `$ O& _  }</P>
<> if(lar1.value==lar2.value&amp;&amp;(lar1.num!=lar2.num||lar1.rc!=lar2.rc)) {
  if(lar1.rc=='r'&amp;&amp;lar2.rc=='r') {
   temp=temp_ab[lar1.num][1];
   r=lar1.num;
( O  h  a1 p$ B      c=1;
   for(i=1;i&lt;=num_b;i++) {
+ G# O, R) T+ C# Q/ K5 ^9 s    if(temp_ab[lar1.num]&lt;temp) {
     temp=temp_ab[lar1.num];
     r=lar1.num;
2 m% e# C) O( e) e" U     c=i;
; N# l) Z' y: M6 Z7 ^7 W    }
    if(temp_ab[lar2.num]&lt;temp) {
5 V! Y5 l- k* E/ |1 o' M6 J     temp=temp_ab[lar2.num];
     r=lar2.num;
     c=i;
    }
   }
2 d; x$ W8 ?. S/ v  }
' o% S& \9 x( @: _9 G9 [. d4 d" ^  if(lar1.rc=='c'&amp;&amp;lar2.rc=='c') {
: D1 _$ |- [( ]  q# z! `$ |# x   temp=temp_ab[1][lar1.num];
   r=1;
- Y- j* q% e/ N. Q' l- t7 T      c=lar1.num;
$ d! j0 J/ v% [. U! z   for(i=1;i&lt;=num_a-1;i++) {
    if(temp_ab[lar1.num]&lt;temp) {
4 E' Z2 S* r8 M" C; |! A8 A     temp=temp_ab[lar1.num];
     c=lar1.num;
- ]& u" b1 w. v2 V     r=i;
2 M8 p* H1 }3 `1 Q1 x    }
    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
4 f6 {$ ?: y# G: `% r     c=lar2.num;
     r=i;
& S- V6 i- [' A* W5 ~    }
+ T$ m4 c3 I6 `8 d   }
  }
  if(lar1.rc=='r'&amp;&amp;lar2.rc=='c') {
   temp=temp_ab[lar1.num][1];
   r=lar1.num;
      c=1;
# N8 |$ S3 b3 n% a   for(i=1;i&lt;=num_b;i++)
% l! _( N. d& a3 x2 B    if(temp_ab[lar1.num]&lt;temp) {
7 D5 n/ G* s4 q- V5 Z8 g# S& ?     temp=temp_ab[lar1.num];
     r=lar1.num;
     c=i;
( r% w( R* h; d( P! u    }
   for(i=1;i&lt;=num_a;i++)
' Y2 c2 u: w9 U8 K    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
     c=lar2.num;
" @/ e: L9 v4 k6 E1 y% E     r=i;
    }
' \* E- F* M! r  }
# {5 _+ p/ ~, p, i8 q8 H  S3 B! O& v  if(lar1.rc=='c'&amp;&amp;lar2.rc=='r') {
   temp=temp_ab[1][lar1.num];
5 `5 i; r+ u/ K( n- o   r=1;
      c=lar1.num;
   for(i=1;i&lt;=num_b;i++)
    if(temp_ab[lar2.num]&lt;temp) {
7 ~0 h7 h6 N8 J     temp=temp_ab[lar2.num];
+ m4 M$ h7 j! f" p! h  P     r=lar2.num;
     c=i;
2 g6 v* g9 S  P    }
8 O3 J0 \1 L/ N   for(i=1;i&lt;=num_a;i++)
" `. R( C: _: E  @, O* }! ]9 v1 z    if(temp_ab[lar1.num]&lt;temp) {
     temp=temp_ab[lar1.num];
; g8 P6 j( R* l! H0 w% n! G) z     c=lar1.num;
9 k- J# |& [  X4 Z, L* ^0 o3 T     r=i;
; Y- m  {: ^: ?: T" l) `    }
  }
}
4 L4 \  P; y' E; n9 s0 X else {
. X7 Q: b' U3 A5 L  if(lar1.rc=='r') {
   r=lar1.num;
   c=1;
   temp=temp_ab[lar1.num][1];
   for(i=1;i&lt;=num_b;i++)
) x3 x. ~* Q7 E+ D    if(temp_ab[lar1.num]&lt;temp) {
; c2 J# j6 H& y' Y) p2 ?3 q7 l# W5 B     c=i;
     temp=temp_ab[lar1.num];
9 w8 E+ |4 G; ]    }
% K+ N. U. n0 h3 ^+ t0 _1 g7 f, ?; n  }
0 z; J6 ^+ {( |# e& M. L  else {
& `. _0 i% w9 v/ t+ V, B9 {$ k  K   r=1;
   c=lar1.num;
: W  H5 w( l& G* F- y' ?$ `   temp=temp_ab[1][lar1.num];
; n2 ?6 f/ I; @: G   for(i=1;i&lt;=num_a;i++)
7 ^# O+ E1 [* G! Z/ ~) ^6 O  a    if(temp_ab[lar1.num]&lt;temp) {
     r=i;
1 }9 v6 n5 O$ q     temp=temp_ab[lar1.num];
    }
  }
# y5 |+ i/ s1 a- z+ k }
- d$ {% H# o7 `( a. t pbase[r][c]=1;
" l/ i6 A- D9 l% M$ o" a- {& P if(temp_a[r]&gt;temp_b[c]) {
  base[r][c]=temp_b[c];
- U% X( R& L1 D- `  temp_a[r]=temp_a[r]-temp_b[c];
  temp_b[c]=0;
  for(i=1;i&lt;=num_a;i++) temp_ab[c]=M;
- K3 `3 ?8 N' U' V9 i. t5 K }
else if(temp_a[r]&lt;temp_b[c]) {
  base[r][c]=temp_a[r];
2 ?% i' Q- F6 a& [1 s. |3 t  temp_b[c]=temp_b[c]-temp_a[r];
  temp_a[r]=0;
- @6 m6 t+ A, }: f9 C5 Y7 W  for(i=1;i&lt;=num_b;i++) temp_ab[r]=M;
}
4 F- Q, N  v$ t# t else if(temp_a[r]==temp_b[c]) {
0 _1 A/ f4 i% z/ z/ G1 k8 t  base[r][c]=temp_a[r];
) T/ v/ k- d7 {' J4 j% @$ L- F4 o- B  temp_a[r]=temp_b[c]=0;
4 k8 t! S% M) Z+ |) N& _  for(i=1;i&lt;=num_a;i++) temp_ab[c]=M;
& q0 i% L$ B0 ]) f7 I& r- X9 `, G/ f  for(i=1;i&lt;=num_b;i++) temp_ab[r]=M;
  k=0;
  for(i=1;i&lt;=num_a;i++) if(temp_a!=0) k=1;
1 k0 n% B: J8 ^6 o$ D8 F  for(i=1;i&lt;=num_b;i++) if(temp_b!=0) k=1;
  if(k!=0) {
   k=0;
. T/ m4 i& M* x   for(i=1;i&lt;=num_a;i++) if(pbase[c]!=1) {k=1;break;}
  L( m2 P( Q+ [9 f   for(j=1;j&lt;=num_b;j++) if(pbase[r][j]!=1) {k=2;break;}
. q0 x& g. k; M' z/ C! j# C   if(k==1) pbase[c]=1;
   else if(k==2) pbase[r][j]=1;
  }
( m  q/ N) Y  s' t) g" M }
k=0;
5 v/ O5 N; K% t! x  `! u for(i=1;i&lt;=num_a;i++) if(temp_a!=0) k=1;
& U& s, ?" B$ p$ M0 B for(i=1;i&lt;=num_b;i++) if(temp_b!=0) k=1;
if(k==0) return;
findinit();
}</P>
<>void computeuv() {
3 O2 q. d5 L3 M2 i/ w1 ?4 d int i,j,k;
for(i=1;i&lt;=num_a;i++)
  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==1) {
6 g8 f5 [9 R$ |    if(pu==1) {v[j]=ab[j]-u; pv[j]=1;}
    if(pv[j]==1) {u=ab[j]-v[j]; pu=1;}
( J+ J9 z& {! f9 y, H   }
k=0;
for(i=1;i&lt;=num_a;i++) if(pu==0) k=1;
+ y4 z% f% j& N for(i=1;i&lt;=num_b;i++) if(pv==0) k=1;
if(k==1) computeuv();
}</P>
/ [8 N8 c2 a7 n6 W<>int check() {
int i,j,k,l;
k=l=0;
/ m8 N, O# {$ D& v1 r) `, S for(i=1;i&lt;=num_a;i++)
  for(j=1;j&lt;=num_b;j++)
: }- O/ Y* S: E8 y- ]  O   if(pbase[j]==0) {
    base[j]=ab[j]-u-v[j];
# b0 t! J8 Y. _  U    if(base[j]&lt;0) k=1;
, c9 ]8 o5 ~: I- ^" G    else if(base[j]==0) l=1;
2 r' _$ @# ]  D  M" u   }
, f$ E7 R& ]& h0 ~. @2 i- v7 L/* for(i=1;i&lt;=num_a;i++){
  for(j=1;j&lt;=num_b;j++) printf("base %lg\t",base[j]);
  putchar('\n');}
for(i=1;i&lt;=num_a;i++){
  for(j=1;j&lt;=num_b;j++) printf("pbase %d\t",pbase[j]);
' `7 n2 i/ m% t) d" Z- C: ~  putchar('\n');}
0 N" f* r" G1 k' F* O  x7 ]*/
if(k==0&amp;&amp;l==0) {status=1; return 1;}
# s$ b- x4 n! x7 [ else if(k==0&amp;&amp;l!=0) {status=-1; return 1;}
" [6 C: @( a( Q else return 0;
}</P>
<>int circle(enum direction dir,struct element cir[],int *t) {
1 j/ d9 u9 S: h  \ int i,j,k;
/*
putchar('\n');
% V  q) R3 }1 _" R1 }+ A5 J( X for(i=1;i&lt;=*t;i++) printf("%d: r%d c%d\t",i, cir.r,cir.c);
  o5 t, Z. m) l! g putchar('\n');
*/
; c/ C2 ?" w' |8 Y  u# ` if((*t)!=1&amp;&amp;cir[(*t)].r==cir[1].r&amp;&amp;cir[*t].c==cir[1].c) {
, E8 m7 @" Z' [  s( s  t--;
  K, N. @. @& H4 E0 p; w  return 1;
}
! a1 P1 J+ m- E) p2 I if(dir!=down) {
  k=0;
7 R# w. Z9 |! U2 r# A  for(i=cir[*t].r-1;i&gt;=1;i--)
   if(pbase[cir[*t].c]==1||(i==cir[1].r&amp;&amp;cir[*t].c==cir[1].c)) {k=1; break;}
0 F- u  D9 E& R) ?4 R( W  for(j=2;j&lt;=*t;j++) if(i==cir[j].r&amp;&amp;cir[*t].c==cir[j].c) k=0;
  if(k==1) {
   if(dir==up) cir[*t].value=0;
   else cir[*t].value=1;
   (*t)++;
   cir[*t].r=i;
, Y6 e# g' ~2 B   cir[*t].c=cir[(*t)-1].c;
   if(circle(up,cir,t)) return 1;
& p. e- h  O; V1 _2 \  }
1 K# ]* D) g/ O+ K1 @; b& ?: W }
( q& f! y8 S  f4 m$ B& ^ if(dir!=up) {
/ C) }# T/ w: R# u$ ?5 t  k=0;
  for(i=cir[*t].r+1;i&lt;=num_a;i++)
   if(pbase[cir[*t].c]==1||(i==cir[1].r&amp;&amp;cir[*t].c==cir[1].c)) {k=1; break;}
  for(j=2;j&lt;=*t;j++) if(i==cir[j].r&amp;&amp;cir[*t].c==cir[j].c) k=0;
  if(k==1) {
" d7 Y4 T, b( X" d7 E- o   if(dir==down) cir[*t].value=0;
   else cir[*t].value=1;
4 t* M+ G' Z- q9 C, [" E   (*t)++;
   cir[*t].r=i;
- g# X% j; T' ^% F( ~   cir[*t].c=cir[(*t)-1].c;
   if(circle(down,cir,t)) return 1;
' W/ O* }9 R. Y0 r% {! b  }
9 D' V$ M& ]+ z4 e* E! \* E. R }
5 F6 ?% }2 R0 ~5 g2 K* g2 y if(dir!=right) {
  k=0;
2 O5 [! l( n2 p* p  for(i=cir[*t].c-1;i&gt;=1;i--)
$ T2 |, }2 M- h8 l/ H. @   if(pbase[cir[*t].r]==1||(cir[*t].r==cir[1].r&amp;&amp;i==cir[1].c)) {k=1; break;}
  for(j=2;j&lt;=*t;j++) if(cir[*t].r==cir[j].r&amp;&amp;i==cir[j].c) k=0;
  if(k==1) {
5 _2 I5 P9 Y  w7 |7 Z2 B   if(dir==left) cir[*t].value=0;
/ P: `8 ^# t6 i+ P& N   else cir[*t].value=1;
* {4 M5 t3 ~( \& y   (*t)++;
   cir[*t].r=cir[(*t)-1].r;
2 m* K7 d1 W, P: }" u# A7 A   cir[*t].c=i;
1 }" x* }/ ~# p9 r3 O. V   if(circle(left,cir,t)) return 1;
  }
}
1 U) l. X5 Q$ o6 v if(dir!=left) {
, O6 z1 f) K5 n) J$ M  I! Y1 X  k=0;
  for(i=cir[*t].c+1;i&lt;=num_b;i++)
4 d; `5 A" \" }/ e0 a   if(pbase[cir[*t].r]==1||(cir[*t].r==cir[1].r&amp;&amp;i==cir[1].c)) {k=1; break;}
  for(j=2;j&lt;=*t;j++) if(cir[*t].r==cir[j].r&amp;&amp;i==cir[j].c) k=0;
0 a4 o- r0 g- P# e  if(k==1) {
# y' W1 ^* b# z2 F' F2 A; y   if(dir==right) cir[*t].value=0;
8 y4 H8 }; p5 m   else cir[*t].value=1;
   (*t)++;
   cir[*t].r=cir[(*t)-1].r;
5 M8 G3 m9 Z6 n' ]   cir[*t].c=i;
1 R- k: i8 c  ?2 r8 s   if(circle(right,cir,t)) return 1;
4 }2 \$ c% h9 z$ o5 R3 V0 o  }
  Q5 h# t* O' N6 ^ }
(*t)--;
return 0;
1 c/ [6 @8 u/ a4 R6 c}</P>
. Z6 Q5 M" Y* N<>void improve() {
int i,j,k,t;
struct element base_in,base_out,cir[2*MAX+1];</P>
* _4 r7 b, X+ ^: n4 e9 w<> for(i=1;i&lt;=num_a;i++) pu=0;
; c" l3 b; i$ {" p4 ?8 ] for(i=1;i&lt;=num_b;i++) pv=0;
u[1]=0; pu[1]=1;
$ n& y- [- O+ m% L. R computeuv();
) {: b) T) ~- C2 J" F if(check()) return;
for(i=1;i&lt;=num_a;i++)
. M! J) Y* R# ]* c3 l- b5 d  for(j=1;j&lt;=num_b;j++)
. s& |7 m( H6 X   if(pbase[j]==0) break;
base_in.r=i;
" j, F4 v4 H. `* X base_in.c=j;
- h- S* w, F! J( n# e base_in.value=base[j];</P>
<> for(i=1;i&lt;=num_a;i++)
" m4 h) ?4 d/ _  for(j=1;j&lt;=num_b;j++)
7 A9 g0 A  |# E# Z   if(pbase[j]==0&amp;&amp;base[j]&lt;base_in.value) {
" d2 h& P5 g, U( H* A( K% f    base_in.r=i;
0 J3 A  N5 G- z% k6 U    base_in.c=j;
' B7 l( ~% [2 M% ^* X    base_in.value=base[j];
   }</P>
<> t=1;
. ]4 G  ?7 C6 M- D% \ cir[t].r=base_in.r;
cir[t].c=base_in.c;
* @0 F3 D5 f/ ^5 q cir[t].value=1;
8 H) ?6 S) D3 ^; B* e if(!circle(mid,cir,&amp;t)) {
  printf("程序出错！按回车结束");
- W: Q8 f' I! S9 F) c3 x  getchar();
  exit(0);
+ B/ r8 O. Z" a* p7 [5 M }
t--;
  n, _; T0 s4 i: j- V. X; @* \  H// for(i=1;i&lt;=t;i++) printf("%d:r%d c%d v%lg\t",i,cir.r,cir.c,cir.value);
// putchar('\n');</P>
<> for(i=2;i&lt;=t;i++) if(cir.value==1) break;
base_out=cir;
base_out.value=base[cir.r][cir.c];
) C6 f6 r% Y' `) q) g; O  ? k=1;
for(i=1;i&lt;=t;i++)
! a6 P+ F9 X* l# O+ J  if(k%2==0&amp;&amp;cir.value==1&amp;&amp;base[cir.r][cir.c]&lt;base_out.value) {
8 K$ ^5 c6 m2 Z  t' a3 H- w' W   base_out=cir;
   base_out.value=base[cir.r][cir.c];
' W. x' V0 f, O' X; W   k++;
8 L: L# b. y4 ?  }
# W# {' `5 T( U4 d  else if(cir.value==1) k++;
" J, q2 r* \% Y+ y, w  R+ A base[cir[1].r][cir[1].c]=0;
k=1;
9 x- F  v# {6 h! ^% h' H for(i=1;i&lt;=t;i++) {
  if(k%2==1&amp;&amp;cir.value==1) {
0 D& W: M& b8 y" ]6 d9 j# c   base[cir.r][cir.c]+=base_out.value;
! W' Z& `9 \  `( L  ?2 |, d   k++;
  }
( |! w) @) |: k  else if(k%2==0&amp;&amp;cir.value==1) {
   base[cir.r][cir.c]-=base_out.value;
* J8 n* z  N6 H7 |   k++;
  }
}
pbase[base_out.r][base_out.c]=0;
pbase[base_in.r][base_in.c]=1;</P>
<> improve();
* U* \/ B' l3 d2 M* M8 p9 l0 a}</P>
* w3 @# v. l# |6 P8 O+ N8 V<>void output() {
+ |0 W& s; ^/ w4 G int i,j;
double sum=0;
- S' P1 Y% A. F7 Y  U) H3 r( n( C printf("\n运量为：\n");
for(i=1;i&lt;=num_a;i++) {
, s! }# o( M1 x: O  putchar(' ');
  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==1) {
- e9 g8 a! E& p2 g6 r3 r5 G    printf("A%d-&gt;B%d:%lg\t",i,j,base[j]);
4 O4 O- @0 a5 ^    sum+=base[j]*ab[j];
( x! q$ T; _/ c* }/ t  X4 Y   }
   else printf("A%d-&gt;B%d:0\t",i,j);
, h$ A9 Q2 d# K& {- D4 Q) M+ E" Q7 ]  putchar('\n');
}
. A2 A. k9 n7 T& L3 w3 L printf("\n最低总运费为：%lg\n",sum);
% q: }% X+ i. d4 x" _- K}
7 K' B. k% w9 {) w  v) K( P1 i</P>

zhongguohelin

good!   就是希望下次把格式稍稍注意下，这样可读性太差了呀~

enrique08

太乱了吧！！！！！！！！！！

hzlhm

乱了让人不想看了。。。。。。。。

liunengwu

好！顶顶！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！