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

plgatc

<>/*************************************************************************
                         表上作业法解运输问题        
/ n3 q) |1 r: T8 ^
+ Y% z: @  S/ I$ H! t9 k& x 编程环境：VC++6.0     
) A$ x: ~$ l9 [. [6 X, X, L 程序说明：
Vogel法求初始解，位势法检验是否最优，递归搜索闭回路改进解。
3 y3 \. L: z- S8 ]" H1 f, q *************************************************************************/
#include &lt;stdio.h&gt;
* [8 c: u) I2 ?6 q! y% ]#include &lt;stdlib.h&gt;</P>
# Y5 A% J" R4 ?) @8 ]: h<>#define MAX 100
% t5 a; q4 u/ O#define M 999999</P>
+ V4 N1 O* t. b6 z. |1 h<>int status; //1唯一最优解，-1无穷多最优解</P>
4 \8 L( O1 B: f+ A5 b( d<>int num_a,num_b;
double a[MAX],b[MAX],temp_a[MAX],temp_b[MAX];
' c" `8 c4 U; x& Odouble u[MAX],v[MAX],pu[MAX],pv[MAX];
double ab[MAX][MAX],temp_ab[MAX][MAX];
% I$ ?' n# S9 p/ m- hdouble base[MAX][MAX];
int pbase[MAX][MAX];
4 D* A# }) \# x% E: Qstruct element {
int r;
! x6 t& U5 q8 p int c;
double value;
/ @* w  p( w7 \/ R5 u. f- C$ u};
: ]/ ^2 d$ m! Q9 }% K/ V3 renum direction {mid,up,down,left,right};</P>
<>void create();
void banner();
double dabs(double d);
( `  ~  d  `5 W& ovoid findinit();
void computeuv();
int check();
int  circle(enum direction dir,struct element cir[],int *t);
void improve();
2 a. c2 v# n; u, i, Jvoid output();</P>
<>void main() {
banner();
) e4 I* N0 s# b6 R, H create();
printf("\n按回车确认后开始求解");
getchar();
5 X1 c' k( r$ K  C7 I% Q) _  V! f getchar();
5 ?- Q" @/ K: G0 i2 n3 g1 i findinit();
improve();
' O4 V* r- y! B. e$ T switch(status) {
7 p8 S" l# m% E! [6 u case 1:
4 m, v2 w/ {$ j  output();
  puts("\n原问题有唯一最优解。\n");
  puts("\n按回车结束");
  getchar();
8 j1 D# i8 e5 f+ @$ A7 C' v  exit(0);
) O: z0 d1 r& u" e5 {% p case -1:
  output();
5 R5 X5 A) C+ g: W/ [  puts("\n原问题有无穷多最优解。\n");
  puts("\n按回车结束");
  getchar();
  exit(0);
0 l  ?" I: _* g% V! c$ X$ g" l2 } }
/ N; L* ^, G( B7 |" Y. S}</P>
9 N, u% Q- R2 Q. I& x6 h% E6 ]<>void banner() {
& L2 a; _3 s! E* m  u) C( y printf("\t\t****************************************\n");
printf("\t\t         表上作业法解运输问题\n");
printf("\t\t                              Thunder\n");
: G, @: F1 O3 h+ ] printf("\t\t****************************************\n");
printf("\n");
}</P>
<>void create() {
int i,j;
& F2 y2 h  U, ~5 Q double sum_a,sum_b;
  ]2 v7 P1 x# I+ `6 f char confirm;
while(1) {
! I- O% {) w. e  c  printf("请输入产地个数：");
& g$ h" G# L$ ~- B6 V# o) s  scanf("%d",&amp;num_a);
3 d+ g: U2 x4 S# N- K  for(i=1;i&lt;=num_a;i++) {
   printf("A%d产量：",i);
2 x% L8 M* ~& \   scanf("%lf",&amp;a);
) n; D$ f8 _* M$ x; v. F) _; W  }
  for(i=1;i&lt;=num_a;i++) printf("A%d产量：%lg\t",i,a);
0 m9 y8 z+ J9 l3 V: w9 c  printf("\n正确吗？：(y/n)");
  getchar();
  confirm=getchar();
  if (confirm=='y') break;
