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

plgatc

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

编程环境：VC++6.0     
程序说明：
% \0 k. w' x8 t% t9 B( W Vogel法求初始解，位势法检验是否最优，递归搜索闭回路改进解。
7 Y5 D* Z$ W! p, U' Y  h *************************************************************************/
#include &lt;stdio.h&gt;
% F" V: j  Z. V$ }' S#include &lt;stdlib.h&gt;</P>
<>#define MAX 100
#define M 999999</P>
<>int status; //1唯一最优解，-1无穷多最优解</P>
2 t2 U* l- @* [2 C, q  {<>int num_a,num_b;
+ A, `6 [9 y  D3 ?# H' rdouble a[MAX],b[MAX],temp_a[MAX],temp_b[MAX];
0 X/ `& A! B" o9 E* Bdouble u[MAX],v[MAX],pu[MAX],pv[MAX];
6 z1 a+ I8 @2 u" `  O; Rdouble ab[MAX][MAX],temp_ab[MAX][MAX];
double base[MAX][MAX];
int pbase[MAX][MAX];
struct element {
. S1 [: e* y! W: ?5 d0 X- @ int r;
" S& W; }# k: z+ m; ~, C int c;
double value;
8 j' }  o# }! S" Z- B, O) c; M};
1 `7 [5 r( D8 {7 Z1 R' g6 ~enum direction {mid,up,down,left,right};</P>
; W8 Y6 o! t, w0 t4 L0 b. ~7 e7 Y<>void create();
- o5 K1 ]- M* w3 J) h  W% lvoid banner();
, C& L# f1 ~4 ^6 n$ n$ ]double dabs(double d);
void findinit();
void computeuv();
int check();
int  circle(enum direction dir,struct element cir[],int *t);
6 \) _: g) a/ t4 zvoid improve();
void output();</P>
<>void main() {
9 ]6 s) L3 o4 y- t2 g7 D banner();
create();
$ I5 I+ Z' w% B7 l printf("\n按回车确认后开始求解");
! L3 ^- R* i* Z% h getchar();
getchar();
findinit();
: z! v9 L/ `  g! F4 y1 V8 i improve();
switch(status) {
case 1:
& ]/ P) [5 M$ L  E0 R. v  output();
  puts("\n原问题有唯一最优解。\n");
  puts("\n按回车结束");
" e' E6 f, D+ G  getchar();
- L' |! P; Z$ m, g6 e  exit(0);
case -1:
  output();
  puts("\n原问题有无穷多最优解。\n");
  puts("\n按回车结束");
8 Q1 [# ]# L5 a  getchar();
4 H7 `2 t3 X2 G) w6 _! g% S  exit(0);
/ k7 c0 g. C1 Q! @; ]. n }
}</P>
( g# h% J+ @/ e! y<>void banner() {
printf("\t\t****************************************\n");
3 G- n% F+ \( c) f$ q/ V( A, m printf("\t\t         表上作业法解运输问题\n");
printf("\t\t                              Thunder\n");
/ W" H/ K4 h4 Y8 x9 ? printf("\t\t****************************************\n");
printf("\n");
}</P>
1 [0 ]4 S3 }/ q<>void create() {
int i,j;
& T$ k9 T% @! ?9 v* C3 t/ I double sum_a,sum_b;
) I7 N; s( c% m" m% U. m char confirm;
' {" U7 ~! M7 E while(1) {
0 D3 A" V  n1 ?; U' r  printf("请输入产地个数：");
  scanf("%d",&amp;num_a);
  for(i=1;i&lt;=num_a;i++) {
   printf("A%d产量：",i);
/ Y" i! @* h. v6 o: r, D2 _# T* ~   scanf("%lf",&amp;a);
  b6 e+ w5 @: N; C4 k  }
3 U  y/ ^9 H  j- w* O+ u  for(i=1;i&lt;=num_a;i++) printf("A%d产量：%lg\t",i,a);
  printf("\n正确吗？：(y/n)");
  getchar();
  confirm=getchar();
  if (confirm=='y') break;
6 Z1 T4 j6 r$ `: U4 X% R  else if(confirm=='n') continue;
}
2 r$ P1 |& j; |( ^ while(1) {
  printf("\n请输入销地个数：");
  scanf("%d",&amp;num_b);
  E6 ?! B- e$ C0 W1 V  for(i=1;i&lt;=num_b;i++) {
2 y3 K  G* X% e   printf("B%d销量：",i);
   scanf("%lf",&amp;b);
) R: r9 i& I$ p  }
" Y1 ]; B# |# `  for(i=1;i&lt;=num_b;i++) printf("B%d销量：%lg\t",i,b);
  printf("\n正确吗？：(y/n)");
& b$ ~: P) z9 p& u  getchar();
1 U" h3 \: S0 {! y* L1 y  confirm=getchar();
  if (confirm=='y') break;
( _; m" o/ c  I  else if(confirm=='n') continue;
}
putchar('\n');
$ ]8 U" h8 o) L' u) K 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]);
  }
6 b% r5 F/ u/ D3 T  for(j=1;j&lt;=num_b;j++) printf("A%d到B%d：%lg\t",i,j,ab[j]);
/ V( c9 ]. A; @9 C. S5 z7 L  printf("\n正确吗？：(y/n)");
+ t# p5 W- M4 R: I  getchar();
- N" v* E0 ^% `0 ~5 G  confirm=getchar();
  if(confirm=='n') i--;
  putchar('\n');
$ X1 W$ ?2 b& [- n( d6 P- K. ? }
% _  Z  N; k7 j4 |% y0 R //处理产销不平衡的情况
sum_a=sum_b=0;
for(i=1;i&lt;=num_a;i++) sum_a+=a;
/ d7 [/ N# c! G& a6 C. m  J for(i=1;i&lt;=num_b;i++) sum_b+=b;</P>
/ q. S' ^7 s6 ]0 P9 I<> printf("总产量：%lg\t总销量：%lg",sum_a,sum_b);
if(sum_a==sum_b) printf("\t产销平衡。");
# e& ~5 F& j* V1 L' k! t8 ^0 ` else if(sum_a&gt;sum_b) {
  printf("\t供大于求，增加假想销地B%d。\n",++num_b);
( r( \8 |9 M! H! C1 G  b[num_b]=sum_a-sum_b;
& y# x7 C& O- C: k4 r  for(i=1;i&lt;=num_a;i++) ab[num_b]=0;
}
( |0 R/ b) {& i$ B$ v+ _; J else if(sum_a&lt;sum_b){
  printf("\t供不应求，增加假想产地A%d。\n",++num_a);
" K- ?7 O8 h- Y; O  a[num_a]=sum_b-sum_a;
2 P  \7 a  c; x9 }, A  {  for(i=1;i&lt;=num_b;i++) ab[num_a]=0;
! l$ c' Z, q2 T* ]3 ^9 p0 _; ]9 h }
. m$ f# `; h4 ~$ J$ D //求解前的准备
& I! Y/ ~5 H5 A3 |4 q4 }7 c1 ?# w for(i=1;i&lt;=num_a;i++)
  for(j=1;j&lt;=num_b;j++)
   base[j]=pbase[j]=0;
) h4 e& _* _2 m4 n( Z" X for(i=1;i&lt;=num_a;i++) temp_a=a;
for(i=1;i&lt;=num_b;i++) temp_b=b;
/ A: h9 S  P) t- @# a7 Q for(i=1;i&lt;=num_a;i++)
4 y6 ^" R) B% k for(j=1;j&lt;=num_b;j++) temp_ab[j]=ab[j];
0 x6 m7 b1 z# f //回显问题
printf("\n\n原问题为：\n\n");
   printf("产量：\n ");
for(i=1;i&lt;=num_a;i++) printf("A%d:%lg\t",i,a);
2 h! L8 G) v6 R) ~5 t) ?0 w2 g9 I printf("\n运量：\n ");
" V. J8 u- s  L" B for(i=1;i&lt;=num_b;i++) printf("B%d:%lg\t",i,b);
* K9 i1 |) m# z2 g1 h printf("\n运价为：\n");
for(i=1;i&lt;=num_a;i++) {
  putchar(' ');
  for(j=1;j&lt;=num_b;j++)
1 [  F7 I4 ?$ ?0 K& p) E% i   printf("A%d-&gt;B%d:%lg\t",i,j,ab[j]);
  putchar('\n');
( x* v" s2 m/ I  I* N, e* K }
  }9 p1 y8 n0 m: _3 h}</P>
<>double dabs(double d) {
if(d&gt;=0) return d;
else return -d;
/ y! T4 w) }! B}</P>
, w  w& B; D3 \; R2 Z# p5 j<>void findinit() {
4 |7 x4 M! i  i int i,j,k;
double r_penum[MAX],c_penum[MAX];
struct largest {
5 L6 P  ^  C5 \- ?8 d/ {. O  char rc;
  int num;
  double value;
2 Z9 R5 }4 \# x. o1 U5 i7 u) S" q };
struct largest lar1,lar2;
int r=0,c=0;
" E" ?' C$ t+ s( P% A3 n" l double a1,a2,b1,b2,temp;</P>
8 s  j6 l6 Z+ |" D<> for(i=1;i&lt;=num_a;i++) {
  temp=temp_ab[1];
  for(j=1;j&lt;=num_b;j++)
8 W: `+ H. Y3 a   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
  a1=a2=temp;
' @' E" c, O$ W  for(j=1;j&lt;=num_b;j++)
   if(temp_ab[j]&lt;=a1) {
6 ^! O0 Y' n9 y3 G    a2=a1;
    a1=temp_ab[j];
; [% f2 P6 @/ o4 S6 |6 c4 _8 ^   }
: J# H, c1 s. e   else if(temp_ab[j]&lt;=a2) a2=temp_ab[j];
, s: c+ c2 ]# B' H  r_penum=dabs(a1-a2);
}</P>
* n, r  |3 L' K% M<> for(i=1;i&lt;=num_b;i++) {
7 q* u1 J# n% I  temp=temp_ab[1];
, O3 g" l- |- `& U) x! h) e  for(j=1;j&lt;=num_a;j++)
" K) C3 ]0 ^$ K+ z) d& p- T" H% R   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
  b1=b2=temp;
  for(j=1;j&lt;=num_a;j++)  
   if(temp_ab[j]&lt;=b1) {
    b2=b1;
3 I" C6 `- L* V$ k2 J) [, G    b1=temp_ab[j];
0 U4 Q6 f9 ]% \  k# s5 U   }
   else if(temp_ab[j]&lt;=b2) b2=temp_ab[j];
  c_penum=dabs(b1-b2);
