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

plgatc

<>/*************************************************************************
' H: L! U/ ^' a/ k1 J                         表上作业法解运输问题        
" U! W8 I3 e6 E
2 J' @+ F1 a' S0 y9 \ 编程环境：VC++6.0     
程序说明：
Vogel法求初始解，位势法检验是否最优，递归搜索闭回路改进解。
*************************************************************************/
' {* p5 \" j7 c7 ~4 o: u5 E  ]#include &lt;stdio.h&gt;
: w+ f! n- R' v#include &lt;stdlib.h&gt;</P>
; o9 Y6 p, r+ V/ Y& u7 n  q<>#define MAX 100
  b0 T& g# Y' j#define M 999999</P>
1 d. Y6 w5 m' F2 Q1 {<>int status; //1唯一最优解，-1无穷多最优解</P>
* v, j, G% e7 v$ v1 b* D  X5 I<>int num_a,num_b;
double a[MAX],b[MAX],temp_a[MAX],temp_b[MAX];
! d" H5 C3 G$ _double u[MAX],v[MAX],pu[MAX],pv[MAX];
double ab[MAX][MAX],temp_ab[MAX][MAX];
double base[MAX][MAX];
7 _$ t; E8 q0 z' _' Q5 m0 [8 qint pbase[MAX][MAX];
struct element {
3 |& L) n; m% V' z2 e int r;
int c;
; @+ S0 E9 y5 ?) i$ E. g& W double value;
};
enum direction {mid,up,down,left,right};</P>
3 H4 b+ ], H6 T: Q; W<>void create();
0 T( w5 d# s7 R% I$ [8 n( Gvoid banner();
double dabs(double d);
void findinit();
- B3 @& |- u$ q  C  O4 R3 b" k1 avoid computeuv();
int check();
3 v, X' R/ @) F& I8 p  Bint  circle(enum direction dir,struct element cir[],int *t);
void improve();
void output();</P>
  k: C0 `# S2 X( `<>void main() {
banner();
9 h  {+ x' Y* j3 u  }8 H create();
8 `) L% U: ?7 {/ D* Z5 z) g printf("\n按回车确认后开始求解");
getchar();
getchar();
0 K5 x; T2 ?# G- x, I0 n6 H0 ~2 [ findinit();
/ C  ^- Q8 j2 L7 Y7 ^3 K improve();
switch(status) {
) S( E; ^) o% N) e case 1:
  @. u; r2 E$ ~& k5 L, d7 q  output();
$ {5 z, j- P3 y4 W2 E  puts("\n原问题有唯一最优解。\n");
  puts("\n按回车结束");
2 X" p( @9 V! ^  getchar();
  exit(0);
case -1:
  output();
6 ]0 m# L! I" m) h) P3 c$ Z! Z* d  puts("\n原问题有无穷多最优解。\n");
1 R" I1 X! f$ @6 C, @7 S  T: J  puts("\n按回车结束");
- k- l4 G! K+ F  getchar();
* P+ I) v2 ?5 s  l0 w  exit(0);
) E6 x9 D7 U4 |- S5 A- |& { }
; c, F1 n2 G3 w. f# ?' Q0 ^, \}</P>
; _  @1 O0 }4 y7 R<>void banner() {
printf("\t\t****************************************\n");
printf("\t\t         表上作业法解运输问题\n");
printf("\t\t                              Thunder\n");
3 r1 H0 M1 C) F printf("\t\t****************************************\n");
printf("\n");
}</P>
<>void create() {
& w0 Q6 \% s5 R, p9 T int i,j;
double sum_a,sum_b;
) r5 Z* O3 s% ~3 o char confirm;
$ @. D: b* J1 E9 i: S0 y while(1) {
  printf("请输入产地个数：");
  scanf("%d",&amp;num_a);
  for(i=1;i&lt;=num_a;i++) {
   printf("A%d产量：",i);
   scanf("%lf",&amp;a);
  }
* o+ p# n: w% \: T% \  for(i=1;i&lt;=num_a;i++) printf("A%d产量：%lg\t",i,a);
  printf("\n正确吗？：(y/n)");
  getchar();
, E6 E  q8 E  m' ~8 u! d  confirm=getchar();
  if (confirm=='y') break;
  else if(confirm=='n') continue;
}
while(1) {
  printf("\n请输入销地个数：");
$ ~' B6 o+ @7 Q, P  scanf("%d",&amp;num_b);
  A& j, s0 u3 F# {7 u  for(i=1;i&lt;=num_b;i++) {
1 P& T& |2 k. s* |) n& }) k$ n. p   printf("B%d销量：",i);
- d7 W" u& I% l% ?4 u' c   scanf("%lf",&amp;b);
# I$ z" L1 p8 z, a, m- {+ g  }
+ \7 d5 a" b4 l, i0 f9 H& Y  for(i=1;i&lt;=num_b;i++) printf("B%d销量：%lg\t",i,b);
  printf("\n正确吗？：(y/n)");
3 Z. T0 C- T6 e) _! ]  getchar();
  confirm=getchar();
  if (confirm=='y') break;
2 V# c, {% U1 ~' ?- D  else if(confirm=='n') continue;
# M5 B4 L3 y' c9 ]" Q }
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]);
( L+ r/ {7 l$ ~2 H7 X  }
( Y  m& `$ y! }7 z% i" b  for(j=1;j&lt;=num_b;j++) printf("A%d到B%d：%lg\t",i,j,ab[j]);
  printf("\n正确吗？：(y/n)");
  getchar();
; r+ k0 c' C; i  confirm=getchar();
  if(confirm=='n') i--;
! F! ~. R5 I  I; Y, U* l  putchar('\n');
0 A* L" C/ J& Q; O& ? }
//处理产销不平衡的情况
sum_a=sum_b=0;
5 m" j- N5 v; Y2 N 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);
if(sum_a==sum_b) printf("\t产销平衡。");
) V% W6 U5 T2 m; L# h! V 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;
}
else if(sum_a&lt;sum_b){
  printf("\t供不应求，增加假想产地A%d。\n",++num_a);
/ E4 ]+ l" _4 O6 `6 d  y" E3 E- }  a[num_a]=sum_b-sum_a;
  for(i=1;i&lt;=num_b;i++) ab[num_a]=0;
}
//求解前的准备
5 \- i3 e" C% T# l: n for(i=1;i&lt;=num_a;i++)
: n; o6 I! E  s. b: v' f  Z' p  for(j=1;j&lt;=num_b;j++)
   base[j]=pbase[j]=0;
