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

plgatc

<>/*************************************************************************
                         表上作业法解运输问题        
1 K& ?' g' i2 s. g- Y% ?! s# B% `! J
$ E, L+ N5 _( R 编程环境：VC++6.0     
程序说明：
! C, [" ]; k/ {( Q! Z2 I Vogel法求初始解，位势法检验是否最优，递归搜索闭回路改进解。
& O7 {1 R$ i: ^- ~5 ^ *************************************************************************/
#include &lt;stdio.h&gt;
7 A" \2 }. Q* A# Z#include &lt;stdlib.h&gt;</P>
<>#define MAX 100
#define M 999999</P>
<>int status; //1唯一最优解，-1无穷多最优解</P>
/ B* V/ w- E" X6 g) _( O<>int num_a,num_b;
7 G6 R' n8 R9 \! Tdouble a[MAX],b[MAX],temp_a[MAX],temp_b[MAX];
double u[MAX],v[MAX],pu[MAX],pv[MAX];
, _( ^7 B0 a/ t, Tdouble ab[MAX][MAX],temp_ab[MAX][MAX];
2 L0 q8 V8 G. Wdouble base[MAX][MAX];
( }* e1 Z% `$ z6 m& m; M" D6 jint pbase[MAX][MAX];
; Y0 l0 c& N# jstruct element {
int r;
int c;
double value;
};
enum direction {mid,up,down,left,right};</P>
2 U( C2 ?+ F& f( D<>void create();
void banner();
double dabs(double d);
void findinit();
0 a! M$ C: _; I1 S/ jvoid computeuv();
4 Q# R# \, ?/ s) S2 U8 ^int check();
2 Z+ S5 J* \, a, S/ l- H* cint  circle(enum direction dir,struct element cir[],int *t);
void improve();
0 o/ @: @5 [! n3 N. Bvoid output();</P>
<>void main() {
banner();
! h4 ]) ~* A* x* O create();
printf("\n按回车确认后开始求解");
getchar();
$ u3 g' t; O& E* m8 m  |- I getchar();
findinit();
( D7 _- S' k, A9 ?( X6 Z, A improve();
switch(status) {
' D& M: j' I, Z" R: F! m: f case 1:
  output();
  puts("\n原问题有唯一最优解。\n");
  puts("\n按回车结束");
0 w: G7 D" u) o, k1 u% T  getchar();
' A3 o* i/ p- y  exit(0);
case -1:
! r' t" f; c3 M+ ^2 J  output();
  puts("\n原问题有无穷多最优解。\n");
  puts("\n按回车结束");
  getchar();
9 X% W1 Z3 R( L+ v9 W) ?, s  exit(0);
( B; }, B1 U" z5 A$ s4 Y }
* j( U- l+ i; N6 X/ x, L}</P>
<>void banner() {
printf("\t\t****************************************\n");
printf("\t\t         表上作业法解运输问题\n");
printf("\t\t                              Thunder\n");
printf("\t\t****************************************\n");
printf("\n");
' a3 j$ G/ t2 r% R}</P>
<>void create() {
& [2 o/ H5 w# S* G$ E+ M int i,j;
1 H. Z% L$ V- Y, i3 ~ double sum_a,sum_b;
char confirm;
+ Q  z6 l6 E' r9 a/ L* k: N while(1) {
  printf("请输入产地个数：");
3 D. ]  w) {  _. ?5 A0 k1 ]  scanf("%d",&amp;num_a);
" R% N" K9 K3 u8 T  for(i=1;i&lt;=num_a;i++) {
) O! ^+ Y- t/ @. g7 m+ N   printf("A%d产量：",i);
   scanf("%lf",&amp;a);
: Y, G0 j7 E: x3 F% t  }
  for(i=1;i&lt;=num_a;i++) printf("A%d产量：%lg\t",i,a);
; h9 p/ ]( z. w. ]- }+ L. R  printf("\n正确吗？：(y/n)");
, e# J' b; b7 T% H6 @' y8 c  getchar();
% I, o5 j9 f2 k' D( e  confirm=getchar();
9 [* m3 m3 d& v$ U1 a6 k  if (confirm=='y') break;
7 n; l( c; E" ^  s6 _) C' p( W  else if(confirm=='n') continue;
}
; V$ W6 W8 t5 j( Z. c+ [ while(1) {
' ]6 _) z- N. W9 N4 |2 Q4 r  printf("\n请输入销地个数：");
& K. }. D$ S' }( _# Z+ c) ?) ^  scanf("%d",&amp;num_b);
  for(i=1;i&lt;=num_b;i++) {
! U7 Y; l% {, o9 j. U$ B   printf("B%d销量：",i);
+ ^, j/ V9 Z6 s& C5 ^, F9 n( X   scanf("%lf",&amp;b);
& W  O+ `5 L/ t8 S  O) X  }
: \# H5 T+ J& [3 f  for(i=1;i&lt;=num_b;i++) printf("B%d销量：%lg\t",i,b);
  printf("\n正确吗？：(y/n)");