/ E% H- K1 K1 ~4 A1 Q }
/*
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);
  q$ d  J0 P  `( v& Y/ e */
/ O, [) m: F4 t( e temp=r_penum[1];
+ a( K4 R% l! B4 j4 J 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>
<> //考虑了有两个罚数相等的情况，大于两个相等只取其中两个进行比较
5 h3 }$ s) ^4 l5 p( U$ k lar1.value=lar2.value=temp;
4 i( F0 e  S, f9 u1 f7 j lar1.num=lar2.num=1;
7 ~  c8 H  [/ p0 ^9 n$ I lar1.rc=lar2.rc='r';
3 t7 _( S; [; I1 x3 Q* _ for(i=1;i&lt;=num_a;i++)
  if(r_penum&gt;=lar1.value) {
, N4 i' m) W2 N: O) f- t% s- [   lar2=lar1;
   lar1.rc='r';
   lar1.num=i;
0 _' i( |! [: h* [   lar1.value=r_penum;
  }
  else if(r_penum&gt;=lar2.value) {
   lar2.rc='r';
   lar2.num=i;
  w" y, `# `' R/ }   lar2.value=r_penum;
  }</P>
7 m" H& a. H) p; U4 T6 P1 Q( x<> for(i=1;i&lt;=num_b;i++)
  if(c_penum&gt;=lar1.value) {
+ z3 ]1 {) M) r' Y   lar2=lar1;
( X6 {; R8 e5 W+ n. ^& Z   lar1.rc='c';
2 H/ y. ^0 J- Q   lar1.num=i;
   lar1.value=c_penum;
# U! r2 D5 f5 D" ]. {$ E  }
; r2 e2 q6 C5 s; G7 r% A) s  else if(c_penum&gt;=lar2.value) {
   lar2.rc='c';
; E) H% n& \+ w8 b9 A, v   lar2.num=i;
   lar2.value=c_penum;
  }</P>
<> if(lar1.value==lar2.value&amp;&amp;(lar1.num!=lar2.num||lar1.rc!=lar2.rc)) {
/ d4 d6 C- y" h% f6 A! l6 i  if(lar1.rc=='r'&amp;&amp;lar2.rc=='r') {
   temp=temp_ab[lar1.num][1];
1 i/ {6 g& s% A4 {# @1 K2 q9 Q* {   r=lar1.num;
- b7 L% ]4 N* u& Y5 H/ A- ~+ V) `      c=1;
   for(i=1;i&lt;=num_b;i++) {
    if(temp_ab[lar1.num]&lt;temp) {
2 K+ Q! J5 G* ?8 N6 q" t5 @, e* ]     temp=temp_ab[lar1.num];
3 U$ H& J3 F# t$ _7 r7 G9 y     r=lar1.num;
     c=i;
    }
    if(temp_ab[lar2.num]&lt;temp) {
: o6 T% m# J- D* t& x* G7 f     temp=temp_ab[lar2.num];
* K$ T# Z/ X  ~  M7 W* B     r=lar2.num;
     c=i;
    }
" U) ~; H3 g" I/ o+ w1 N5 H; [, l- ]) E9 Y   }
2 {1 b8 G$ l. V, T  }
  if(lar1.rc=='c'&amp;&amp;lar2.rc=='c') {
& [8 s# ]  i2 B: Q, n! u2 M; T   temp=temp_ab[1][lar1.num];
" \# @. k& j! M1 q# A; ^9 B; t1 p   r=1;
      c=lar1.num;
! D2 C- [4 q6 \+ W   for(i=1;i&lt;=num_a-1;i++) {
    if(temp_ab[lar1.num]&lt;temp) {
/ W$ R6 ]1 g' B% Y4 T2 X  t     temp=temp_ab[lar1.num];
     c=lar1.num;
     r=i;
% A2 n: Y3 Q% ^9 `- p( r    }
    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
     c=lar2.num;
     r=i;
    }
8 B! K6 V5 @/ L+ k" `1 N" d% w   }
+ {6 k: ]+ n" e5 T) X7 Q  }
" H- D1 D* e7 w  if(lar1.rc=='r'&amp;&amp;lar2.rc=='c') {
% d& D$ ]4 G" U; |; ]7 v% w   temp=temp_ab[lar1.num][1];
   r=lar1.num;
      c=1;
   for(i=1;i&lt;=num_b;i++)
    if(temp_ab[lar1.num]&lt;temp) {
     temp=temp_ab[lar1.num];
     r=lar1.num;
     c=i;
) z. B5 t! i& u3 Y    }
   for(i=1;i&lt;=num_a;i++)
5 l7 E  v* Q. ~1 B    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
     c=lar2.num;
     r=i;
    }
  }
  if(lar1.rc=='c'&amp;&amp;lar2.rc=='r') {
0 {# b( O6 o0 V9 F   temp=temp_ab[1][lar1.num];
   r=1;
+ r* c  g. H* ~      c=lar1.num;
   for(i=1;i&lt;=num_b;i++)
    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
     r=lar2.num;
     c=i;
    }
' |8 x" E3 J( U! t- c6 o! z. M( b   for(i=1;i&lt;=num_a;i++)
+ H/ n9 d$ U% ]3 e6 C+ @    if(temp_ab[lar1.num]&lt;temp) {
# {0 r! t0 {  D2 d+ P" Z& ]' C2 `* [     temp=temp_ab[lar1.num];
' v* W6 I1 b( h3 w0 D9 b     c=lar1.num;
     r=i;
7 R2 O6 {. K0 m' F2 W    }
  }
}
6 r  M4 g" X* w* E# i9 G else {
  if(lar1.rc=='r') {
4 H0 ?6 z3 R) r; w" ?( V( Q3 }   r=lar1.num;
2 O8 I* p6 z1 O8 ?' Q; w0 G   c=1;
   temp=temp_ab[lar1.num][1];
   for(i=1;i&lt;=num_b;i++)
    if(temp_ab[lar1.num]&lt;temp) {
# \5 L6 L6 E2 a+ y, O2 e0 o     c=i;
; f  D( n7 z+ E1 ?( w% g     temp=temp_ab[lar1.num];
    }
  }
  else {
   r=1;
   c=lar1.num;
; R7 _' \$ b3 r: I  q   temp=temp_ab[1][lar1.num];
   for(i=1;i&lt;=num_a;i++)
$ J" I) b0 z: p( [( Y2 c    if(temp_ab[lar1.num]&lt;temp) {
; Z) N2 s/ X2 ?     r=i;
     temp=temp_ab[lar1.num];
    }
  }
}
5 j, e5 ^" i  E7 a7 V pbase[r][c]=1;
if(temp_a[r]&gt;temp_b[c]) {
  base[r][c]=temp_b[c];
  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;
) A  i7 W( S1 a( W0 @, J }
else if(temp_a[r]&lt;temp_b[c]) {
  base[r][c]=temp_a[r];
  temp_b[c]=temp_b[c]-temp_a[r];
  temp_a[r]=0;
  for(i=1;i&lt;=num_b;i++) temp_ab[r]=M;
}
else if(temp_a[r]==temp_b[c]) {
" ^: P9 n# b4 b0 \3 }  base[r][c]=temp_a[r];
8 y; K% \1 @5 |6 {  temp_a[r]=temp_b[c]=0;
# y: y$ U7 z4 h7 u  for(i=1;i&lt;=num_a;i++) temp_ab[c]=M;
  for(i=1;i&lt;=num_b;i++) temp_ab[r]=M;
3 L) N) G# l* s6 }  k=0;
' Y1 V8 b/ I: o  p2 x8 q; z  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) {
   k=0;
3 Q, ], Z! S" R- t9 p; A& {   for(i=1;i&lt;=num_a;i++) if(pbase[c]!=1) {k=1;break;}
   for(j=1;j&lt;=num_b;j++) if(pbase[r][j]!=1) {k=2;break;}
   if(k==1) pbase[c]=1;
