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

plgatc

<>/*************************************************************************
                         表上作业法解运输问题        
  B$ s, ^. l8 _9 u
编程环境：VC++6.0     
. ]0 l1 t  m0 q7 g9 J 程序说明：
# _2 k0 G7 V  n( o7 G1 b3 e( z Vogel法求初始解，位势法检验是否最优，递归搜索闭回路改进解。
' h! A& O9 o8 @: r1 \ *************************************************************************/
#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;</P>
" d, R& @' Z0 T  i- [<>#define MAX 100
/ q9 o# L: l/ I" W#define M 999999</P>
<>int status; //1唯一最优解，-1无穷多最优解</P>
% p( p* L! C+ a$ a3 b. O- X<>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];
double ab[MAX][MAX],temp_ab[MAX][MAX];
# d. ^8 m6 I7 q, P0 _7 {double base[MAX][MAX];
int pbase[MAX][MAX];
3 F  s7 w3 U* F% |8 s$ S. r- kstruct element {
int r;
int c;
' c* }+ U# b& w( V double value;
};
enum direction {mid,up,down,left,right};</P>
$ P) D, Z; W5 V. }6 c<>void create();
void banner();
+ G) p& H& d* v/ Kdouble dabs(double d);
, t6 L* K1 V/ J! @1 Y$ R) Rvoid findinit();
void computeuv();
int check();
& i. T+ `( A9 l- z, ]/ `( Aint  circle(enum direction dir,struct element cir[],int *t);
6 U6 z3 O/ }; i+ ~3 avoid improve();
( B9 G7 ^0 K+ [* W0 D5 Tvoid output();</P>
" y* H. a) u0 L" v- r<>void main() {
banner();
1 j/ r& B# I0 V2 T. E* v% Y7 ` create();
printf("\n按回车确认后开始求解");
+ I' b) y8 y8 | getchar();
getchar();
findinit();
- m0 T( U  q2 A improve();
) Y& z$ \' w* O, D# Z switch(status) {
$ \  S6 Z) s* I$ ~% e9 @  \ case 1:
  output();
/ A: @- D7 g6 B9 T' Q  puts("\n原问题有唯一最优解。\n");
: r' g1 D- `" w/ G5 ]" a# J  puts("\n按回车结束");
  getchar();
  exit(0);
case -1:
  output();
3 e! w# D. O2 d: L$ d, C& e  puts("\n原问题有无穷多最优解。\n");
' a  O5 l0 p: `3 p# u( j6 z  puts("\n按回车结束");
  getchar();
  exit(0);
}
}</P>
' }7 P8 V; I/ v1 I0 Y<>void banner() {
printf("\t\t****************************************\n");
printf("\t\t         表上作业法解运输问题\n");
5 l% U! s3 U" U2 ^( _ printf("\t\t                              Thunder\n");
) s) p- @3 V0 W6 M9 R  j printf("\t\t****************************************\n");
printf("\n");
$ a) ~( r1 y/ R2 ]}</P>
9 e; O/ z$ k7 f1 M- q8 S! a7 D8 J<>void create() {
int i,j;
double sum_a,sum_b;
char confirm;
while(1) {
0 }" d, T, |, j, M7 Q( K" |  printf("请输入产地个数：");
$ g) ], B8 M! Z0 }" _! F  scanf("%d",&amp;num_a);
/ d/ V( D, {3 I  for(i=1;i&lt;=num_a;i++) {
   printf("A%d产量：",i);
   scanf("%lf",&amp;a);
  }
  for(i=1;i&lt;=num_a;i++) printf("A%d产量：%lg\t",i,a);
  printf("\n正确吗？：(y/n)");
  getchar();
8 d" @* v# @8 d  confirm=getchar();
  if (confirm=='y') break;
. a  Z  \: ]; ^  else if(confirm=='n') continue;
}
$ Z  q' b2 x1 F, V! v while(1) {
  printf("\n请输入销地个数：");
  scanf("%d",&amp;num_b);
9 l5 A1 }/ y. \# u6 ]+ i% m" r  for(i=1;i&lt;=num_b;i++) {
   printf("B%d销量：",i);
   scanf("%lf",&amp;b);