9 B2 P9 h) J, |. z7 k# `  else if(confirm=='n') continue;
}
while(1) {
  printf("\n请输入销地个数：");
  scanf("%d",&amp;num_b);
" G7 @. ^, `3 z- Y  d/ w  for(i=1;i&lt;=num_b;i++) {
   printf("B%d销量：",i);
   scanf("%lf",&amp;b);
5 E. Y) t" e7 ^" A  }
  for(i=1;i&lt;=num_b;i++) printf("B%d销量：%lg\t",i,b);
  printf("\n正确吗？：(y/n)");
  getchar();
  confirm=getchar();
5 ], b: i( o: y3 n  if (confirm=='y') break;
6 T, O! f; H# K  H5 S) d- \1 v  else if(confirm=='n') continue;
5 \. g9 z, O5 ^- { }
3 F. j: W! W% P' e' G0 R$ g putchar('\n');
for(i=1;i&lt;=num_a;i++) {
  z* V' x9 v$ M( `0 s  for(j=1;j&lt;=num_b;j++) {
' \; Q3 N; U. A; x: D( P- S   printf("A%d到B%d运价：",i,j);
2 h6 g8 }  K: d2 V   scanf("%lf",&amp;ab[j]);
, h$ w, p4 J/ f5 e- g  }
  for(j=1;j&lt;=num_b;j++) printf("A%d到B%d：%lg\t",i,j,ab[j]);
  printf("\n正确吗？：(y/n)");