7 O1 r  @$ ^) I" o  getchar();
, V- `( M$ W/ X& B5 t, a5 T  confirm=getchar();
5 h: G9 x8 i5 Y  if (confirm=='y') break;
  v. O2 i% f# Z" l0 X1 q  else if(confirm=='n') continue;
}
! l9 r* ?, m( u1 r8 A putchar('\n');
for(i=1;i&lt;=num_a;i++) {
  for(j=1;j&lt;=num_b;j++) {
   printf("A%d到B%d运价：",i,j);
   scanf("%lf",&amp;ab[j]);
  }
  for(j=1;j&lt;=num_b;j++) printf("A%d到B%d：%lg\t",i,j,ab[j]);
  printf("\n正确吗？：(y/n)");
+ c# {+ j# O7 N$ A  y  getchar();
# Q2 D/ d5 T' g! `  W& O5 p  confirm=getchar();
  if(confirm=='n') i--;
  putchar('\n');
) K. h8 F/ `9 r/ c }
//处理产销不平衡的情况
sum_a=sum_b=0;
for(i=1;i&lt;=num_a;i++) sum_a+=a;
8 R2 |9 u2 S5 V/ K: Z. P8 U4 }# o5 |0 {4 ~0 P 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) {
  printf("\t供大于求，增加假想销地B%d。\n",++num_b);
  b[num_b]=sum_a-sum_b;
0 r6 p, L! K1 u8 c' D6 t/ o  for(i=1;i&lt;=num_a;i++) ab[num_b]=0;
}
else if(sum_a&lt;sum_b){
! T7 S% _' o# ?  S  a  printf("\t供不应求，增加假想产地A%d。\n",++num_a);
  a[num_a]=sum_b-sum_a;
& Y* M4 _& m  x7 v) E  for(i=1;i&lt;=num_b;i++) ab[num_a]=0;
}
1 ~; {3 j% W1 G& J //求解前的准备
for(i=1;i&lt;=num_a;i++)
  for(j=1;j&lt;=num_b;j++)
   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;
' k! I" ]0 d1 e for(i=1;i&lt;=num_a;i++)
8 S' m( @) [  z+ }1 W for(j=1;j&lt;=num_b;j++) temp_ab[j]=ab[j];
$ J. [  O. X6 G8 g. k- e% s //回显问题
7 W$ ^6 d+ P3 m8 i printf("\n\n原问题为：\n\n");
   printf("产量：\n ");
1 e* S$ @$ |. e+ M, A1 t for(i=1;i&lt;=num_a;i++) printf("A%d:%lg\t",i,a);
/ ]( U  `4 `1 o! _ printf("\n运量：\n ");
for(i=1;i&lt;=num_b;i++) printf("B%d:%lg\t",i,b);
printf("\n运价为：\n");
5 D) m1 `; N" [* L7 i$ X2 z' w. J( r for(i=1;i&lt;=num_a;i++) {
  putchar(' ');