. X- g2 V# E, I0 k& l2 l8 T   else if(k==2) pbase[r][j]=1;
  }
}
k=0;
& k& \- h$ ~' s/ g3 a 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) return;
* T) G/ M2 m, Z  \9 s: S findinit();
4 e( P" L+ O8 O0 ]}</P>
5 K0 m+ }) j1 P' L0 F<>void computeuv() {
! N0 r* F2 Z/ M$ M4 R, I int i,j,k;
for(i=1;i&lt;=num_a;i++)
  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==1) {
$ N$ H+ o0 c. D# o2 t" n+ d& B& b% |    if(pu==1) {v[j]=ab[j]-u; pv[j]=1;}
& {/ x0 `* F$ O) O1 H* F    if(pv[j]==1) {u=ab[j]-v[j]; pu=1;}
   }
k=0;
for(i=1;i&lt;=num_a;i++) if(pu==0) k=1;
* x2 Q; N5 J0 l* e; ~9 r for(i=1;i&lt;=num_b;i++) if(pv==0) k=1;
if(k==1) computeuv();
}</P>
& J7 q7 y( @% b; O, G( {' T0 K<>int check() {
int i,j,k,l;
. P2 |8 ^; }& z' @0 Q9 m k=l=0;
' j' U) L9 N) F. _ for(i=1;i&lt;=num_a;i++)
  for(j=1;j&lt;=num_b;j++)
% I( q! H7 k4 q+ @5 y- Y1 B! j* l/ X   if(pbase[j]==0) {
    base[j]=ab[j]-u-v[j];
, D  M  e: X, F7 r9 D/ `. D    if(base[j]&lt;0) k=1;
% E$ V8 F" M1 O) K; ?/ i6 S    else if(base[j]==0) l=1;
   }
# A8 W+ z1 ?. W$ {4 ~+ i/* for(i=1;i&lt;=num_a;i++){
  for(j=1;j&lt;=num_b;j++) printf("base %lg\t",base[j]);
, m5 Q: M4 s* w- v+ @2 z  putchar('\n');}
8 W. w: S2 ~/ X8 \2 l+ ] for(i=1;i&lt;=num_a;i++){
  for(j=1;j&lt;=num_b;j++) printf("pbase %d\t",pbase[j]);
  putchar('\n');}