# g; X5 Y4 f# l4 o# j( {  getchar();
+ M- f1 ^# W% @4 r6 T& D2 e1 g2 m  confirm=getchar();
  if(confirm=='n') i--;
  putchar('\n');
}
1 d* }) N' _& ^ //处理产销不平衡的情况
sum_a=sum_b=0;
) w* z  Q* r" [& J3 E% C5 f for(i=1;i&lt;=num_a;i++) sum_a+=a;
for(i=1;i&lt;=num_b;i++) sum_b+=b;</P>
<> printf("总产量：%lg\t总销量：%lg",sum_a,sum_b);
% S0 e! z2 J2 l( w5 k! R& I9 E if(sum_a==sum_b) printf("\t产销平衡。");
  q5 W" s7 B5 F; D' j else if(sum_a&gt;sum_b) {
  printf("\t供大于求，增加假想销地B%d。\n",++num_b);
  b[num_b]=sum_a-sum_b;
  for(i=1;i&lt;=num_a;i++) ab[num_b]=0;
& u1 D9 C% B9 _ }
else if(sum_a&lt;sum_b){
$ b& t' D& H$ w; x  printf("\t供不应求，增加假想产地A%d。\n",++num_a);
  a[num_a]=sum_b-sum_a;
  for(i=1;i&lt;=num_b;i++) ab[num_a]=0;
; Z  r, ?; ~' [( [5 \ }
//求解前的准备
+ e% L) e6 }3 J. T% }! m; d for(i=1;i&lt;=num_a;i++)
- R  P8 `: A' O& G  for(j=1;j&lt;=num_b;j++)
" V* [( B/ x. n6 C% Z   base[j]=pbase[j]=0;
! G5 [# ^, o! |) }* A for(i=1;i&lt;=num_a;i++) temp_a=a;
  @9 D! O9 f3 R9 f$ J. o8 J for(i=1;i&lt;=num_b;i++) temp_b=b;
for(i=1;i&lt;=num_a;i++)
for(j=1;j&lt;=num_b;j++) temp_ab[j]=ab[j];
; J) g2 k; f  m //回显问题
printf("\n\n原问题为：\n\n");
2 d% S$ P5 [8 @! K/ c   printf("产量：\n ");
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");
( b" R" D% z3 |. H) { for(i=1;i&lt;=num_a;i++) {
8 W, A* E, [0 n  putchar(' ');
  for(j=1;j&lt;=num_b;j++)
   printf("A%d-&gt;B%d:%lg\t",i,j,ab[j]);
+ U& F4 P4 E0 C  putchar('\n');
4 r; r' }3 f" t; D }
' Q. j9 Y9 ^4 G}</P>
<>double dabs(double d) {
if(d&gt;=0) return d;
; D. E( R; R4 o7 Q/ q else return -d;
}</P>
<>void findinit() {
int i,j,k;
double r_penum[MAX],c_penum[MAX];
! g0 B3 O3 p9 b, w) n+ A1 N2 |2 X* ^ struct largest {
  char rc;
  int num;
  double value;
! P# b, Q* V/ d- O  N2 n- h };
struct largest lar1,lar2;
% A: Y, T! A1 q2 G/ B  ^# Y. v8 N3 i int r=0,c=0;
6 S" }/ V* ?. m/ n3 i* [# ]- o double a1,a2,b1,b2,temp;</P>
<> for(i=1;i&lt;=num_a;i++) {
  temp=temp_ab[1];
  for(j=1;j&lt;=num_b;j++)
   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
  a1=a2=temp;
  for(j=1;j&lt;=num_b;j++)
   if(temp_ab[j]&lt;=a1) {
! M* t5 s4 d( R* U    a2=a1;
+ }! {9 D7 Q* q4 a% m    a1=temp_ab[j];
% j. w5 C: i- o* X5 E3 U   }
   else if(temp_ab[j]&lt;=a2) a2=temp_ab[j];
: |% c4 ^% l3 I7 l, [& r6 h  r_penum=dabs(a1-a2);
2 p& h# f& i! v# q }</P>
<> for(i=1;i&lt;=num_b;i++) {
5 a* k' D) i$ V( \# {" k  temp=temp_ab[1];
  for(j=1;j&lt;=num_a;j++)
   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;
7 s' p  W( n  `5 `* x" ^9 @* x8 |9 E; A    b1=temp_ab[j];
   }
7 T- E% a, e" t( V+ F   else if(temp_ab[j]&lt;=b2) b2=temp_ab[j];
  c_penum=dabs(b1-b2);
2 l9 `1 A% V# \* U' u }
/*
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);
! @' j( N% t5 ~3 |7 h7 R */
3 d) \. N5 L" H+ A3 L/ D! x temp=r_penum[1];
for(i=1;i&lt;=num_a;i++) if(r_penum&lt;temp) temp=r_penum;
( |- I# P9 |) W$ \' @3 d) x; [ for(i=1;i&lt;=num_b;i++) if(c_penum&lt;temp) temp=c_penum;</P>
/ a! J5 G. Z- ^* t# V<> //考虑了有两个罚数相等的情况，大于两个相等只取其中两个进行比较
* o2 x  l* ~% |) P% j' F$ ^ lar1.value=lar2.value=temp;
  L- H( M2 K  g' j% v lar1.num=lar2.num=1;
lar1.rc=lar2.rc='r';
for(i=1;i&lt;=num_a;i++)
  if(r_penum&gt;=lar1.value) {
   lar2=lar1;
3 n3 B7 m, V" |7 e# Y  ~) ]1 Q   lar1.rc='r';
% d. ~  `) Q# y! S0 Y$ w/ l! g   lar1.num=i;
   lar1.value=r_penum;
  }
; K! N9 p/ l1 v6 ~  else if(r_penum&gt;=lar2.value) {
   lar2.rc='r';
/ ^1 g: C, L' z; |# ?6 J9 P' ]   lar2.num=i;
   lar2.value=r_penum;
  }</P>
% A8 m8 a  Q; e7 ^+ O' w4 |<> for(i=1;i&lt;=num_b;i++)
  if(c_penum&gt;=lar1.value) {
   lar2=lar1;
   lar1.rc='c';
   lar1.num=i;
   lar1.value=c_penum;
- p+ g! V5 r8 E  K  }
  else if(c_penum&gt;=lar2.value) {
. D$ g1 t" _: g+ R5 B2 d& b   lar2.rc='c';
   lar2.num=i;
   lar2.value=c_penum;
  }</P>
, k/ m: J3 B# c, T<> if(lar1.value==lar2.value&amp;&amp;(lar1.num!=lar2.num||lar1.rc!=lar2.rc)) {
  if(lar1.rc=='r'&amp;&amp;lar2.rc=='r') {
3 R9 L9 t' q- z) w6 p& a. E( H+ g   temp=temp_ab[lar1.num][1];
   r=lar1.num;
; I' }$ D( [( P& }$ w      c=1;
* I, w9 g6 B4 `/ G! ?   for(i=1;i&lt;=num_b;i++) {
! ]# o3 h" c9 Q$ ^) o# W    if(temp_ab[lar1.num]&lt;temp) {
     temp=temp_ab[lar1.num];
) h2 \* y! o" B1 x+ s     r=lar1.num;
     c=i;
    }