2 ]! q& \. A, V2 D, k- u5 ]  }
4 [; Z0 o/ C: a0 G7 |/ l7 i  for(i=1;i&lt;=num_b;i++) printf("B%d销量：%lg\t",i,b);
8 p9 F  P0 d) y- M  printf("\n正确吗？：(y/n)");
2 a! h# A' @2 D  g9 a  getchar();
  confirm=getchar();
  if (confirm=='y') break;
  else if(confirm=='n') continue;
}
( c9 e8 l. J1 s& ~1 v  q" l putchar('\n');
for(i=1;i&lt;=num_a;i++) {
) [5 a" G! N! e! u  w+ |3 M  for(j=1;j&lt;=num_b;j++) {
   printf("A%d到B%d运价：",i,j);
   scanf("%lf",&amp;ab[j]);
' Z" s4 d/ G+ `8 d& v  }
  for(j=1;j&lt;=num_b;j++) printf("A%d到B%d：%lg\t",i,j,ab[j]);
3 Z3 {/ f) \, v- f# K  printf("\n正确吗？：(y/n)");
  getchar();
* Z6 d' p0 k- u$ m2 r  confirm=getchar();
& y9 s/ |& y" z' K; l- q4 w  if(confirm=='n') i--;
6 M, W# R4 j( x4 }! \  putchar('\n');
}
7 {2 Y) f, c3 @8 M //处理产销不平衡的情况
5 N: T! y0 i1 g sum_a=sum_b=0;
for(i=1;i&lt;=num_a;i++) sum_a+=a;
for(i=1;i&lt;=num_b;i++) sum_b+=b;</P>
3 m. `. U. j1 H' g" r<> printf("总产量：%lg\t总销量：%lg",sum_a,sum_b);
if(sum_a==sum_b) printf("\t产销平衡。");
3 f; Y% O" d6 h: w) ~7 A else if(sum_a&gt;sum_b) {
  printf("\t供大于求，增加假想销地B%d。\n",++num_b);
  b[num_b]=sum_a-sum_b;
4 F5 y- D* ^/ u, t6 G: K  for(i=1;i&lt;=num_a;i++) ab[num_b]=0;
}
else if(sum_a&lt;sum_b){
+ l% q/ v; o4 T& f  Y+ @0 v  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;
}
//求解前的准备
, U6 r4 s7 P3 t for(i=1;i&lt;=num_a;i++)
  for(j=1;j&lt;=num_b;j++)
2 Q5 G* o0 L$ ~, Q+ [2 \   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;
for(i=1;i&lt;=num_a;i++)
0 a2 j1 @# J+ o5 T5 x for(j=1;j&lt;=num_b;j++) temp_ab[j]=ab[j];
- U5 n' R1 S) {' _- _ //回显问题
; c9 }% ^  n0 t* ?8 g/ a printf("\n\n原问题为：\n\n");
   printf("产量：\n ");
for(i=1;i&lt;=num_a;i++) printf("A%d:%lg\t",i,a);
4 U; F  w# J  L) w4 t printf("\n运量：\n ");
, r, T' `3 M% c* i for(i=1;i&lt;=num_b;i++) printf("B%d:%lg\t",i,b);
+ a0 `( M1 ?7 W+ `6 W- g" ?5 @7 l, m printf("\n运价为：\n");
; ]( M  m& ^8 D, ^& Y for(i=1;i&lt;=num_a;i++) {
5 `1 ?8 Q4 h1 b6 h) w, w2 n  putchar(' ');
1 e. F& G/ y4 B9 ]  u8 @  for(j=1;j&lt;=num_b;j++)
, B. A+ b  _4 o   printf("A%d-&gt;B%d:%lg\t",i,j,ab[j]);
4 S3 M! W  S; w0 w' S  putchar('\n');
}
}</P>
<>double dabs(double d) {
6 d% O/ u# g% g+ w, w0 f4 F if(d&gt;=0) return d;
4 w0 _: Y0 m( l- R2 m. ?- \ else return -d;
) l3 j/ b7 K5 R: {" e}</P>
# }0 I) e) D1 a7 J<>void findinit() {
int i,j,k;
- K( \2 h: I, {; J; T- l, p double r_penum[MAX],c_penum[MAX];
6 ?4 ?0 m3 a# }% ~+ r& y" V struct largest {
  char rc;
  int num;
  double value;
, K' B, x$ K; Q0 n$ S1 w' w2 S };
% O' Q# {9 ~7 j# q- ^2 G' M! @ struct largest lar1,lar2;
int r=0,c=0;
double a1,a2,b1,b2,temp;</P>
<> for(i=1;i&lt;=num_a;i++) {
( p3 S" }6 C) K3 L3 [  temp=temp_ab[1];
  for(j=1;j&lt;=num_b;j++)
   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
' a' l9 F! D6 N4 }; W* s  a1=a2=temp;
  for(j=1;j&lt;=num_b;j++)
, ]7 d1 f. M& D3 v! B+ u7 O) y   if(temp_ab[j]&lt;=a1) {
0 Z+ j2 R/ J& h6 x7 m/ q6 q    a2=a1;
    a1=temp_ab[j];
   }
   else if(temp_ab[j]&lt;=a2) a2=temp_ab[j];
  @. G+ ^9 d7 n8 }$ c$ K7 W: l  r_penum=dabs(a1-a2);
* L) v/ n8 y  T. F, c( o }</P>
6 _4 r4 |7 E; E9 u<> for(i=1;i&lt;=num_b;i++) {
6 Y# E" V2 I6 S3 u* {0 H) i% S  temp=temp_ab[1];
7 w: L) e, i1 k9 ?6 K. u  for(j=1;j&lt;=num_a;j++)
   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
; e2 v7 \" N; B4 d8 ^( R' n7 J  b1=b2=temp;
* s/ \7 g4 n) `8 E3 A% S. c4 ^  for(j=1;j&lt;=num_a;j++)  
   if(temp_ab[j]&lt;=b1) {
    b2=b1;
/ s3 j% O3 k9 R+ T    b1=temp_ab[j];
   }
' o/ b0 I* p$ k: R   else if(temp_ab[j]&lt;=b2) b2=temp_ab[j];
4 k" ]+ j) @" M6 E- `" `, G0 W  c_penum=dabs(b1-b2);
7 n% V' j9 H. `9 [" h }
/*
: Y6 M: a4 H: J2 o for(i=1;i&lt;=num_a;i++) printf("pa%d=%lg ",i,r_penum);
( j( {1 e- ]/ r1 {: K% Q: g0 K$ F putchar('\n');
4 u/ \- t$ H% I" Z for(i=1;i&lt;=num_b;i++) printf("pb%d=%lg ",i,c_penum);
*/
. W6 b0 m$ A" j5 v temp=r_penum[1];
' q( M$ o* ?2 W$ a6 S  b# R for(i=1;i&lt;=num_a;i++) if(r_penum&lt;temp) temp=r_penum;
/ P+ R8 ]* I) q" ]4 R/ h# z for(i=1;i&lt;=num_b;i++) if(c_penum&lt;temp) temp=c_penum;</P>
<> //考虑了有两个罚数相等的情况，大于两个相等只取其中两个进行比较
4 d+ v; V9 }/ b0 p, r lar1.value=lar2.value=temp;
" b5 r, s6 g( x: n' U# y lar1.num=lar2.num=1;
lar1.rc=lar2.rc='r';
for(i=1;i&lt;=num_a;i++)
0 T- @& G9 p% s3 u1 d  if(r_penum&gt;=lar1.value) {
! S% B! T: z( N, X5 Y: d   lar2=lar1;
   lar1.rc='r';
   lar1.num=i;
   lar1.value=r_penum;
  }
+ J2 f1 E1 R+ Q5 x2 ~" k  else if(r_penum&gt;=lar2.value) {
   lar2.rc='r';
   lar2.num=i;
/ I' Q9 B0 a1 n2 F1 S6 z$ W; p   lar2.value=r_penum;
* V: z  H- x' l  }</P>
6 |1 m0 F6 T/ V* P( Y3 p<> for(i=1;i&lt;=num_b;i++)
$ J" m6 c, z; j  x$ h4 r1 X# X' j  if(c_penum&gt;=lar1.value) {
$ N8 e* C6 U& v7 g  B+ c   lar2=lar1;
. L& ^) H% \) O; T* C% p# ^   lar1.rc='c';
   lar1.num=i;
   lar1.value=c_penum;