$ `* u' X5 c$ n, a6 \  for(j=1;j&lt;=num_b;j++)
  v' b0 k. g! G   printf("A%d-&gt;B%d:%lg\t",i,j,ab[j]);
4 C, m# r$ P8 R$ f1 K1 ]- ]1 ~  putchar('\n');
}
8 L0 j. r( ]6 n  Q/ C3 _9 J) w, o  ]3 `}</P>
5 O& @; E7 J2 }0 b# [$ A<>double dabs(double d) {
if(d&gt;=0) return d;
( }2 @  D! L2 y7 @- `7 ?3 ~, I else return -d;
! a" G: D/ r1 \+ @}</P>
<>void findinit() {
int i,j,k;
5 Q, \5 P" I; B& j3 J3 C, m double r_penum[MAX],c_penum[MAX];
struct largest {
2 g0 e- |- _/ b1 H+ x  char rc;
- {5 B: V$ m" c7 k0 [4 f  int num;
  double value;
0 P+ H; S  U2 Y. g };
- [" C! Z/ p5 G8 ]* X struct largest lar1,lar2;
int r=0,c=0;
8 w  L" F5 U0 z1 @' | double a1,a2,b1,b2,temp;</P>
: Z1 C) o$ h" ^! |0 H<> for(i=1;i&lt;=num_a;i++) {
" x9 m/ p+ d% {$ O& a9 ^  temp=temp_ab[1];
  for(j=1;j&lt;=num_b;j++)
0 i7 `7 R$ Z3 C   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
$ {3 V( C5 d+ K  a1=a2=temp;
  for(j=1;j&lt;=num_b;j++)
   if(temp_ab[j]&lt;=a1) {
    a2=a1;
    a1=temp_ab[j];
   }
   else if(temp_ab[j]&lt;=a2) a2=temp_ab[j];
! E$ N; h% c; q( M  r_penum=dabs(a1-a2);
}</P>
<> for(i=1;i&lt;=num_b;i++) {
( }% X' Z7 B9 e4 P8 y* J% p" z- Z  temp=temp_ab[1];
  for(j=1;j&lt;=num_a;j++)
) Y7 @- [4 R+ T& o/ r( r+ K+ f7 j   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
, h6 H, `, z0 f( L0 M5 c  b1=b2=temp;
  for(j=1;j&lt;=num_a;j++)  
   if(temp_ab[j]&lt;=b1) {
    b2=b1;
& N. d  B, m; t8 w& }8 ]; Q    b1=temp_ab[j];
! i+ }: q$ A. C7 _  _$ _   }
  w6 L" X: s6 B) i' D( E/ ]+ ?+ k$ x   else if(temp_ab[j]&lt;=b2) b2=temp_ab[j];
1 l5 c. g% [* u. C; Z2 D/ ^  c_penum=dabs(b1-b2);
}
) u. {2 q) \* ~& B  _, @; f /*
% N8 r2 O6 h: h# A9 W( N; _ for(i=1;i&lt;=num_a;i++) printf("pa%d=%lg ",i,r_penum);
putchar('\n');
for(i=1;i&lt;=num_b;i++) printf("pb%d=%lg ",i,c_penum);
7 m3 N2 X) P1 M! {5 _- T  U2 d */
temp=r_penum[1];
for(i=1;i&lt;=num_a;i++) if(r_penum&lt;temp) temp=r_penum;
for(i=1;i&lt;=num_b;i++) if(c_penum&lt;temp) temp=c_penum;</P>
<> //考虑了有两个罚数相等的情况，大于两个相等只取其中两个进行比较
9 M8 C4 l8 ~8 i7 R1 ] lar1.value=lar2.value=temp;
/ t  V) M8 I3 I4 Z) J  {1 ]- P( a lar1.num=lar2.num=1;
& I. ^% }9 c' Q lar1.rc=lar2.rc='r';
* P0 {9 x4 p  P  u/ @. w for(i=1;i&lt;=num_a;i++)
  if(r_penum&gt;=lar1.value) {
   lar2=lar1;
   lar1.rc='r';
( D4 z9 R8 \9 m   lar1.num=i;
   lar1.value=r_penum;
  }
  else if(r_penum&gt;=lar2.value) {
   lar2.rc='r';
" y! x' u" R* x- J7 l0 v( ^* Z   lar2.num=i;
0 ]1 ?. Q: @$ g3 |% z+ E   lar2.value=r_penum;
# U1 }. s% S0 l; s8 ~# m  }</P>
* I: u1 f! T$ n& {* L<> for(i=1;i&lt;=num_b;i++)
2 G  A4 x$ H. ^5 h) _' o! v8 N5 l  if(c_penum&gt;=lar1.value) {
   lar2=lar1;
. \1 V) T2 u' j" Y( ?7 J! C, w- e   lar1.rc='c';
   lar1.num=i;
) ]+ m! T+ x+ u8 ~1 b" z5 N2 H   lar1.value=c_penum;
  }
  else if(c_penum&gt;=lar2.value) {
. E; V2 q) Y# n* r3 s0 N9 l   lar2.rc='c';
   lar2.num=i;
   lar2.value=c_penum;
6 \( j- y$ u# M4 E  }</P>
/ D* M& J/ n- |  F7 O, R<> if(lar1.value==lar2.value&amp;&amp;(lar1.num!=lar2.num||lar1.rc!=lar2.rc)) {
1 ^0 w0 A! g0 t2 O0 z8 e; D  if(lar1.rc=='r'&amp;&amp;lar2.rc=='r') {
4 J" G% g' p0 C   temp=temp_ab[lar1.num][1];
3 F& P0 G! R& O7 y  N1 X+ i   r=lar1.num;
      c=1;
   for(i=1;i&lt;=num_b;i++) {
% V- M; j# I: _: d% G- J$ ?    if(temp_ab[lar1.num]&lt;temp) {
     temp=temp_ab[lar1.num];
5 p  ?9 t: ?, e& \# s4 X     r=lar1.num;
/ c: p0 t- X( n: y     c=i;
    }
    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
6 Y. J$ S9 F9 Z) D6 ~0 h; m     r=lar2.num;
' t5 V$ c) Z  W8 N/ y     c=i;
    }
   }
% Z/ y+ r3 T' m* \- w+ W! j  }
  if(lar1.rc=='c'&amp;&amp;lar2.rc=='c') {
   temp=temp_ab[1][lar1.num];
2 U  Q! I6 @- J# M9 Y   r=1;
      c=lar1.num;
6 l2 U$ L, j' A. g  Z   for(i=1;i&lt;=num_a-1;i++) {
    if(temp_ab[lar1.num]&lt;temp) {
: X9 `" F8 K. F- N* G' t8 h     temp=temp_ab[lar1.num];
     c=lar1.num;
     r=i;
    }
    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
     c=lar2.num;
, `# _9 \; I8 }* ^. s5 N     r=i;
    }
   }
7 Z& ]$ W8 ]! t. \1 V  }
; i( b- A0 h  j  if(lar1.rc=='r'&amp;&amp;lar2.rc=='c') {
4 v3 N) O4 d- U' h   temp=temp_ab[lar1.num][1];
' p3 j6 ~% k. ?2 X& ?   r=lar1.num;
% h# G. k* G% i4 N% R5 x$ y# t      c=1;
   for(i=1;i&lt;=num_b;i++)
    if(temp_ab[lar1.num]&lt;temp) {
3 Z1 k% I  ~! v* f     temp=temp_ab[lar1.num];
( R- v) W  A& i5 j: Z# M     r=lar1.num;
' K" Z3 S, H; W3 S6 D7 m     c=i;
    }
) a9 r2 g0 ^2 k( r; b2 a9 x$ n   for(i=1;i&lt;=num_a;i++)
    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
     c=lar2.num;
0 a) s! u: h& v7 N7 p( t7 ?     r=i;
    }
1 x) l0 v+ }  k: ~5 a; h  }
  if(lar1.rc=='c'&amp;&amp;lar2.rc=='r') {
+ h( `& E, M2 F" |+ Q7 u   temp=temp_ab[1][lar1.num];
, i: v& w7 h/ F   r=1;
7 I$ P5 x: Q6 C# K/ h      c=lar1.num;
   for(i=1;i&lt;=num_b;i++)
+ ]7 c/ {9 r3 x! d( G  J    if(temp_ab[lar2.num]&lt;temp) {
2 f! R6 C3 d7 W8 J. ~9 O     temp=temp_ab[lar2.num];
) K% {: H! t9 M* H" N) O     r=lar2.num;
$ \% Z6 {/ ]" D8 r6 L- i3 |: n4 [; Y     c=i;
    }
/ ]: r) [% t# G9 a- c   for(i=1;i&lt;=num_a;i++)
" G- ]$ V9 V) D    if(temp_ab[lar1.num]&lt;temp) {
     temp=temp_ab[lar1.num];
     c=lar1.num;
" M5 z8 Z' i' m! L& C# f     r=i;
" A5 ]2 ~+ R6 Q7 w. @    }
/ R6 I% b, O, n. H) J* q  }
}
else {
% y- o* Y1 J. q- I, S' k/ t  if(lar1.rc=='r') {
   r=lar1.num;
   c=1;
   temp=temp_ab[lar1.num][1];
   for(i=1;i&lt;=num_b;i++)
    if(temp_ab[lar1.num]&lt;temp) {
) H" D; H: b* \" `6 d     c=i;
     temp=temp_ab[lar1.num];
/ y  g3 D/ @3 r' d  W4 h6 g5 a$ Y    }
  }
  else {
8 x8 p- B2 `, H& _   r=1;
6 i1 H' I& T" ^   c=lar1.num;
8 m: }7 R, _$ a7 j   temp=temp_ab[1][lar1.num];
   for(i=1;i&lt;=num_a;i++)
9 E! ~: N6 s3 a0 B7 _6 E( r5 F    if(temp_ab[lar1.num]&lt;temp) {
7 u# P4 Y$ e9 C' E6 l! D) C4 {     r=i;
9 I; J5 i! a- Z& B: j& ]1 e; H: K     temp=temp_ab[lar1.num];
! k5 E* ?8 t0 t/ u    }
  }
}
pbase[r][c]=1;
+ w( b# t) n3 @  v" C3 R if(temp_a[r]&gt;temp_b[c]) {
1 W$ d( z% [/ b0 {" A" c! U) u% H  base[r][c]=temp_b[c];
+ ^! l8 \' w8 ]3 u  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;
/ ]0 B* x% g0 ^+ ]+ ?* T4 ~ }
& H7 ]. D, {0 ~: J9 } else if(temp_a[r]&lt;temp_b[c]) {
  base[r][c]=temp_a[r];
! ?$ _# ?; H( q% I5 ~  temp_b[c]=temp_b[c]-temp_a[r];
. c/ {5 I. Q2 Z* Y5 r  temp_a[r]=0;
  for(i=1;i&lt;=num_b;i++) temp_ab[r]=M;
1 X) g5 [: O: ~* n. F }
; Q& M8 \8 f( s else if(temp_a[r]==temp_b[c]) {
0 c: L0 ]* B) u: N  base[r][c]=temp_a[r];
$ ], K( k5 E4 X, J0 `; @: H  temp_a[r]=temp_b[c]=0;
  for(i=1;i&lt;=num_a;i++) temp_ab[c]=M;
9 P) y! r. Y$ ?* V2 R6 w0 O  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;
  for(i=1;i&lt;=num_b;i++) if(temp_b!=0) k=1;
  if(k!=0) {
, x% u8 F/ T1 z3 F6 c) d1 ?& u4 H   k=0;
   for(i=1;i&lt;=num_a;i++) if(pbase[c]!=1) {k=1;break;}