' G" a* F+ e. \    if(temp_ab[lar2.num]&lt;temp) {
$ ~( T) c1 d- a. H0 o     temp=temp_ab[lar2.num];
     r=lar2.num;
8 G: s( q2 h& U9 Y     c=i;
& }& J7 S6 ^0 U6 ^    }
   }
9 x2 L+ s! Q" p# l2 p" O7 O  }
  if(lar1.rc=='c'&amp;&amp;lar2.rc=='c') {
- l1 O# P" V' d6 K$ F$ ~) |5 A   temp=temp_ab[1][lar1.num];
   r=1;
      c=lar1.num;
9 \2 m6 x9 a2 n  W/ b   for(i=1;i&lt;=num_a-1;i++) {
) k! F( V4 G# s) e1 x# Y4 ~( p    if(temp_ab[lar1.num]&lt;temp) {
) X1 |8 b* B6 l6 R& y$ x9 e     temp=temp_ab[lar1.num];
5 `' A; F# u- i     c=lar1.num;
     r=i;
    }
' i! q6 n; S  Y7 A' ^    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
+ N8 _5 P& y0 p# Q: N     c=lar2.num;
     r=i;
    }
$ Z8 x/ Z% A8 q3 g   }
2 m! [4 a2 D  N1 B  }
  if(lar1.rc=='r'&amp;&amp;lar2.rc=='c') {
5 L( H) c5 y8 \" _   temp=temp_ab[lar1.num][1];
' L% I( G* ]7 U5 o   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];
- D# b+ c5 F8 R, ?5 O* C     r=lar1.num;
5 w& E" l9 e- ?! o/ y9 \$ _6 u2 O( C     c=i;
    }
0 b- q  m  c# I& U   for(i=1;i&lt;=num_a;i++)
    if(temp_ab[lar2.num]&lt;temp) {
- P  f* E, S. v! P     temp=temp_ab[lar2.num];
     c=lar2.num;
     r=i;
    }
  }
( M0 v5 @6 O$ D3 q* I( O% E  if(lar1.rc=='c'&amp;&amp;lar2.rc=='r') {
, ?, e' k" c6 L3 A   temp=temp_ab[1][lar1.num];
' H1 G" ^- y+ z   r=1;
      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;
  a+ A6 K5 }- d5 g$ `: w9 H    }