; D% O' D0 W- Z) [0 ~  }
8 y" u* P7 y: g, P  else if(c_penum&gt;=lar2.value) {
   lar2.rc='c';
   lar2.num=i;
   lar2.value=c_penum;
  }</P>
1 P% b/ C) R$ U  I! o3 [2 s$ d<> 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;
      c=1;
   for(i=1;i&lt;=num_b;i++) {
2 X, ]% ?& }0 F  h8 ~+ F    if(temp_ab[lar1.num]&lt;temp) {
$ I2 q; R8 B" U6 o: B: {/ ~     temp=temp_ab[lar1.num];
     r=lar1.num;
1 e% r* c; G( B3 _0 |2 u- ^$ k6 G     c=i;
    }
    if(temp_ab[lar2.num]&lt;temp) {
7 d: l) v- \9 @% i     temp=temp_ab[lar2.num];
; z  P( q0 m5 m- U2 H5 n     r=lar2.num;
     c=i;
    }
! g- H. t& G7 d, e4 r7 G+ r! X8 e   }
  }
% a6 M0 x. ]' t9 N+ M" p  if(lar1.rc=='c'&amp;&amp;lar2.rc=='c') {
3 N" O* k! w* E+ f! G1 y+ X   temp=temp_ab[1][lar1.num];
   r=1;
      c=lar1.num;