% T; p: @2 `: X   for(j=1;j&lt;=num_b;j++) if(pbase[r][j]!=1) {k=2;break;}
   if(k==1) pbase[c]=1;
   else if(k==2) pbase[r][j]=1;
  }
% W; {" y8 L+ T7 A- K }
! l7 r9 u  }/ b( U8 M k=0;
for(i=1;i&lt;=num_a;i++) if(temp_a!=0) k=1;
% e  a( I! z: f3 @+ w* F$ d for(i=1;i&lt;=num_b;i++) if(temp_b!=0) k=1;
if(k==0) return;
findinit();
" f+ V0 A6 v* g/ E6 R$ k}</P>
" z+ k% |# t! Q; N<>void computeuv() {
int i,j,k;
% e  _( J0 N2 O; V for(i=1;i&lt;=num_a;i++)
$ X: e9 }9 C  a+ ]  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==1) {
' K5 V6 t% s  \- k3 s2 m9 P    if(pu==1) {v[j]=ab[j]-u; pv[j]=1;}
2 _! k, K; ~+ d. A! ~1 g( ]; ?: S* |    if(pv[j]==1) {u=ab[j]-v[j]; pu=1;}
1 ^3 y( [5 H: S$ ^7 r0 f% A+ E# r   }
k=0;
8 U5 J7 F( I. S1 n7 o9 F for(i=1;i&lt;=num_a;i++) if(pu==0) k=1;
for(i=1;i&lt;=num_b;i++) if(pv==0) k=1;
if(k==1) computeuv();
! t3 p( J! q$ N+ y, A7 e5 l5 h' M}</P>
) A, V  e: t7 T2 V1 n<>int check() {
9 J  ^7 l! t3 Y* J# L# A int i,j,k,l;
7 t% L; p) e7 ^" e8 r- a4 g k=l=0;
for(i=1;i&lt;=num_a;i++)
8 r) K+ Y/ ^7 l6 D  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==0) {
    base[j]=ab[j]-u-v[j];
    if(base[j]&lt;0) k=1;
    else if(base[j]==0) l=1;
% I$ u8 m2 [+ Z; @5 d   }
% P; f+ q+ K6 y, B' `) w& ?/* for(i=1;i&lt;=num_a;i++){
, p& A9 p1 m3 E) B  for(j=1;j&lt;=num_b;j++) printf("base %lg\t",base[j]);
/ ?7 L) \8 t4 P# d5 o4 n  putchar('\n');}
6 W2 @) b: \& q1 u for(i=1;i&lt;=num_a;i++){
  for(j=1;j&lt;=num_b;j++) printf("pbase %d\t",pbase[j]);
( G$ A; |) A) c, B; f: I  putchar('\n');}
; O3 a7 v) g: O*/
if(k==0&amp;&amp;l==0) {status=1; return 1;}
else if(k==0&amp;&amp;l!=0) {status=-1; return 1;}
else return 0;
}</P>
2 r4 F3 j/ I+ m$ T* d* B<>int circle(enum direction dir,struct element cir[],int *t) {
& n4 S8 }1 @, _0 r int i,j,k;
/*
putchar('\n');
for(i=1;i&lt;=*t;i++) printf("%d: r%d c%d\t",i, cir.r,cir.c);
putchar('\n');
; `5 ~1 C( X6 {: [& |; h) m7 b* j */
if((*t)!=1&amp;&amp;cir[(*t)].r==cir[1].r&amp;&amp;cir[*t].c==cir[1].c) {
  t--;
3 Z! _! T) w. Y+ g0 V8 v  return 1;
}
if(dir!=down) {
/ i" w- c5 M  f" g4 j  k=0;
3 }0 w5 x& j+ X  for(i=cir[*t].r-1;i&gt;=1;i--)
& f5 p! Y. i0 X; f# C8 [( {   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) {
   if(dir==up) cir[*t].value=0;
) K& w& Q* ^5 N" _  \   else cir[*t].value=1;
, \* c* ]6 A2 L   (*t)++;
   cir[*t].r=i;