for(i=1;i&lt;=num_a;i++) temp_a=a;
/ @! R" D; {( H. r2 o/ n for(i=1;i&lt;=num_b;i++) temp_b=b;
for(i=1;i&lt;=num_a;i++)
: P0 U9 v, A4 x4 j) B4 S: w for(j=1;j&lt;=num_b;j++) temp_ab[j]=ab[j];
//回显问题
  Z+ H' p$ J% w# b1 O; f printf("\n\n原问题为：\n\n");
" m$ e  {" N3 D0 [( S# d   printf("产量：\n ");
for(i=1;i&lt;=num_a;i++) printf("A%d:%lg\t",i,a);
, S* d$ S# i  Y# F0 x6 e: K printf("\n运量：\n ");
6 @0 B! j1 k* h; I' ` for(i=1;i&lt;=num_b;i++) printf("B%d:%lg\t",i,b);
printf("\n运价为：\n");
" G; {$ K9 y! `! r  `% I for(i=1;i&lt;=num_a;i++) {
  putchar(' ');
3 [$ L6 {$ Y: U; R% L: W! k  for(j=1;j&lt;=num_b;j++)
   printf("A%d-&gt;B%d:%lg\t",i,j,ab[j]);
  putchar('\n');
}
, _, p5 ]& s  R2 v; |4 Q}</P>
<>double dabs(double d) {
if(d&gt;=0) return d;
else return -d;
4 ^9 K3 `" L% K! e! D0 d+ z}</P>
$ }* k: |  s& R  c<>void findinit() {
int i,j,k;
' M# b+ u0 P: A" } double r_penum[MAX],c_penum[MAX];
2 o/ p. `6 K1 y! {3 t struct largest {
  char rc;
& L% @$ s9 H- A# d1 s- R  int num;
  double value;
};
4 M' ]* m! d; q$ x struct largest lar1,lar2;
# J+ p  l4 b" [: {% J int r=0,c=0;
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];
7 \& |; |5 T2 U" }$ n+ o  a1=a2=temp;
  for(j=1;j&lt;=num_b;j++)
   if(temp_ab[j]&lt;=a1) {
  I; x3 W3 H" d* g- U- n3 L1 ?    a2=a1;
) \/ j, x5 j& U7 z* s    a1=temp_ab[j];
- p: w- ^5 k" \+ r2 h2 ?   }
   else if(temp_ab[j]&lt;=a2) a2=temp_ab[j];
  r_penum=dabs(a1-a2);
! U/ l. o& F1 T+ ~' | }</P>
8 {# {/ K2 t  y9 h" y5 L5 b<> for(i=1;i&lt;=num_b;i++) {
- V2 u% E: k5 }1 f) h  temp=temp_ab[1];
  C6 G' D2 i( p6 [2 I2 W  for(j=1;j&lt;=num_a;j++)
  M9 @0 i+ D! K8 W7 l( O0 \   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;
    b1=temp_ab[j];
- m( B2 y! h; a   }
9 L# l" R3 D/ D3 [$ Z$ I: {2 ?# N% k   else if(temp_ab[j]&lt;=b2) b2=temp_ab[j];
  c_penum=dabs(b1-b2);
}
/*
4 N3 C2 |; h( } for(i=1;i&lt;=num_a;i++) printf("pa%d=%lg ",i,r_penum);
& `6 E1 ^' Q% d putchar('\n');
3 S3 K+ x' H, }9 [. N' C for(i=1;i&lt;=num_b;i++) printf("pb%d=%lg ",i,c_penum);
$ V, }# Z8 F2 H2 B' i" p3 b6 z) T, X */
temp=r_penum[1];
: i- ?5 t  [8 \  {* k for(i=1;i&lt;=num_a;i++) if(r_penum&lt;temp) temp=r_penum;
( l: E- A2 M( x% c) Q* g* y8 F for(i=1;i&lt;=num_b;i++) if(c_penum&lt;temp) temp=c_penum;</P>
) _! B  j4 H, B5 a<> //考虑了有两个罚数相等的情况，大于两个相等只取其中两个进行比较
: J, y5 \+ G% R# E, G4 K lar1.value=lar2.value=temp;
lar1.num=lar2.num=1;
3 \! U1 a/ B1 @, x7 h* q  n7 r lar1.rc=lar2.rc='r';
for(i=1;i&lt;=num_a;i++)
' A6 A6 v, k& y1 x% Q) t  if(r_penum&gt;=lar1.value) {
# @9 v1 h5 y5 k4 ~1 ~" C0 o' l( w   lar2=lar1;
- S2 B: r2 j1 n: G8 @3 X   lar1.rc='r';
   lar1.num=i;
  i( o  N! L/ \, G! M   lar1.value=r_penum;
1 K: ?* j" k1 u! Z# @  }
  else if(r_penum&gt;=lar2.value) {
& [3 `1 t' Z0 v% C% N5 K6 ^   lar2.rc='r';
   lar2.num=i;
' o" n: K; ]. V; z/ \   lar2.value=r_penum;
# i: R9 w- V3 j2 G. i! B# H/ E  }</P>
<> for(i=1;i&lt;=num_b;i++)
  if(c_penum&gt;=lar1.value) {
2 r( u+ |" g0 L7 ?   lar2=lar1;
& \& I! W8 t5 |3 `6 s% ^   lar1.rc='c';
! l2 p* F6 @8 s   lar1.num=i;
  y# K  t" Z  n( Z) I   lar1.value=c_penum;
7 \+ n* D' F+ J# U, W  }
' [6 F/ u) R5 W  \* W0 a  else if(c_penum&gt;=lar2.value) {
3 [2 y8 v" J& Y* M   lar2.rc='c';
/ F* t! Q- I; R8 L4 A/ t! m9 `   lar2.num=i;
   lar2.value=c_penum;
  }</P>
0 e8 z& z& d% K; k& Y1 Z. I- E. M<> if(lar1.value==lar2.value&amp;&amp;(lar1.num!=lar2.num||lar1.rc!=lar2.rc)) {
+ |' v' u: V+ J7 W( H  if(lar1.rc=='r'&amp;&amp;lar2.rc=='r') {
& O' Y& `5 c* S7 C. ?% e  }   temp=temp_ab[lar1.num][1];
   r=lar1.num;
; E" e" n5 k" e" o! w" M9 V9 b: Q      c=1;
   for(i=1;i&lt;=num_b;i++) {
, b2 }( q0 F4 ?& ]8 }    if(temp_ab[lar1.num]&lt;temp) {
/ d) q" T! S' [6 e+ \     temp=temp_ab[lar1.num];
     r=lar1.num;
     c=i;
9 P1 w; e& r# |7 i    }
    if(temp_ab[lar2.num]&lt;temp) {
0 L4 q4 K; R, v/ K( d/ k: C     temp=temp_ab[lar2.num];
( k8 d0 H" {4 x: S9 N1 S! d& e     r=lar2.num;
6 F# [# f# |0 m     c=i;
    }
# m- o  n) Y9 x7 |; p( O   }
" Y! u: s+ @0 g' p  }
  if(lar1.rc=='c'&amp;&amp;lar2.rc=='c') {
, S; M1 m+ x8 t- W5 S7 x2 d   temp=temp_ab[1][lar1.num];
   r=1;
      c=lar1.num;
   for(i=1;i&lt;=num_a-1;i++) {
, \! D7 D+ R9 O% k9 U+ {    if(temp_ab[lar1.num]&lt;temp) {
4 T8 c' ^" t, ]: [     temp=temp_ab[lar1.num];
     c=lar1.num;
% |2 w) P9 S5 `$ U4 a& ~/ ?5 }: Y     r=i;
, r6 d& g2 X! a. Y! v7 {    }
1 I% g+ o+ r2 d9 `  Y0 h    if(temp_ab[lar2.num]&lt;temp) {
$ W' [' F6 N1 o9 A$ s7 H     temp=temp_ab[lar2.num];
     c=lar2.num;
/ [  W& H6 ^9 g: H     r=i;
    }
- Q+ c) _3 Y( z+ h* _7 [   }
  }
  if(lar1.rc=='r'&amp;&amp;lar2.rc=='c') {
   temp=temp_ab[lar1.num][1];
   r=lar1.num;
      c=1;
: n& u" k- z: _) N7 k   for(i=1;i&lt;=num_b;i++)
' C$ `' P3 }5 }* h    if(temp_ab[lar1.num]&lt;temp) {
     temp=temp_ab[lar1.num];
# n; i. y7 a4 q0 z8 T     r=lar1.num;
     c=i;
( i* |" b+ ?. C0 w6 v4 L    }
   for(i=1;i&lt;=num_a;i++)
    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
     c=lar2.num;
     r=i;
* t8 _: _( W3 i( F0 a0 v    }
  q+ s+ r/ X: B4 p  }
: C9 k5 u1 g! W- ]' d3 K  if(lar1.rc=='c'&amp;&amp;lar2.rc=='r') {
   temp=temp_ab[1][lar1.num];
   r=1;
+ W) p$ d1 q2 b' j      c=lar1.num;
2 K% d/ i/ L: U( Q   for(i=1;i&lt;=num_b;i++)
$ m0 A( {2 j# c; a6 M+ u+ ]6 {* M" Q    if(temp_ab[lar2.num]&lt;temp) {
$ V$ Z( F8 M2 {% ?% o- P; y     temp=temp_ab[lar2.num];
9 z* t# g: _$ y9 ^+ B9 {     r=lar2.num;
9 a* d0 d1 t* H* @# `     c=i;
    }
, w$ _  S& {' g) Z  t   for(i=1;i&lt;=num_a;i++)
: C" J$ v' `: k7 A    if(temp_ab[lar1.num]&lt;temp) {
     temp=temp_ab[lar1.num];
  n3 S+ v% ^# z5 m     c=lar1.num;
     r=i;
    }
  }
}
3 x3 Q) F+ K7 {1 F9 u, j else {
  if(lar1.rc=='r') {
   r=lar1.num;
   c=1;
+ X2 ?" F" b& z/ n, T( g9 k   temp=temp_ab[lar1.num][1];
6 q) R! `- j4 B0 I   for(i=1;i&lt;=num_b;i++)
    if(temp_ab[lar1.num]&lt;temp) {
8 \* a: h  l7 m5 p( [7 A     c=i;
     temp=temp_ab[lar1.num];
" ^: D% V: W. H# w* X: s7 Q    }
( M8 H3 l  K. m2 |  }
  else {
   r=1;
   c=lar1.num;
1 m( }0 W- b# N* `4 S2 [   temp=temp_ab[1][lar1.num];
7 S. v, Q3 y/ I- J: c( q% S& q   for(i=1;i&lt;=num_a;i++)
: G( U- l6 R4 j3 b    if(temp_ab[lar1.num]&lt;temp) {
     r=i;
3 R# C0 E, X+ R' i2 H" Z     temp=temp_ab[lar1.num];
4 @" N$ l6 k9 F1 p9 @9 n6 h    }
  }
0 s, e- [+ l" Y }
pbase[r][c]=1;
- v4 E9 K4 m& N. _, w! s9 h6 a if(temp_a[r]&gt;temp_b[c]) {
  base[r][c]=temp_b[c];
* Z" r8 k1 ?3 {5 Q  temp_a[r]=temp_a[r]-temp_b[c];
  |" n* ^) E: W; H  temp_b[c]=0;
  for(i=1;i&lt;=num_a;i++) temp_ab[c]=M;
0 U5 J  ]5 N- _+ u, p  ] }
else if(temp_a[r]&lt;temp_b[c]) {
  base[r][c]=temp_a[r];
4 o/ C  C( I/ D( [) _7 O  temp_b[c]=temp_b[c]-temp_a[r];
' ^$ b' U8 o  [& \  temp_a[r]=0;
  for(i=1;i&lt;=num_b;i++) temp_ab[r]=M;
, Q/ K! N/ J8 P: U% ]' t }
% ]. z1 j: A2 | else if(temp_a[r]==temp_b[c]) {
  base[r][c]=temp_a[r];
  temp_a[r]=temp_b[c]=0;
  for(i=1;i&lt;=num_a;i++) temp_ab[c]=M;
# `, A; b% w5 I- n/ y  for(i=1;i&lt;=num_b;i++) temp_ab[r]=M;
' H' G6 t, p0 F+ P/ B  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) {
   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;}
   if(k==1) pbase[c]=1;
$ z2 f9 j: X( C9 B! u  H, Q& \   else if(k==2) pbase[r][j]=1;
. P0 q- u- s8 J! R' u! c" s+ a) D* F  }
, M; z2 }' T5 M( x5 ?, N2 P/ _) t }
k=0;
$ Y0 G: [$ C4 s; z+ w) n6 _! e: R8 j# L for(i=1;i&lt;=num_a;i++) if(temp_a!=0) k=1;
  Z, x8 X7 b# V- ~4 L) F2 X" @& ]/ p1 f2 X for(i=1;i&lt;=num_b;i++) if(temp_b!=0) k=1;
if(k==0) return;
findinit();
" i* x/ D2 ]' l2 [0 ^- s5 f}</P>
( @+ \- [/ h# Q( H<>void computeuv() {
# ]5 v7 {! L& }+ g& O! X& ~. [ int i,j,k;
! d) K  ]- G, w" W for(i=1;i&lt;=num_a;i++)
  for(j=1;j&lt;=num_b;j++)
  ~/ b" [' n! T$ I4 f8 s  ?   if(pbase[j]==1) {
3 b- [! V# y. @1 {2 f; Z6 q. e: c    if(pu==1) {v[j]=ab[j]-u; pv[j]=1;}
' d+ f* v7 f& b* X+ g1 m    if(pv[j]==1) {u=ab[j]-v[j]; pu=1;}
   }
k=0;
2 v! a- Q! `" X* R/ e% [2 T for(i=1;i&lt;=num_a;i++) if(pu==0) k=1;
1 e9 |4 ^/ G9 H! Y- B/ |2 C/ \ for(i=1;i&lt;=num_b;i++) if(pv==0) k=1;
; m6 v( F6 }, r, ~+ t8 U, m: T+ z6 | if(k==1) computeuv();
}</P>
4 d% t+ |3 X9 v9 j' l<>int check() {
int i,j,k,l;
  E. s- \: \7 x* ^2 p k=l=0;
2 g8 W4 P2 v2 q for(i=1;i&lt;=num_a;i++)
7 ~$ V* w7 C2 J( }; C7 _  for(j=1;j&lt;=num_b;j++)
+ L7 h/ d6 V' j3 ]! j2 |2 ?* I8 b   if(pbase[j]==0) {
    base[j]=ab[j]-u-v[j];
+ q( b; W6 h6 T    if(base[j]&lt;0) k=1;
+ @( G4 D. @( \    else if(base[j]==0) l=1;
. H( ~9 k  ]; U6 C2 ]. V0 ?* d   }
- N" P3 y+ L3 g, s" H/* for(i=1;i&lt;=num_a;i++){
/ t% Y5 {8 Q4 @; o  for(j=1;j&lt;=num_b;j++) printf("base %lg\t",base[j]);
% b% u% w1 ~+ o# I  putchar('\n');}
' L$ r2 g& n8 R' U for(i=1;i&lt;=num_a;i++){
: G: w2 N  z: s( d4 |  for(j=1;j&lt;=num_b;j++) printf("pbase %d\t",pbase[j]);
- }4 R$ U$ ]+ z& l1 r$ `  putchar('\n');}
*/
if(k==0&amp;&amp;l==0) {status=1; return 1;}
# K" X  f- T/ k2 ?- C( {! o" Y else if(k==0&amp;&amp;l!=0) {status=-1; return 1;}
( o% z$ b( l. f# \/ n4 j8 M else return 0;
' d# a4 }1 ?. g1 B" O$ w: z}</P>
$ H# f' A, f, ^<>int circle(enum direction dir,struct element cir[],int *t) {
int i,j,k;
5 I: N, |+ O* a5 z; J: k /*
putchar('\n');
! H% M! r2 h+ X5 m8 t7 r& z for(i=1;i&lt;=*t;i++) printf("%d: r%d c%d\t",i, cir.r,cir.c);
8 f0 a" L$ l! a) s putchar('\n');
*/
if((*t)!=1&amp;&amp;cir[(*t)].r==cir[1].r&amp;&amp;cir[*t].c==cir[1].c) {
  t--;
( b- _+ v- ~" p9 I' [, C" V' C  return 1;
}
5 u7 Y! Q: |9 m, t3 H# ^ if(dir!=down) {
. C7 C- H: d# M+ I  k=0;
  for(i=cir[*t].r-1;i&gt;=1;i--)
# i2 D& Z' B0 v+ g0 L+ [4 M  D   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;
- x( n7 A9 a$ I1 A9 p  if(k==1) {
6 f! y$ V4 I2 F% P/ M- |   if(dir==up) cir[*t].value=0;
   else cir[*t].value=1;
   (*t)++;
   cir[*t].r=i;
   cir[*t].c=cir[(*t)-1].c;
: ^, K) Z+ f5 D. L" W3 f" }; S   if(circle(up,cir,t)) return 1;
  }
# H6 o) l( s9 J, P, @5 o }
if(dir!=up) {
  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;}
2 O6 F1 }, q* K* [  for(j=2;j&lt;=*t;j++) if(i==cir[j].r&amp;&amp;cir[*t].c==cir[j].c) k=0;
; d: V1 \0 {6 B; |  if(k==1) {
   if(dir==down) cir[*t].value=0;
: Q3 u# f3 v+ L   else cir[*t].value=1;
   (*t)++;
# L3 X" v* }4 C  V2 k5 p$ t9 d   cir[*t].r=i;
2 g' V/ `& O1 e) L   cir[*t].c=cir[(*t)-1].c;
   if(circle(down,cir,t)) return 1;
  }
}
, p) n* r, ?& k/ l$ q. P9 s if(dir!=right) {
  k=0;
  for(i=cir[*t].c-1;i&gt;=1;i--)
" K. o4 v) z( X9 P" @- w" s. b3 C   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 a& y1 @3 j7 f' b) }* F2 ]  if(k==1) {
   if(dir==left) cir[*t].value=0;
   else cir[*t].value=1;
   (*t)++;
4 }1 ^" K2 H7 f9 q* Y$ O/ k   cir[*t].r=cir[(*t)-1].r;
; j3 b: t* `3 e- c! \9 H' v   cir[*t].c=i;
   if(circle(left,cir,t)) return 1;
  }
}
! `$ R$ K- V3 u# c if(dir!=left) {
! c1 q9 C( G7 x4 v0 S  k=0;
0 y8 W! }& F, F  I  for(i=cir[*t].c+1;i&lt;=num_b;i++)
7 [) @/ O( `/ d& \3 L: z   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==right) cir[*t].value=0;
: @+ W* `: C2 ?& F6 L   else cir[*t].value=1;
6 ?& o8 v6 x7 t1 |   (*t)++;
   cir[*t].r=cir[(*t)-1].r;
   cir[*t].c=i;
   if(circle(right,cir,t)) return 1;
  }
}
, s7 _; A. y6 f- z! M (*t)--;
8 A6 A; D4 _' h9 Y2 l return 0;
}</P>
<>void improve() {
int i,j,k,t;
$ G" E  k6 U0 [) h struct element base_in,base_out,cir[2*MAX+1];</P>
<> for(i=1;i&lt;=num_a;i++) pu=0;
2 w% W) Q! E  U. S  U- u% y' ` for(i=1;i&lt;=num_b;i++) pv=0;
- ^. [0 _" f- z  G; { 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++)
   if(pbase[j]==0) break;
" d$ `% j8 H' o) X; R9 o base_in.r=i;
base_in.c=j;
; t2 ~& u5 W) O' i base_in.value=base[j];</P>
( ~9 y0 x: R- X  `7 o1 I) p( k0 L<> for(i=1;i&lt;=num_a;i++)
/ ?, x# m# b3 R& p  for(j=1;j&lt;=num_b;j++)
) L9 Q. T- _/ D3 n4 ]  w   if(pbase[j]==0&amp;&amp;base[j]&lt;base_in.value) {
2 F; i9 M3 y5 K    base_in.r=i;
: m. {# {& j% G+ Z& Z0 E    base_in.c=j;
' @' Q( ?/ ^" A4 n1 \* q' x3 k4 _    base_in.value=base[j];
   }</P>
<> t=1;
cir[t].r=base_in.r;
cir[t].c=base_in.c;
cir[t].value=1;
! [3 ]! F& I0 H- p& T3 O if(!circle(mid,cir,&amp;t)) {
  printf("程序出错！按回车结束");
  x1 ]  w0 v: P/ p; J2 S  getchar();
  exit(0);
: {8 F8 v( C  ]* K }
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>
/ f+ D3 u# x  z4 c% F<> for(i=2;i&lt;=t;i++) if(cir.value==1) break;
+ ^+ d( G  |* B0 J# @: A, b& M9 \. l base_out=cir;
2 c4 c, X, T; L+ a9 s% v 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;
7 o) R0 }! @. r) @% d   base_out.value=base[cir.r][cir.c];
- i) k2 [& l" s0 i) m   k++;
  }
  else if(cir.value==1) k++;
7 m, j: y7 {6 E% 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;
; h' V" T2 w4 Q( a+ R   k++;
6 j$ ?4 B# K& i0 C  }
  else if(k%2==0&amp;&amp;cir.value==1) {
   base[cir.r][cir.c]-=base_out.value;
* j7 V; e( N: ]: r+ @- J* s" L   k++;
2 I! B# O( J+ ]% \/ n  t  }
}
pbase[base_out.r][base_out.c]=0;
pbase[base_in.r][base_in.c]=1;</P>
- Z1 [- ^; _  n& M$ H2 ?  _<> improve();
}</P>
<>void output() {
int i,j;
double sum=0;
' u6 C1 i/ M5 [& S4 O7 C. p printf("\n运量为：\n");
8 l, ^$ [# @: x for(i=1;i&lt;=num_a;i++) {
  putchar(' ');
  for(j=1;j&lt;=num_b;j++)
% r2 F4 z9 R' y6 N$ }% _   if(pbase[j]==1) {
    printf("A%d-&gt;B%d:%lg\t",i,j,base[j]);
& a( c8 [3 a/ ?, s% z) V    sum+=base[j]*ab[j];
   }
   else printf("A%d-&gt;B%d:0\t",i,j);
  putchar('\n');
}
  K, t8 y2 p4 V2 _8 K- p) x printf("\n最低总运费为：%lg\n",sum);
2 d5 I3 j  b4 J  N5 v/ e- J}
3 u) D) x% X. i  \/ a* b</P>

zhongguohelin

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

enrique08

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

hzlhm

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

liunengwu

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