$ B2 x' W  V  e. b7 P/ I* V. R   for(i=1;i&lt;=num_a-1;i++) {
    if(temp_ab[lar1.num]&lt;temp) {
$ e& m, |" \  I: A! `) ]& E+ y& Y     temp=temp_ab[lar1.num];
; [# D- [4 S+ |: y     c=lar1.num;
     r=i;
    }
    if(temp_ab[lar2.num]&lt;temp) {
: Y0 j2 i- q7 N0 r  h/ z     temp=temp_ab[lar2.num];
     c=lar2.num;
     r=i;
5 X- f+ C' J6 M) M$ {9 C8 }8 ]9 A    }
1 s2 H( Y0 _/ _" P  \; J   }
  }
: n: e2 ?( L) [; Q  if(lar1.rc=='r'&amp;&amp;lar2.rc=='c') {
1 K  S* S0 z! f   temp=temp_ab[lar1.num][1];
   r=lar1.num;
# y) ]+ {& P- b$ o      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;
. L( r9 l1 x8 S& v4 G& o+ m     c=i;
    }
$ e' a' Q! _/ n9 }; P, V& c   for(i=1;i&lt;=num_a;i++)
' J. I( M) A0 O/ }1 h    if(temp_ab[lar2.num]&lt;temp) {
* a" X  M: i- S2 ?' f     temp=temp_ab[lar2.num];
     c=lar2.num;
     r=i;
8 \* ~+ }8 a" H( a$ x    }
0 B) ]$ D1 o' D; a% C" h, V; W  }
  if(lar1.rc=='c'&amp;&amp;lar2.rc=='r') {
   temp=temp_ab[1][lar1.num];
   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];
- ~! G4 F7 \) {! D: \     r=lar2.num;
  p) @2 U$ M1 \. X! W     c=i;