5 f4 @* f# C) h' l$ B5 z6 @3 h   cir[*t].c=cir[(*t)-1].c;
: m1 d: s" b5 H. Y9 t5 ]2 g% ~6 l   if(circle(up,cir,t)) return 1;
  }
}
3 [6 K& p3 U# A7 q( u if(dir!=up) {
) D7 p- M9 Q' w  c5 R* w% l0 g  k=0;
/ X7 B1 z) d% [4 i5 s( ^  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;}
2 r5 l& ~  N3 F  X% D+ D% i6 ?  for(j=2;j&lt;=*t;j++) if(i==cir[j].r&amp;&amp;cir[*t].c==cir[j].c) k=0;
0 q3 @' n! T* V) j$ {" T$ E  if(k==1) {
   if(dir==down) cir[*t].value=0;
   else cir[*t].value=1;
* Z7 t7 L& G5 r4 s   (*t)++;
& L% |+ j3 I; H+ E& }; T6 ~   cir[*t].r=i;
5 H) v. H' d# Z+ g$ q0 ?" ~6 e0 E  }   cir[*t].c=cir[(*t)-1].c;
  P* a+ Y) b8 J- X0 n% f: r& l   if(circle(down,cir,t)) return 1;
  }
}
if(dir!=right) {
8 l1 R1 ^# m: B  L- r9 w  k=0;
2 t5 O9 N$ `: p! t6 c" q, i) V  w  for(i=cir[*t].c-1;i&gt;=1;i--)
   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;
2 p( ~2 h2 c5 D! i, J7 Y  if(k==1) {
   if(dir==left) cir[*t].value=0;
   else cir[*t].value=1;
8 M. ]8 `; ^7 N# \( Y4 ~   (*t)++;
, Y( y2 p! @0 q# q   cir[*t].r=cir[(*t)-1].r;
   cir[*t].c=i;
$ |3 Q# J! J5 _" D# P- x   if(circle(left,cir,t)) return 1;
  }
) F0 G) _  p5 S$ h3 C }
2 D5 D1 g6 d4 m" i6 C if(dir!=left) {
: `: Z8 L; X( t  k=0;
. H1 g; f- X! o7 z# ?  for(i=cir[*t].c+1;i&lt;=num_b;i++)
6 _3 L4 [$ h. Y9 X2 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;
, ?! {' O6 K$ C; }. s0 W# _& k/ m- {5 \  if(k==1) {
) P: G1 V+ O0 X+ z   if(dir==right) cir[*t].value=0;
   else cir[*t].value=1;
   (*t)++;
   cir[*t].r=cir[(*t)-1].r;
   cir[*t].c=i;
   if(circle(right,cir,t)) return 1;
1 o! \2 L0 z( C% J% ~4 R  }
0 t4 A. L5 [4 u }
& d) u; V  N; f# D3 a9 [ (*t)--;
return 0;
}</P>
) O* k$ l1 O6 L0 @0 ?1 u<>void improve() {
int i,j,k,t;
2 C% ?; G" E, Q1 y# n& s struct element base_in,base_out,cir[2*MAX+1];</P>
<> for(i=1;i&lt;=num_a;i++) pu=0;
for(i=1;i&lt;=num_b;i++) pv=0;
8 V  o( ^( m, B  @9 F& [- [ u[1]=0; pu[1]=1;
computeuv();
if(check()) return;
for(i=1;i&lt;=num_a;i++)
  for(j=1;j&lt;=num_b;j++)
$ z. l7 u" y: Q$ J/ G   if(pbase[j]==0) break;
base_in.r=i;
* K5 j* ~& V" G7 ] base_in.c=j;
base_in.value=base[j];</P>
9 B, A0 \) y$ \' u: Z% y2 W$ G2 q1 i6 I<> for(i=1;i&lt;=num_a;i++)
  for(j=1;j&lt;=num_b;j++)
' U& F5 I- e5 U2 s: I( }   if(pbase[j]==0&amp;&amp;base[j]&lt;base_in.value) {
    base_in.r=i;
    base_in.c=j;
* O$ g7 \2 Z) e9 t6 E    base_in.value=base[j];
- x- D8 u  r3 U1 I! g  F3 n   }</P>
% V; T4 ?/ a  L' L<> t=1;
cir[t].r=base_in.r;
cir[t].c=base_in.c;
4 K% U  l" i, M( ^& R% {( x; d cir[t].value=1;
! X3 h) U3 Y" z( O8 L8 U if(!circle(mid,cir,&amp;t)) {
  printf("程序出错！按回车结束");
  getchar();
  exit(0);
; U! Y; R0 W- L( U4 Y$ w }
t--;
  p$ E# z# n1 n9 l6 ~* q# F! f0 p// for(i=1;i&lt;=t;i++) printf("%d:r%d c%d v%lg\t",i,cir.r,cir.c,cir.value);
9 O" H8 v5 y; \$ h, r# c// putchar('\n');</P>
& i; q' i8 K+ K) m# y, d9 L" L1 m<> for(i=2;i&lt;=t;i++) if(cir.value==1) break;
base_out=cir;
base_out.value=base[cir.r][cir.c];
k=1;
for(i=1;i&lt;=t;i++)
  if(k%2==0&amp;&amp;cir.value==1&amp;&amp;base[cir.r][cir.c]&lt;base_out.value) {
   base_out=cir;
; N) K& S, W3 h1 S2 j3 Q   base_out.value=base[cir.r][cir.c];
   k++;
; e9 O0 c& p. X  }
" ~; b+ S- |8 q: r) t  else if(cir.value==1) k++;
base[cir[1].r][cir[1].c]=0;
k=1;
; B: G4 y/ |0 R  ^# Z3 Y for(i=1;i&lt;=t;i++) {
  if(k%2==1&amp;&amp;cir.value==1) {
! ]4 l8 Z% S2 x( _" |1 c   base[cir.r][cir.c]+=base_out.value;
   k++;
  }
  else if(k%2==0&amp;&amp;cir.value==1) {
3 X* a: T2 `8 Z  W   base[cir.r][cir.c]-=base_out.value;
   k++;
  }