*/
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>
<>int circle(enum direction dir,struct element cir[],int *t) {
int i,j,k;
9 M- U* x  h" t& i, @$ X /*
8 i) c2 }! o3 b0 J0 [ putchar('\n');
for(i=1;i&lt;=*t;i++) printf("%d: r%d c%d\t",i, cir.r,cir.c);
putchar('\n');
*/
if((*t)!=1&amp;&amp;cir[(*t)].r==cir[1].r&amp;&amp;cir[*t].c==cir[1].c) {
  D5 Z* k5 z0 X  U* k  t--;
  return 1;
}
1 [7 k3 A8 C) Y; W if(dir!=down) {
  k=0;
  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;}
  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;
" D. e) e6 l  \5 y- V& A" F/ L   else cir[*t].value=1;
/ v, H2 g/ g4 e- o   (*t)++;
! j# x7 F0 F  ^* G   cir[*t].r=i;
   cir[*t].c=cir[(*t)-1].c;
0 z' `6 B& k- q) K/ }8 X, `4 Z   if(circle(up,cir,t)) return 1;
  }
}
5 o4 S' b! `2 |5 }) g if(dir!=up) {
  k=0;
* L% ~, d" p  T! O  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;
0 R/ a" N, q6 [' E; C, d3 Q  if(k==1) {
8 t6 f  a" _# r7 y- b9 J: k$ Y  |( U   if(dir==down) cir[*t].value=0;
   else cir[*t].value=1;