# P4 G  I; R2 }* M4 r    }
; T& y' T+ n* l/ T/ b   for(i=1;i&lt;=num_a;i++)
    if(temp_ab[lar1.num]&lt;temp) {
  {9 W3 l! j, v. s$ w/ S1 ~3 k# X     temp=temp_ab[lar1.num];
+ X& V3 t% q0 J- q  {$ h5 l     c=lar1.num;
8 ?, V2 P' D( \' \8 Y     r=i;
' N) Q* o9 C4 I5 g0 r4 B    }
4 H" ^9 _  n( g( S7 J! _  }
4 t6 a7 L  D& |+ v! R' \ }
; \8 i/ ]- [* Z$ p else {
  if(lar1.rc=='r') {
   r=lar1.num;
% l! \) K0 W& o  l& u2 q   c=1;
& n4 |0 T" f" C5 L; m   temp=temp_ab[lar1.num][1];
9 B0 V: E2 A/ y  n, m: R% w   for(i=1;i&lt;=num_b;i++)
    if(temp_ab[lar1.num]&lt;temp) {
     c=i;
+ G+ _4 W6 k2 x& @     temp=temp_ab[lar1.num];
    }
  }
% O! U: {* V* w# k4 r  A  else {
   r=1;
   c=lar1.num;
   temp=temp_ab[1][lar1.num];
   for(i=1;i&lt;=num_a;i++)
% q; ?7 I4 Q* P8 C1 N) e$ ?% B( o: J    if(temp_ab[lar1.num]&lt;temp) {
     r=i;
     temp=temp_ab[lar1.num];
7 r, D* s0 r* T0 C' ^3 E& c+ q5 T9 F    }
! G7 `" b5 }9 p, [  }
}
, u- P9 G. e$ _- B2 H pbase[r][c]=1;
if(temp_a[r]&gt;temp_b[c]) {
  base[r][c]=temp_b[c];
7 f) }+ i' n' ~+ T9 Z' v  temp_a[r]=temp_a[r]-temp_b[c];
& @- V3 |+ v" m, M6 E  temp_b[c]=0;
8 ^* S, |  b  o8 z  for(i=1;i&lt;=num_a;i++) temp_ab[c]=M;
) ]6 z2 t$ m& m9 R. _* A: P }
else if(temp_a[r]&lt;temp_b[c]) {
  base[r][c]=temp_a[r];
  temp_b[c]=temp_b[c]-temp_a[r];
2 B  B4 I( Y  d  @; N  Z  temp_a[r]=0;
  for(i=1;i&lt;=num_b;i++) temp_ab[r]=M;
}
% o! d; j9 Y+ k7 n! z3 d9 M" @ else if(temp_a[r]==temp_b[c]) {
  base[r][c]=temp_a[r];
  temp_a[r]=temp_b[c]=0;
" S! R: n& b' Z2 E2 }  for(i=1;i&lt;=num_a;i++) temp_ab[c]=M;
% w% b& W. j% [3 e% a, 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) {
/ a# x. ^' F$ O   k=0;
   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;}
2 e9 X+ h( E& N3 `- U, {9 i$ m   if(k==1) pbase[c]=1;
   else if(k==2) pbase[r][j]=1;
5 s& ~; _6 J3 p$ U4 l. W( ^  }
}
k=0;
! Y: c* e9 t( 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;
2 ^0 I1 J: [0 w! |$ e$ E# X3 y if(k==0) return;
! e0 n. A9 F, ]/ X+ p( m findinit();
; V) b; j: ^' H8 R3 i5 Q}</P>
<>void computeuv() {
  ^& a) u* r1 u3 s- m int i,j,k;
( s5 Q; {6 N$ C5 w# `+ } for(i=1;i&lt;=num_a;i++)
9 ?- K% q0 f0 }: k3 Q+ S, q  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==1) {
4 e- ?1 Q2 y+ F, b9 A8 @! {    if(pu==1) {v[j]=ab[j]-u; pv[j]=1;}
    if(pv[j]==1) {u=ab[j]-v[j]; pu=1;}
* Q; h( z+ {/ H8 j% v   }
2 u; ^; X5 b+ Q# x* Y$ E k=0;
4 v# Q& e7 w8 V2 O9 ^. u# T 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>
3 p+ M6 P) S+ {; p7 e7 O: [- U/ v& a<>int check() {
int i,j,k,l;
5 t9 o+ a) N0 ]* O& r k=l=0;
for(i=1;i&lt;=num_a;i++)
" G& l3 h+ |$ u% ]* u. V1 }7 ^  for(j=1;j&lt;=num_b;j++)
3 ^+ k/ j# \4 ~4 y% A   if(pbase[j]==0) {
- s+ J3 P7 M& }7 q! v- ]* V0 E, ^5 b    base[j]=ab[j]-u-v[j];
4 q& v. i5 m3 K) ]$ A% Y4 _' x* N    if(base[j]&lt;0) k=1;
& s3 S3 f4 c% `* G9 s" c    else if(base[j]==0) l=1;
8 l( }8 g$ _1 ]4 i% Y0 T   }
  M. L& h/ k: r( f) C/* for(i=1;i&lt;=num_a;i++){
+ H0 s' k: q8 F  for(j=1;j&lt;=num_b;j++) printf("base %lg\t",base[j]);
+ O; D: G  h8 v  putchar('\n');}
for(i=1;i&lt;=num_a;i++){
# b4 M- f- H# |: D0 N  for(j=1;j&lt;=num_b;j++) printf("pbase %d\t",pbase[j]);
  putchar('\n');}
1 [0 r# v) a& x) d6 ~0 H9 ~, _*/
7 x; o' y! v. g' G$ r$ Z 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;
5 T1 Q4 A+ \& H: | /*
/ J4 e+ t8 n( b: ?3 K5 F putchar('\n');
for(i=1;i&lt;=*t;i++) printf("%d: r%d c%d\t",i, cir.r,cir.c);
putchar('\n');
*/
; I9 f4 A: N; N5 f; t" I: H if((*t)!=1&amp;&amp;cir[(*t)].r==cir[1].r&amp;&amp;cir[*t].c==cir[1].c) {
* t2 e- Q# N% s5 ?2 [  t--;
  return 1;
# c( d6 ^7 E9 X }
if(dir!=down) {
  k=0;
' @8 @3 X7 o9 J  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;}
. F; Z9 s9 y  ^  for(j=2;j&lt;=*t;j++) if(i==cir[j].r&amp;&amp;cir[*t].c==cir[j].c) k=0;
! z) y# z( F9 ^8 C; D& O' h. P  if(k==1) {
   if(dir==up) cir[*t].value=0;
   else cir[*t].value=1;
   (*t)++;
   cir[*t].r=i;
   cir[*t].c=cir[(*t)-1].c;
; K9 I( T" T3 T, ]2 o. Q   if(circle(up,cir,t)) return 1;
9 a. R7 L- y; l% E) \1 R" b5 f  }
- ~, w) Q. F+ p4 x }
. K. c+ y2 [* _& E; Y, A if(dir!=up) {
  k=0;
0 o8 e  t6 r  U! r6 @  for(i=cir[*t].r+1;i&lt;=num_a;i++)
) B$ s4 ^" J4 T. Q   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) {
5 K2 C3 d% m/ z7 F- c: l9 X   if(dir==down) cir[*t].value=0;
3 K3 T$ p3 x1 }7 K: I   else cir[*t].value=1;
   (*t)++;
9 E: F) N( c' r0 [2 j4 k   cir[*t].r=i;
   cir[*t].c=cir[(*t)-1].c;
   if(circle(down,cir,t)) return 1;
4 A. q0 y: _, o& f+ c+ f  }
}
: l  K& N2 Q" ]$ v 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;
0 A# e) |6 a* r" l   (*t)++;
0 o) s$ s2 k$ Z* y6 `* R, n6 K   cir[*t].r=cir[(*t)-1].r;
# T, P1 M" J4 `: m; o0 v$ g) {   cir[*t].c=i;
   if(circle(left,cir,t)) return 1;
  }
4 {1 @5 K/ p' X2 F$ Y* W }
if(dir!=left) {
: D& j! t& O3 b& Z  k=0;
6 b3 T9 G: v9 N  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;}
8 P: U  E: _  O) j( G! b8 q: p! o  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 L9 E6 i3 [! g9 ~   if(dir==right) cir[*t].value=0;
   else cir[*t].value=1;
  o9 v5 V0 b0 b0 v/ i+ `  k  I4 U   (*t)++;
   cir[*t].r=cir[(*t)-1].r;
   cir[*t].c=i;
   if(circle(right,cir,t)) return 1;
* H$ z5 f% T$ [3 g$ _# C  }
7 a/ H2 s+ m, x% \% l# j( N }
5 Q2 `1 _# ~' ~2 r (*t)--;
return 0;
1 [2 f+ s# d  T2 ~! d/ U}</P>
) {$ e6 J, e) e# z* }, z+ Q, s8 K# l<>void improve() {
0 Q4 h6 N0 c2 u  y$ q# y int i,j,k,t;
- p% o- w) m0 }9 ~- t! U struct element base_in,base_out,cir[2*MAX+1];</P>
+ Y% B1 E$ }5 ]. d; R<> for(i=1;i&lt;=num_a;i++) pu=0;
$ g% p  r$ {  Y) y/ S. S for(i=1;i&lt;=num_b;i++) pv=0;
u[1]=0; pu[1]=1;
computeuv();
% k8 ^7 U8 z  M) B  C+ P( o if(check()) return;
8 _- F9 S" \9 j2 ?- f5 X# ? for(i=1;i&lt;=num_a;i++)
  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==0) break;
base_in.r=i;
$ T; R' m6 O& `2 Y& j, S" {2 C. r0 i base_in.c=j;
7 u$ R3 p9 v: e! K0 L% A6 | base_in.value=base[j];</P>
5 [6 M, ]0 R) z. ^<> for(i=1;i&lt;=num_a;i++)
0 H. y. e2 C7 U9 D3 A1 i4 B4 i, T0 G3 P  for(j=1;j&lt;=num_b;j++)
. y+ O4 g$ a( y, j* H9 g& ]4 k, t3 C) ~   if(pbase[j]==0&amp;&amp;base[j]&lt;base_in.value) {
    base_in.r=i;
    base_in.c=j;
  x1 {$ D% O) ]    base_in.value=base[j];
   }</P>