2 c2 y# a  B  V9 F }
pbase[base_out.r][base_out.c]=0;
pbase[base_in.r][base_in.c]=1;</P>
$ D! g# h- Q# x$ {# A<> improve();
}</P>
8 {  q8 c" S# S<>void output() {
% c- r) j$ i% ~+ @$ K int i,j;
6 c" I- ]3 g' e$ g7 { double sum=0;
1 p- A' ]2 K& V! W6 j* M% ?7 a. B4 ~6 w printf("\n运量为：\n");
/ G! t; _2 m  K$ f* \5 X for(i=1;i&lt;=num_a;i++) {
  K; o( }, N' w, N; B9 J  putchar(' ');
  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==1) {
    printf("A%d-&gt;B%d:%lg\t",i,j,base[j]);
- D* @. }% O: V+ ]5 h8 F, u# K    sum+=base[j]*ab[j];
   }
   else printf("A%d-&gt;B%d:0\t",i,j);
! z% E; A: a. ~: a$ ~  putchar('\n');
, {" n! F" y4 F) @1 H, R9 O! x8 f }
' q" j( {% D1 J printf("\n最低总运费为：%lg\n",sum);
$ L0 w' W0 D) v; T9 n) o# ~! y7 D}
8 A7 {: }- q+ U</P>

zhongguohelin

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

enrique08

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

hzlhm

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

liunengwu

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