$ _/ ^) H3 `  d& Z6 }6 m& l   (*t)++;
2 m$ z" h: H; c( J3 ]+ K   cir[*t].r=i;
4 J+ ?2 E" K5 M+ t9 l) Q! z   cir[*t].c=cir[(*t)-1].c;
   if(circle(down,cir,t)) return 1;
4 B4 X, k; e* E& m# S2 F% R3 Y8 }0 l  }
}
if(dir!=right) {
# R& Z6 C1 }, ]3 R- S# A2 S) R% M  k=0;
  W3 a7 X' o* @: B  for(i=cir[*t].c-1;i&gt;=1;i--)
3 o) h) R; |) ?   if(pbase[cir[*t].r]==1||(cir[*t].r==cir[1].r&amp;&amp;i==cir[1].c)) {k=1; break;}
, g: V/ i7 V4 N3 P  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) {
! D( k2 A& B6 j5 J. |7 N8 M   if(dir==left) cir[*t].value=0;
) Y" l& R5 W- D) l7 t# F- }5 P; J   else cir[*t].value=1;
   (*t)++;
   cir[*t].r=cir[(*t)-1].r;
; ~2 Z3 e* `( j# K6 P1 b   cir[*t].c=i;
: g7 l2 |% b4 P, ]5 H3 e) _   if(circle(left,cir,t)) return 1;
  }
}
2 O+ V( H( Z) ^" v  V$ L! h1 t if(dir!=left) {
7 l( K! `8 z2 x1 ^( g1 k  k=0;
. D; `+ ~( K6 Y  X8 J  for(i=cir[*t].c+1;i&lt;=num_b;i++)
2 F: k7 O' ]$ W& n' u* t   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;
8 {6 R9 s' H( r: `5 n  if(k==1) {
   if(dir==right) cir[*t].value=0;
/ u, B* D+ ?  O5 z2 I9 g+ x   else cir[*t].value=1;
6 E9 j  w& h4 r& D   (*t)++;
   cir[*t].r=cir[(*t)-1].r;
   cir[*t].c=i;
   if(circle(right,cir,t)) return 1;
$ ?- F8 M& C0 Y5 L8 R1 _/ c  }
}
(*t)--;
return 0;
4 ~, H1 g% E3 {6 _9 O( B}</P>
4 P  G3 ^- L5 q* F8 b, G<>void improve() {
int i,j,k,t;
struct element base_in,base_out,cir[2*MAX+1];</P>
<> for(i=1;i&lt;=num_a;i++) pu=0;
' Z7 z6 K* I3 L) s& w% H for(i=1;i&lt;=num_b;i++) pv=0;
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++)
+ ?0 @2 t7 z- r* ]% U% {6 M. f   if(pbase[j]==0) break;
base_in.r=i;
, n4 P8 ~: W! |# D base_in.c=j;
base_in.value=base[j];</P>
<> for(i=1;i&lt;=num_a;i++)
8 T9 _+ Z! B0 P% J  for(j=1;j&lt;=num_b;j++)
5 A6 i; ]1 @4 A" }   if(pbase[j]==0&amp;&amp;base[j]&lt;base_in.value) {
    base_in.r=i;
  ]8 I: [+ ^$ d' O1 [. S. d. c    base_in.c=j;
# G) t( t3 g3 @6 _$ L9 v    base_in.value=base[j];
5 F! K4 P# j* K$ P   }</P>
- C: O3 `# d+ X0 s( V. p5 q<> t=1;
; Z$ b/ Z  h3 E" v. e: g cir[t].r=base_in.r;
cir[t].c=base_in.c;
cir[t].value=1;
if(!circle(mid,cir,&amp;t)) {
9 o  M- n# E8 a. t+ a2 X  printf("程序出错！按回车结束");
  getchar();
) a6 V- t5 \( I1 [. j  exit(0);
}
3 [! a" f; X- @/ S& [ t--;
// 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];
! W7 [- d5 }' U: C: n k=1;
3 S- y! b$ P  @* a: v5 H$ C 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;
" ]* W8 R9 D  I' R+ P0 y1 o   base_out.value=base[cir.r][cir.c];
0 `) q4 {/ @/ V( m! D% K   k++;
  }
' b' `5 j. z+ d6 s' w' T, j  else if(cir.value==1) k++;
base[cir[1].r][cir[1].c]=0;
k=1;
1 n( y7 d" ^- r for(i=1;i&lt;=t;i++) {
  if(k%2==1&amp;&amp;cir.value==1) {
   base[cir.r][cir.c]+=base_out.value;
: ^& A% y) U& y   k++;
  }
, j5 S# _! f* m' v  o  else if(k%2==0&amp;&amp;cir.value==1) {
   base[cir.r][cir.c]-=base_out.value;
   k++;
  }
}
pbase[base_out.r][base_out.c]=0;
pbase[base_in.r][base_in.c]=1;</P>
0 p6 p5 d$ D1 E' Z5 w' }<> improve();
}</P>
<>void output() {
" J: z" m' W1 C/ v9 a6 z( o& l int i,j;
: T, E" q& d1 P) B9 S double sum=0;
printf("\n运量为：\n");
for(i=1;i&lt;=num_a;i++) {
: a; [1 `: J2 }3 b  J2 O3 n  putchar(' ');
' j* P* p. O) r* e5 Y  j/ E: K  for(j=1;j&lt;=num_b;j++)
9 [7 a7 e) o/ r. U% \! T; ]& }/ l6 f/ _   if(pbase[j]==1) {
    printf("A%d-&gt;B%d:%lg\t",i,j,base[j]);
1 `9 f, v8 |( \    sum+=base[j]*ab[j];
   }
) J* c  N0 R7 ^& ^( W   else printf("A%d-&gt;B%d:0\t",i,j);
' j2 v6 v, t6 N  putchar('\n');
}
printf("\n最低总运费为：%lg\n",sum);
9 r8 ^3 W8 @" _1 j" [( k}
</P>

zhongguohelin

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

enrique08

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

hzlhm

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

liunengwu

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