3 b$ `7 ?) `* g! l0 |6 S  ^% }   for(i=1;i&lt;=num_a;i++)
. [; x8 `8 d5 r5 w' U+ t- C- h    if(temp_ab[lar1.num]&lt;temp) {
     temp=temp_ab[lar1.num];
3 l  K. |# v* ?3 T; M- o* ~     c=lar1.num;
     r=i;
, R0 }+ R" J/ l* d* W    }
1 x/ H' w" w+ H0 ~5 A% o% [, J/ l  }
  |+ X: Y" n, R }
else {
  if(lar1.rc=='r') {
/ k1 k2 _& d; f: F0 g   r=lar1.num;
   c=1;
$ x1 k! k; w7 t" [" b/ P) X   temp=temp_ab[lar1.num][1];
0 S5 d. M4 O4 j# ^: L$ c   for(i=1;i&lt;=num_b;i++)
  f; p1 _: c( ?# T7 k    if(temp_ab[lar1.num]&lt;temp) {
6 Z9 V' D9 U0 h. p! ?     c=i;
     temp=temp_ab[lar1.num];
' `! Y* B- d- A& H    }
7 }( ]8 q8 c$ h- H7 n+ x' \1 d  }
: _6 s, F& F$ j  else {
* E1 a* h- {) `. q" D   r=1;
+ Y: h$ [1 H* u; C9 M/ _8 S. {/ l+ P   c=lar1.num;
   temp=temp_ab[1][lar1.num];
   for(i=1;i&lt;=num_a;i++)
    if(temp_ab[lar1.num]&lt;temp) {
. t' x5 h, H( N$ I- u) l  H5 T) y     r=i;
     temp=temp_ab[lar1.num];
! U. ?2 F3 d3 H  Y. H$ K* i! z    }
  }
, D" l8 `  h& }+ Y- W }
pbase[r][c]=1;
if(temp_a[r]&gt;temp_b[c]) {
5 }8 ~- O: \: R' O0 j  base[r][c]=temp_b[c];
) C( R4 ]4 U3 M3 A" P  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;
. e( C3 L- f6 \2 n: x& e }
else if(temp_a[r]&lt;temp_b[c]) {
: }2 ]. `/ V& z, w1 o9 [  base[r][c]=temp_a[r];
6 I# ^# N1 ?( E. h9 l  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;
7 I3 F; u- o8 `8 X }
9 w7 i; V' q  b: p else if(temp_a[r]==temp_b[c]) {
4 z0 Z* {5 `0 L  W5 N( ?' Y  base[r][c]=temp_a[r];
  temp_a[r]=temp_b[c]=0;
" P+ n" y* x8 q7 }3 v7 P- n  for(i=1;i&lt;=num_a;i++) temp_ab[c]=M;
2 U* ?% i6 [) V) Y, H8 Z  for(i=1;i&lt;=num_b;i++) temp_ab[r]=M;
  k=0;
# d1 o, p, ?! K  for(i=1;i&lt;=num_a;i++) if(temp_a!=0) k=1;
" n2 p$ h9 A" K& ~" C  for(i=1;i&lt;=num_b;i++) if(temp_b!=0) k=1;
  if(k!=0) {
7 }) e/ F/ E2 [4 S0 g   k=0;
4 u3 I# Q8 S' f   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;}
7 P, d! |& _8 x% [: ~* U. _. m  j9 \   if(k==1) pbase[c]=1;
0 z4 N* T/ ]# ^* }3 h9 K4 T. f   else if(k==2) pbase[r][j]=1;
  }
}
6 `1 g8 p+ Q& i& k2 X' M& t k=0;
( v, n+ W& U) I) }8 s 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;
+ u  e. h0 U/ |, Z0 f if(k==0) return;
findinit();
}</P>
. K) A- e) b7 m' h2 y5 A$ v: a<>void computeuv() {
! |, k0 U/ 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) {
5 I" K  h5 e* e+ I) }    if(pu==1) {v[j]=ab[j]-u; pv[j]=1;}
    if(pv[j]==1) {u=ab[j]-v[j]; pu=1;}
$ N6 I8 ]8 S; |: }8 i   }
k=0;
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();
}</P>
<>int check() {
& d& Z8 d% |& b* Q int i,j,k,l;
# [8 _5 N1 F1 [7 e. ^ k=l=0;
  ~! f( p/ R. a8 f( d for(i=1;i&lt;=num_a;i++)
7 M7 f9 q' e( L$ _' h/ ^7 Z  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==0) {
& p, D0 F6 e7 O* {- a' |6 A' H* l    base[j]=ab[j]-u-v[j];
    if(base[j]&lt;0) k=1;
1 J' D& t8 _3 C# `    else if(base[j]==0) l=1;
3 Q+ J" V- E) o  o0 _   }
. P# Z2 z" e6 T( s! a/* for(i=1;i&lt;=num_a;i++){
  for(j=1;j&lt;=num_b;j++) printf("base %lg\t",base[j]);
  putchar('\n');}
9 k! V6 \0 ]2 o) j9 A for(i=1;i&lt;=num_a;i++){
' ]- `" j+ w7 m5 e  for(j=1;j&lt;=num_b;j++) printf("pbase %d\t",pbase[j]);
  putchar('\n');}
% L0 \2 r% v) ^) _4 `*/
; w0 F6 _% l8 ~# M 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;
8 z! D$ F5 _8 G8 c3 |6 G! E) n/ P}</P>
<>int circle(enum direction dir,struct element cir[],int *t) {
int i,j,k;
( q% S6 |7 ]$ A2 P2 {% V- \, f /*
' Z+ J: f; e2 _9 S5 n' z putchar('\n');
for(i=1;i&lt;=*t;i++) printf("%d: r%d c%d\t",i, cir.r,cir.c);
9 r7 S+ R1 [9 S0 F6 Y4 T2 U putchar('\n');
" [% w3 S, Q  V& I5 H */
if((*t)!=1&amp;&amp;cir[(*t)].r==cir[1].r&amp;&amp;cir[*t].c==cir[1].c) {
& {; f" Q, V+ [0 N9 k  t--;
  return 1;
}
5 M+ |- w. I- w: N( r) _ if(dir!=down) {
  k=0;
  for(i=cir[*t].r-1;i&gt;=1;i--)
; m+ [1 N! h8 n6 k/ \! D/ w   if(pbase[cir[*t].c]==1||(i==cir[1].r&amp;&amp;cir[*t].c==cir[1].c)) {k=1; break;}
8 _; L3 A' m. D* \- O$ X  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) {
8 D$ @% x, X+ `* E9 \$ N' V2 ^   if(dir==up) cir[*t].value=0;
9 ^' n, a1 \% A: b1 b   else cir[*t].value=1;
   (*t)++;