<> t=1;
$ X( ^! }! T* f! _! O cir[t].r=base_in.r;
cir[t].c=base_in.c;
cir[t].value=1;
0 q: c8 ?8 ~( J2 Y if(!circle(mid,cir,&amp;t)) {
  printf("程序出错！按回车结束");
- T' M$ P, L! s" I3 ?5 {  getchar();
  exit(0);
+ T7 M( i- O6 c; D: T }
1 p( Q# m) n$ {# ]- x& V# _2 w t--;
// for(i=1;i&lt;=t;i++) printf("%d:r%d c%d v%lg\t",i,cir.r,cir.c,cir.value);
9 [1 A/ e: k( F5 x; N1 i7 ]// putchar('\n');</P>
<> for(i=2;i&lt;=t;i++) if(cir.value==1) break;
9 i3 ?  b% r3 c$ E base_out=cir;
3 u/ [0 p5 i0 d4 D: n3 ^8 ?: {( D! T; A base_out.value=base[cir.r][cir.c];
k=1;
" q- q- F* S: Z- U/ j, H for(i=1;i&lt;=t;i++)
2 w: K1 G/ o% T3 V9 s$ U/ F3 B+ N& v  if(k%2==0&amp;&amp;cir.value==1&amp;&amp;base[cir.r][cir.c]&lt;base_out.value) {
3 g3 m* z1 j3 Q' u   base_out=cir;
, K2 d! r6 h' f1 @   base_out.value=base[cir.r][cir.c];
   k++;
  v* @6 M6 P5 o) J  }
  else if(cir.value==1) k++;
$ s5 j# m! F5 P( @: F base[cir[1].r][cir[1].c]=0;
3 ]0 t2 ~) {% n* B1 G- U k=1;
for(i=1;i&lt;=t;i++) {
  if(k%2==1&amp;&amp;cir.value==1) {
* l7 Z- P9 T6 i2 y   base[cir.r][cir.c]+=base_out.value;
5 e9 Y/ ~7 [9 C+ X* U7 `: K4 Q8 [   k++;
  }
+ g: m; G8 p/ T, I  else if(k%2==0&amp;&amp;cir.value==1) {
   base[cir.r][cir.c]-=base_out.value;
1 ~; D: n9 ]. s   k++;
  }
" d1 {  T/ c* S! `4 z% u }
* l# }/ z2 l; c( p pbase[base_out.r][base_out.c]=0;
pbase[base_in.r][base_in.c]=1;</P>
<> improve();
) m# I/ D  g: C+ n& W, ]4 U. f}</P>
<>void output() {
int i,j;
! C' u% A) ~- I( w' n6 X double sum=0;
printf("\n运量为：\n");
for(i=1;i&lt;=num_a;i++) {
& [: ?1 d6 X1 J6 k5 h: F7 D  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]);
8 }1 g: Y3 P8 [. Y  R    sum+=base[j]*ab[j];
   }
6 ]- z9 x, ~6 ]; v2 z7 F   else printf("A%d-&gt;B%d:0\t",i,j);
: M( e- T3 v' f2 q& g0 K3 o* h  putchar('\n');
}
printf("\n最低总运费为：%lg\n",sum);
5 A7 @4 `% C* L4 ?3 E" i}
</P>

zhongguohelin

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

enrique08

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

hzlhm

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

liunengwu

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