+ d& F' f# q% S: f/ C/ Q2 a. _   cir[*t].r=i;
$ d2 A) g( i: T$ _7 z# K   cir[*t].c=cir[(*t)-1].c;
# S8 D" F7 z! R* X% _" o8 T   if(circle(up,cir,t)) return 1;
4 z) D8 B- t" O4 f" x  }
}
5 `5 b/ ~9 w# |2 ~ if(dir!=up) {
  k=0;
  for(i=cir[*t].r+1;i&lt;=num_a;i++)
) ~& U4 L; s$ d+ G5 N1 L   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;
1 j- r  ^3 m$ {7 a1 c& b5 {  ?  if(k==1) {
   if(dir==down) cir[*t].value=0;
5 S2 Q" K2 h1 c* b7 j) l0 v   else cir[*t].value=1;
   (*t)++;
$ I- |$ b0 N' h: E( R& ^   cir[*t].r=i;
4 A, H8 P& G# P; m% x8 @' {   cir[*t].c=cir[(*t)-1].c;
' H. ^5 i7 i9 H7 U' I3 f   if(circle(down,cir,t)) return 1;
  }
}
if(dir!=right) {
  k=0;
  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;
  if(k==1) {
   if(dir==left) cir[*t].value=0;
   else cir[*t].value=1;
   (*t)++;
; {* @2 l9 x/ j3 \, ?5 t  B   cir[*t].r=cir[(*t)-1].r;
   cir[*t].c=i;
6 H0 t. \$ `8 J, D6 {0 K   if(circle(left,cir,t)) return 1;
  }
2 p- o1 n1 t0 n6 B# I& t/ [ }
if(dir!=left) {
- l* d) h6 s  E* V4 y8 U  k=0;
8 j# h' T4 Y. o  P, p  for(i=cir[*t].c+1;i&lt;=num_b;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;
4 f+ _  K* r! c% a6 ~  if(k==1) {
   if(dir==right) cir[*t].value=0;
   else cir[*t].value=1;
   (*t)++;
: @! e& P+ ]6 a& D9 ]! n* F. r   cir[*t].r=cir[(*t)-1].r;
) O2 d' {! R+ ~   cir[*t].c=i;
3 z+ n7 a( @; J   if(circle(right,cir,t)) return 1;
* y$ h0 c2 n, N" L$ _* }* x1 p  }
& A% r9 {8 U& e4 V/ @ }
7 O; _+ j- i$ d9 e6 l( b (*t)--;
return 0;
6 U# W1 V) f3 ]}</P>
<>void improve() {
int i,j,k,t;
struct element base_in,base_out,cir[2*MAX+1];</P>
, s. |; d6 y$ K+ p3 u4 W8 [2 [<> for(i=1;i&lt;=num_a;i++) pu=0;
: G6 Y, ~" \7 D, X$ m9 x! L. ? for(i=1;i&lt;=num_b;i++) pv=0;
0 k9 U2 o$ b& J8 r( t u[1]=0; pu[1]=1;
% @4 z0 P" {$ K, C1 z computeuv();
if(check()) return;
for(i=1;i&lt;=num_a;i++)
) B" m4 @" Q; p4 t% \  for(j=1;j&lt;=num_b;j++)
; B, i6 r- u5 P   if(pbase[j]==0) break;
base_in.r=i;
- m+ |  K5 C- b7 ^0 z4 n. i. I base_in.c=j;
4 R& i. L3 D2 L: S  [9 i base_in.value=base[j];</P>
<> for(i=1;i&lt;=num_a;i++)
/ [/ `, b' [: G+ u  P( f# b  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==0&amp;&amp;base[j]&lt;base_in.value) {
& Y: M# T4 M7 c4 X3 h    base_in.r=i;
    base_in.c=j;
    base_in.value=base[j];
4 P+ C1 d( V& g2 A( M5 X   }</P>
$ N$ M- Q! r" J# d6 x9 X# _<> t=1;
cir[t].r=base_in.r;
  M' l6 n* _4 o$ v+ O7 r cir[t].c=base_in.c;
5 R2 x: T0 O  s cir[t].value=1;
  h$ h( S! W- G. F7 B$ k% z if(!circle(mid,cir,&amp;t)) {
& N8 T- e, |( ^5 Q5 Q4 @  printf("程序出错！按回车结束");
+ [9 ^4 H* n$ D; z# [# b' _  getchar();
  exit(0);
6 l% w; v, P7 r; O, l }
4 L$ X* c  C9 k5 V t--;
7 y7 M$ B1 s* D// for(i=1;i&lt;=t;i++) printf("%d:r%d c%d v%lg\t",i,cir.r,cir.c,cir.value);
9 |  z! x! F5 S4 h4 J6 `// putchar('\n');</P>
( I/ e, F) h- _$ [+ K+ E<> for(i=2;i&lt;=t;i++) if(cir.value==1) break;
base_out=cir;
1 h' s" q' N8 I  u base_out.value=base[cir.r][cir.c];
k=1;
" b! m$ }# h6 M# o: {7 a: t 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: x2 G7 a/ ]6 i; T6 M( h7 s   base_out.value=base[cir.r][cir.c];
9 N0 B& H0 A( \  f0 _0 p   k++;
  }
  @4 z+ K; Y% U  else if(cir.value==1) k++;
' m' k/ z+ [( D, ~( _+ l/ ~) Q base[cir[1].r][cir[1].c]=0;
k=1;
for(i=1;i&lt;=t;i++) {
  if(k%2==1&amp;&amp;cir.value==1) {
   base[cir.r][cir.c]+=base_out.value;
5 E1 m& E+ f. _3 q  W   k++;
4 {. y5 e- {1 L  b( W3 @1 \& x% `  }
  else if(k%2==0&amp;&amp;cir.value==1) {
5 i5 @- T' J* x6 u/ U   base[cir.r][cir.c]-=base_out.value;
   k++;
  }
; }, S3 p$ Q' y( L }
pbase[base_out.r][base_out.c]=0;
pbase[base_in.r][base_in.c]=1;</P>
3 ^8 r8 Z1 W: W0 @2 g% N<> improve();
}</P>
9 c9 Y' H& ?5 P5 Q% ]<>void output() {
int i,j;
double sum=0;
) f! g1 s0 D, t  E, v6 V! S; [. I printf("\n运量为：\n");
! k6 G& i2 J- _( I3 h" Z for(i=1;i&lt;=num_a;i++) {
  putchar(' ');
. E5 f; B- G* A) S  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==1) {
    printf("A%d-&gt;B%d:%lg\t",i,j,base[j]);
    sum+=base[j]*ab[j];
; W( f1 K; p, a8 v/ _+ r   }
  G' x. N0 @" Z   else printf("A%d-&gt;B%d:0\t",i,j);
0 z( p8 g" x$ g$ t1 A  putchar('\n');
6 V% I* e; Y5 c }
printf("\n最低总运费为：%lg\n",sum);
1 {  b" _. z9 s) W& {7 k& {}
</P>

zhongguohelin

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

enrique08

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

hzlhm

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

liunengwu

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