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

plgatc

<>/*************************************************************************
                         表上作业法解运输问题        
0 F. i1 g" e5 s: a/ R
编程环境：VC++6.0     
) P' N. {+ f$ K/ S( @7 p+ n 程序说明：
1 m* k+ {. D5 x7 u Vogel法求初始解，位势法检验是否最优，递归搜索闭回路改进解。
$ C( S8 @  K: q2 r) t *************************************************************************/
' P; x  T9 z1 X#include &lt;stdio.h&gt;
( K7 o0 O- W; m#include &lt;stdlib.h&gt;</P>
* l7 b$ }+ f" y3 J<>#define MAX 100
: |: ]4 C" m6 ?2 G6 x#define M 999999</P>
<>int status; //1唯一最优解，-1无穷多最优解</P>
<>int num_a,num_b;
double a[MAX],b[MAX],temp_a[MAX],temp_b[MAX];
, \% X4 c4 x5 ^8 s/ {8 Qdouble u[MAX],v[MAX],pu[MAX],pv[MAX];
% N# I" \' U( v- N9 m( g5 l) O0 q/ qdouble ab[MAX][MAX],temp_ab[MAX][MAX];
1 E( }: Y/ x* Y8 [' Ydouble base[MAX][MAX];
9 ]. B! z. B( r6 U) C6 ^* Qint pbase[MAX][MAX];
! B& j' r. `: A3 s* x9 q6 L! {+ lstruct element {
int r;
int c;
double value;
};
enum direction {mid,up,down,left,right};</P>
, H/ W& t3 O  i2 V3 T4 d5 n4 {0 R<>void create();
void banner();
: S2 Y2 F  d$ o2 D( odouble dabs(double d);
void findinit();
. N5 n; a( |) v/ Wvoid computeuv();
int check();
int  circle(enum direction dir,struct element cir[],int *t);
void improve();
void output();</P>
<>void main() {
banner();
create();
, w0 b- a6 B1 m5 L! z0 d6 m( F printf("\n按回车确认后开始求解");
1 d7 t$ ]. {' |* G/ U% Z5 |8 O getchar();
2 }: O0 y& `- }6 r+ d  ~! _. d getchar();
2 ]# _2 C* H  |4 v9 X, n findinit();
improve();
switch(status) {
case 1:
  output();
  puts("\n原问题有唯一最优解。\n");
  puts("\n按回车结束");
  getchar();
  exit(0);
case -1:
  output();
  puts("\n原问题有无穷多最优解。\n");
% ?" q! O* q3 i+ G( u  puts("\n按回车结束");
  getchar();
/ k( V1 `7 A8 L  exit(0);
}
$ |1 e) v6 b" v; {- H6 M4 b}</P>
<>void banner() {
* ~" s5 ~% U2 H% K  R$ Q printf("\t\t****************************************\n");
9 B2 [( u4 P4 w& x printf("\t\t         表上作业法解运输问题\n");
printf("\t\t                              Thunder\n");
7 ]  R3 ?- a9 w9 @ printf("\t\t****************************************\n");
printf("\n");
}</P>
+ t9 d' F" E! A$ z5 }* m  d& Y<>void create() {
int i,j;
double sum_a,sum_b;
. b3 @& T7 I2 i- g' a char confirm;
4 L# a2 y9 I' Z4 }. X while(1) {
/ U/ }; X3 ~: g# B7 T  printf("请输入产地个数：");
  scanf("%d",&amp;num_a);
+ v4 _$ ~# x& [  ?' y  for(i=1;i&lt;=num_a;i++) {
   printf("A%d产量：",i);
$ N+ V$ I, I5 b) A" A: u* y   scanf("%lf",&amp;a);
  }
  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;
  else if(confirm=='n') continue;
}
while(1) {
/ x/ V/ Q% e- R4 M2 j  printf("\n请输入销地个数：");
  scanf("%d",&amp;num_b);
  for(i=1;i&lt;=num_b;i++) {
   printf("B%d销量：",i);
   scanf("%lf",&amp;b);
  }
  for(i=1;i&lt;=num_b;i++) printf("B%d销量：%lg\t",i,b);
  printf("\n正确吗？：(y/n)");
' b) q7 x/ R1 r+ Q0 @. B% M0 b+ u  getchar();
$ _  q7 V' f6 t7 G) R3 n- B, p  confirm=getchar();
  if (confirm=='y') break;
5 h" Y& c0 ^3 b1 i6 r! s) T  else if(confirm=='n') continue;
}
putchar('\n');
0 m* A1 F  Q/ r. T7 u for(i=1;i&lt;=num_a;i++) {
$ V3 R% M0 f& x  for(j=1;j&lt;=num_b;j++) {
+ j* u! p! W! D7 `   printf("A%d到B%d运价：",i,j);
7 u! h! R; T( B; I3 y' C( h; s) F   scanf("%lf",&amp;ab[j]);
- q+ U# ?& M2 Q  U$ W9 `- k. I9 \5 e  }
* `9 M2 C; F6 X  for(j=1;j&lt;=num_b;j++) printf("A%d到B%d：%lg\t",i,j,ab[j]);
4 F( W2 M. m" Q: X0 {; N! ^/ P- f  printf("\n正确吗？：(y/n)");
  getchar();
. v" y0 z( ~, J1 _# Z+ C  confirm=getchar();
  if(confirm=='n') i--;
  putchar('\n');
0 L; m9 b% a: B }
//处理产销不平衡的情况
sum_a=sum_b=0;
/ j" s* n, b- E for(i=1;i&lt;=num_a;i++) sum_a+=a;
for(i=1;i&lt;=num_b;i++) sum_b+=b;</P>
- y+ @$ X) |" a% P<> printf("总产量：%lg\t总销量：%lg",sum_a,sum_b);
$ v: e  e' k9 \5 z2 a4 ` if(sum_a==sum_b) printf("\t产销平衡。");
else if(sum_a&gt;sum_b) {
- u( i3 a, z, @! [/ W0 N$ O! X  printf("\t供大于求，增加假想销地B%d。\n",++num_b);
  b[num_b]=sum_a-sum_b;
) l1 R8 v) w- ~# s8 R% v% S  for(i=1;i&lt;=num_a;i++) ab[num_b]=0;
- y7 q1 E' K2 i- s3 z  ^% J) [. P/ f }
else if(sum_a&lt;sum_b){
$ l: ]+ `1 c' s4 s  printf("\t供不应求，增加假想产地A%d。\n",++num_a);
& r. o( J0 @* y! [  H  a[num_a]=sum_b-sum_a;
/ b3 g- b/ y* m5 |  F  for(i=1;i&lt;=num_b;i++) ab[num_a]=0;
  i+ m! {; _* _* M }
//求解前的准备
+ B$ A$ |* y7 c/ d4 [ for(i=1;i&lt;=num_a;i++)
" ?% y+ a3 ^- x  for(j=1;j&lt;=num_b;j++)
5 m3 W$ d+ Y7 ?' z) }2 E   base[j]=pbase[j]=0;
7 J1 H4 b, Q. _( T- m) d" ` for(i=1;i&lt;=num_a;i++) temp_a=a;
: s; _. S; G8 L! T. g% w) F for(i=1;i&lt;=num_b;i++) temp_b=b;
- U/ _: G5 ^3 E$ ~3 W for(i=1;i&lt;=num_a;i++)
for(j=1;j&lt;=num_b;j++) temp_ab[j]=ab[j];
/ {# a# b3 j+ A1 _" B1 c, U- f //回显问题
printf("\n\n原问题为：\n\n");
) H2 w$ a7 o7 Q   printf("产量：\n ");
for(i=1;i&lt;=num_a;i++) printf("A%d:%lg\t",i,a);
printf("\n运量：\n ");
4 B; z. o' L4 I( Q9 |* J for(i=1;i&lt;=num_b;i++) printf("B%d:%lg\t",i,b);
printf("\n运价为：\n");
for(i=1;i&lt;=num_a;i++) {
  putchar(' ');
  for(j=1;j&lt;=num_b;j++)
   printf("A%d-&gt;B%d:%lg\t",i,j,ab[j]);
  putchar('\n');
}
}</P>
& E7 w5 _5 B( c/ T0 }  l<>double dabs(double d) {
5 L2 z" C: Y  z5 i& m) ?- { if(d&gt;=0) return d;
else return -d;
}</P>
. p; k2 m0 O. {" u- M<>void findinit() {
2 {: A$ @5 y: S( T/ R0 A" Q int i,j,k;
double r_penum[MAX],c_penum[MAX];
6 V) _5 E! J/ i- N struct largest {
4 G/ X4 Z4 `  R6 E# L" s  char rc;
  int num;
  double value;
};
6 e) Q# y$ j6 z% L) P* M+ }! d3 t struct largest lar1,lar2;
' |4 u, L: N0 }1 `5 T' K9 A% V1 y int r=0,c=0;
double a1,a2,b1,b2,temp;</P>
<> for(i=1;i&lt;=num_a;i++) {
$ H9 b( I+ G1 [$ N  temp=temp_ab[1];
. l7 l2 y* Y( P1 D; O- h* q  for(j=1;j&lt;=num_b;j++)
   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
5 T, B: Z0 ~9 p" Q/ `( a+ H  a1=a2=temp;
  for(j=1;j&lt;=num_b;j++)
   if(temp_ab[j]&lt;=a1) {
+ L4 \$ d4 W/ ~4 o0 z/ `: q! p) `    a2=a1;
    a1=temp_ab[j];
   }
  Q& A9 m: l; H' L$ r" J1 J# T% S   else if(temp_ab[j]&lt;=a2) a2=temp_ab[j];
  r_penum=dabs(a1-a2);
2 c/ ]( g3 H! T" E2 z" U$ R, l }</P>
  N& e  f) Q$ C- `( Z+ |+ }<> for(i=1;i&lt;=num_b;i++) {
0 r6 D- V/ a. D; a& J7 i+ a0 k  temp=temp_ab[1];
1 h. s8 X. T) X( i$ D7 d  for(j=1;j&lt;=num_a;j++)
7 }8 y- w) }; n" h; o% ]   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
  b1=b2=temp;
6 a0 C% b4 `0 ~' X* x. O7 A  for(j=1;j&lt;=num_a;j++)  
, a- U; }  Z# A5 V% ^   if(temp_ab[j]&lt;=b1) {
3 c' l+ ?# y! D" D6 Q    b2=b1;
# c# }: F. q# N' J6 E    b1=temp_ab[j];
   }
   else if(temp_ab[j]&lt;=b2) b2=temp_ab[j];
& t0 L0 ]% E" u; `8 O* \  c_penum=dabs(b1-b2);
}
/*
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);
*/
0 E; k! D" e$ m2 Y0 i7 J- \* m 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>
<> //考虑了有两个罚数相等的情况，大于两个相等只取其中两个进行比较
4 q7 m* w5 ~2 X8 i- B0 U, q9 z5 L lar1.value=lar2.value=temp;
8 @5 M+ d$ g% }# s: W9 ]" a( E lar1.num=lar2.num=1;
lar1.rc=lar2.rc='r';
for(i=1;i&lt;=num_a;i++)
  if(r_penum&gt;=lar1.value) {
7 x. u7 w2 L2 L4 @6 n   lar2=lar1;
* s3 ]" e  e( k  o9 p0 ~2 I- g   lar1.rc='r';
   lar1.num=i;
& M1 z* U( H6 H+ c   lar1.value=r_penum;
# S4 N& H) T* E. w' Y* y  }
; H9 I6 S8 M$ |7 P  else if(r_penum&gt;=lar2.value) {
; D' @6 \7 {; [1 H   lar2.rc='r';
* w2 K9 W) Q( J5 r& f& N# ]   lar2.num=i;
   lar2.value=r_penum;
  }</P>
<> for(i=1;i&lt;=num_b;i++)
$ K3 `# a6 N, X( f# G7 ^! m9 L  if(c_penum&gt;=lar1.value) {
% |5 \: W! o- D6 \: R" E4 I( ^! K   lar2=lar1;
   lar1.rc='c';
- C/ w* Y! f* w( S   lar1.num=i;
- J. G& V$ o! b7 D: T: W) Y   lar1.value=c_penum;
  }
' \/ X: V: F6 A7 o' U  else if(c_penum&gt;=lar2.value) {
   lar2.rc='c';
* X/ ?* }' p# ?6 n+ v. b2 L   lar2.num=i;
, ?- _! m" b9 R- D   lar2.value=c_penum;
7 v  p8 h+ }8 L3 B. p' b  }</P>
, f* g) o$ v1 q( S2 v, s4 X5 G<> if(lar1.value==lar2.value&amp;&amp;(lar1.num!=lar2.num||lar1.rc!=lar2.rc)) {
- c8 {. ]. e0 c/ e  if(lar1.rc=='r'&amp;&amp;lar2.rc=='r') {
   temp=temp_ab[lar1.num][1];
5 {( h" R# E# {- Z- S   r=lar1.num;
      c=1;
7 Z  z# U6 }& U' L   for(i=1;i&lt;=num_b;i++) {
/ U0 `4 s* Q5 o' w0 v0 ~, v" f7 Z    if(temp_ab[lar1.num]&lt;temp) {
     temp=temp_ab[lar1.num];
     r=lar1.num;
% d) D2 b- D* D/ u     c=i;
    }
# ^) B- G$ U0 ^# ]$ @& b    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
     r=lar2.num;
     c=i;
, B: z7 r: x6 N5 N& H% h    }
$ f2 `  R; B3 Q  `& ?   }
  }
  if(lar1.rc=='c'&amp;&amp;lar2.rc=='c') {
( r  H6 l/ b6 R& ?9 S1 [   temp=temp_ab[1][lar1.num];
& T8 K( u9 O$ s1 n$ r$ n7 w   r=1;
      c=lar1.num;
   for(i=1;i&lt;=num_a-1;i++) {
# k) Z! z( X  K, I! |! K6 c0 a! B) P    if(temp_ab[lar1.num]&lt;temp) {
7 V0 S1 _0 |2 X; _     temp=temp_ab[lar1.num];
$ P4 R+ \/ x1 K/ h" Y0 h- \" h# Q3 ^     c=lar1.num;
4 U/ I% R4 R6 F& p  j/ v     r=i;
    }
6 ^+ E  [5 t( O( [( d" k    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
     c=lar2.num;
     r=i;
    }
0 A* g) l" B& w( {; A   }
+ f! c. {& K: l$ G  }
' v8 G; S' S* ]2 y. ^+ b  if(lar1.rc=='r'&amp;&amp;lar2.rc=='c') {
; ]5 W1 _3 d. ~0 O' l) {2 z5 g  a   temp=temp_ab[lar1.num][1];
   r=lar1.num;
, O+ V6 L! u5 a. `      c=1;
   for(i=1;i&lt;=num_b;i++)
    if(temp_ab[lar1.num]&lt;temp) {
' Y' Z4 B6 p( j+ Z     temp=temp_ab[lar1.num];
1 [. N! W- I% M     r=lar1.num;
     c=i;
* b" t3 T6 D' \' A    }
   for(i=1;i&lt;=num_a;i++)
6 \2 |' h/ R" x$ h9 Z& _    if(temp_ab[lar2.num]&lt;temp) {
# c4 w* m) u. r" j, `  K% B7 [4 k     temp=temp_ab[lar2.num];
     c=lar2.num;
- _/ Y. l, P/ m3 F5 g     r=i;
    }
  }
) m6 b! @1 ^; i  if(lar1.rc=='c'&amp;&amp;lar2.rc=='r') {
   temp=temp_ab[1][lar1.num];
( N. M9 I# u" y& O+ C0 T   r=1;
      c=lar1.num;
   for(i=1;i&lt;=num_b;i++)
' p, A' k; u; }+ i: a! Q# B- B    if(temp_ab[lar2.num]&lt;temp) {
" y$ C( J6 ^) j! [! R     temp=temp_ab[lar2.num];
/ C8 {5 K7 D0 w     r=lar2.num;
; q$ ^3 H0 w) O     c=i;
    }
   for(i=1;i&lt;=num_a;i++)
    if(temp_ab[lar1.num]&lt;temp) {
: O" ^( C, n8 V! P' r     temp=temp_ab[lar1.num];
5 A1 V, M" E. Y% @+ r/ j) D8 Q     c=lar1.num;
( W3 d! C# k% v8 b. Q6 z+ [6 Z6 a     r=i;
    }
  }
}
/ ^! ^- K: n" }- ~# k! f else {
" a! d: e# [& ]/ F# L- M( E  if(lar1.rc=='r') {
   r=lar1.num;
. `" B9 v4 u( u4 g3 }2 a   c=1;
   temp=temp_ab[lar1.num][1];
8 |2 q- i7 N6 G' b- m   for(i=1;i&lt;=num_b;i++)
    if(temp_ab[lar1.num]&lt;temp) {
     c=i;
# A# ^; ~  k7 `& {! `2 {     temp=temp_ab[lar1.num];
    }
  }
  else {
   r=1;
   c=lar1.num;
   temp=temp_ab[1][lar1.num];
: \. |4 n. R5 z5 x6 j2 S) L   for(i=1;i&lt;=num_a;i++)
    if(temp_ab[lar1.num]&lt;temp) {
     r=i;
: H, t2 d& s' v     temp=temp_ab[lar1.num];
- d1 p" t% M0 d- u; p6 F3 E    }
  }
, K8 j% g1 y0 K, z }
pbase[r][c]=1;
1 Y6 B5 S! P( E4 @: ?7 Y; O# ? if(temp_a[r]&gt;temp_b[c]) {
  base[r][c]=temp_b[c];
6 [1 j, L- u! J  J' |3 e! v- e  C  temp_a[r]=temp_a[r]-temp_b[c];
1 h* G( J2 H+ Q' e8 I% F$ i* j+ ~  temp_b[c]=0;
  for(i=1;i&lt;=num_a;i++) temp_ab[c]=M;
% t7 [( I4 l7 y }
else if(temp_a[r]&lt;temp_b[c]) {
' n+ j3 T) `2 M7 ~$ Q- z4 }6 I% I  base[r][c]=temp_a[r];
$ B; m: j# ^: B2 @7 ]  temp_b[c]=temp_b[c]-temp_a[r];
5 K$ Y" A. ^7 Z; y9 n- g  temp_a[r]=0;
  for(i=1;i&lt;=num_b;i++) temp_ab[r]=M;
}
+ m4 m% S9 r& @- O# F+ k else if(temp_a[r]==temp_b[c]) {
, j7 S1 J1 U9 M7 R; J% |  base[r][c]=temp_a[r];
  temp_a[r]=temp_b[c]=0;
0 t7 F6 `* I4 [. L9 V  for(i=1;i&lt;=num_a;i++) temp_ab[c]=M;
  for(i=1;i&lt;=num_b;i++) temp_ab[r]=M;
  k=0;
% t; H1 P8 X+ e5 D3 q  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;
% U5 C3 f8 N2 u; ^1 l* \8 S% z8 y  if(k!=0) {
& u/ O( }( a2 _% e; k: B   k=0;
( R; b- z% l5 |# r  Y   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;
   else if(k==2) pbase[r][j]=1;
! K8 d1 j8 i4 e- l7 d; o. J  }
3 r" T% [2 e9 K! ]! h }
0 k) m. H' h! B1 c$ o! {) Z/ c+ b6 j( o k=0;
1 X+ X  [8 I6 d  f- H* 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;
4 |, r. `; G' Q if(k==0) return;
findinit();
}</P>
8 y% I+ H, m/ Z: {$ a- ^1 \+ r. J" y<>void computeuv() {
int i,j,k;
for(i=1;i&lt;=num_a;i++)
/ S. p5 q& m, N  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==1) {
    if(pu==1) {v[j]=ab[j]-u; pv[j]=1;}
2 O6 ^# l' ?! Q0 O5 q' i6 O    if(pv[j]==1) {u=ab[j]-v[j]; pu=1;}
   }
k=0;
; [# f8 ]2 a' A' @- | 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;
, [! z% g% i4 i. d* a- e' X6 \ if(k==1) computeuv();
}</P>
<>int check() {
) c4 L/ x5 |7 |. Z9 d- V. k int i,j,k,l;
k=l=0;
' E. x9 }1 k1 d for(i=1;i&lt;=num_a;i++)
+ m; N3 s+ U0 f- Y  o  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;
   }
3 d5 r. s) ]9 F1 D% |/* for(i=1;i&lt;=num_a;i++){
  for(j=1;j&lt;=num_b;j++) printf("base %lg\t",base[j]);
  putchar('\n');}
for(i=1;i&lt;=num_a;i++){
+ y- d* z3 V9 O  [9 |  for(j=1;j&lt;=num_b;j++) printf("pbase %d\t",pbase[j]);
  putchar('\n');}
: G4 N) u( \, L; }# J! k; w*/
& r8 R# j! [& c/ l4 G& g/ i& B if(k==0&amp;&amp;l==0) {status=1; return 1;}
# m3 @+ M$ J9 E; m+ x else if(k==0&amp;&amp;l!=0) {status=-1; return 1;}
6 T6 V8 }2 O/ ~. }! e else return 0;
9 Y0 f8 f+ i9 {}</P>
) y* u2 G+ @) U% W/ D<>int circle(enum direction dir,struct element cir[],int *t) {
# I* E3 A! e8 Z% j4 Q4 b+ L int i,j,k;
1 a! @$ H8 d- } /*
6 m$ q2 @# ]  n) P) d putchar('\n');
0 G! Q' Y( U1 b+ } for(i=1;i&lt;=*t;i++) printf("%d: r%d c%d\t",i, cir.r,cir.c);
8 V+ ^0 c0 \2 i9 s7 k. O putchar('\n');
*/
* N8 |7 \% ]4 n: U  x7 F if((*t)!=1&amp;&amp;cir[(*t)].r==cir[1].r&amp;&amp;cir[*t].c==cir[1].c) {
  t--;
. Z0 U5 G+ F$ {: i  return 1;
}
if(dir!=down) {
5 f- z4 X- |: \# L1 z( h  S' q( {  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) {
1 `4 A& }3 x8 ]   if(dir==up) cir[*t].value=0;
   else cir[*t].value=1;
   (*t)++;
2 W% O+ C" Z) a" d4 s   cir[*t].r=i;
5 n: g4 h% l) E5 |   cir[*t].c=cir[(*t)-1].c;
3 |4 q' H# p/ |( {, t( z- {   if(circle(up,cir,t)) return 1;
  }
}
6 y& {- D3 a, g& C1 `, F, U if(dir!=up) {
  k=0;
  for(i=cir[*t].r+1;i&lt;=num_a;i++)
$ Q/ d7 O. h/ A7 t* J   if(pbase[cir[*t].c]==1||(i==cir[1].r&amp;&amp;cir[*t].c==cir[1].c)) {k=1; break;}
! R9 I9 f4 X& _( h1 l% [6 V  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==down) cir[*t].value=0;
   else cir[*t].value=1;
- Q4 O4 h/ H8 \! X$ V& t/ a- x$ t' J% ?   (*t)++;
   cir[*t].r=i;
5 X" S9 e4 Z' {' A4 {6 r5 a   cir[*t].c=cir[(*t)-1].c;
; [& Q' e# n9 R9 U   if(circle(down,cir,t)) return 1;
8 p& b% y& W& j7 S. K8 N  }
4 d# U  ?$ \& q# O; z( J1 e$ _, w }
if(dir!=right) {
: [6 P" L( S, _- a  A  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;
7 S% v5 E4 Y' e( n, ?5 m   else cir[*t].value=1;
" J: G8 B# @6 E   (*t)++;
   cir[*t].r=cir[(*t)-1].r;
   cir[*t].c=i;
9 N, y# v0 B! B6 c+ b6 e5 N   if(circle(left,cir,t)) return 1;
# h" ]0 M+ I5 M  }
}
* z: S6 f) A' m. Z. H9 G if(dir!=left) {
  k=0;
( u+ z. F2 Q9 B9 q0 a  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;
5 m& f  f$ S3 e+ k  if(k==1) {
1 ~  a" Z6 y$ V   if(dir==right) cir[*t].value=0;
( C' c: R$ n. V   else cir[*t].value=1;
   (*t)++;
6 ~. o# u% H' e% K" ]8 L+ v   cir[*t].r=cir[(*t)-1].r;
" v  u4 R9 ]2 w4 ]6 H" X/ t$ n1 w# d   cir[*t].c=i;
! [# h5 @4 g) V5 ^   if(circle(right,cir,t)) return 1;
  }
}
(*t)--;
return 0;
}</P>
<>void improve() {
int i,j,k,t;
5 k1 ?! y* J  g1 H7 p8 O) I struct element base_in,base_out,cir[2*MAX+1];</P>
" V* T8 B' s% R) \1 Y<> for(i=1;i&lt;=num_a;i++) pu=0;
for(i=1;i&lt;=num_b;i++) pv=0;
1 ]0 c2 T% s/ K" J9 t1 w+ d u[1]=0; pu[1]=1;
$ H! D! @0 z( q+ R computeuv();
6 L8 K# T; J: {0 J; K% l if(check()) return;
8 s7 D/ R$ V0 B for(i=1;i&lt;=num_a;i++)
: @+ ]& Y! p, e# D3 C4 a  for(j=1;j&lt;=num_b;j++)
' V2 z1 P4 ?# l- R* B   if(pbase[j]==0) break;
base_in.r=i;
& ]- ^3 e  z! w: J' D base_in.c=j;
base_in.value=base[j];</P>
<> for(i=1;i&lt;=num_a;i++)
  for(j=1;j&lt;=num_b;j++)
0 h5 F6 G1 ^2 h5 D" A. G   if(pbase[j]==0&amp;&amp;base[j]&lt;base_in.value) {
    base_in.r=i;
$ v2 v! E. Y& `8 d% m, P    base_in.c=j;
& ?3 c( w$ x& k6 l! y/ _    base_in.value=base[j];
& a" \( ?- f1 K) b   }</P>
<> t=1;
cir[t].r=base_in.r;
2 A% c+ D# l3 j! ~4 w( S cir[t].c=base_in.c;
cir[t].value=1;
if(!circle(mid,cir,&amp;t)) {
  printf("程序出错！按回车结束");
  getchar();
  exit(0);
: ?% q9 T: G. I# } }
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>
1 |& q7 v# T+ [; X) |% _) h7 T<> for(i=2;i&lt;=t;i++) if(cir.value==1) break;
base_out=cir;
base_out.value=base[cir.r][cir.c];
) w: `; L/ U7 T* B: U k=1;
5 U2 s" h6 K. O% N# D# T0 f for(i=1;i&lt;=t;i++)
7 E& W( o+ z8 D) x" ~& W& K. _  if(k%2==0&amp;&amp;cir.value==1&amp;&amp;base[cir.r][cir.c]&lt;base_out.value) {
, Y5 t( O  _9 p& D2 U( n8 ~   base_out=cir;
   base_out.value=base[cir.r][cir.c];
$ l+ c- ^$ C8 \$ u! d   k++;
  }
+ Q! L) {; M/ O8 R+ t  else if(cir.value==1) k++;
9 G" M' ~. Z! h* D+ O( [ base[cir[1].r][cir[1].c]=0;
1 h" ]. @7 _: E k=1;
$ \0 P/ C" R+ i7 }$ |% W for(i=1;i&lt;=t;i++) {
  if(k%2==1&amp;&amp;cir.value==1) {
   base[cir.r][cir.c]+=base_out.value;
   k++;
  }
  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>
1 ?2 Z* K- @: j  @0 B<> improve();
}</P>
1 J1 m, }5 N5 L' I1 Y/ _+ E<>void output() {
5 A( W1 M/ t( y+ h1 r int i,j;
9 P) o6 g" L4 G& I8 ^ double sum=0;
printf("\n运量为：\n");
1 [5 C$ k! p! J" n9 z1 R& y for(i=1;i&lt;=num_a;i++) {
  putchar(' ');
- E& Q$ z% d! h7 k8 R$ P  for(j=1;j&lt;=num_b;j++)
# y0 Z& z& I; J   if(pbase[j]==1) {
    printf("A%d-&gt;B%d:%lg\t",i,j,base[j]);
    sum+=base[j]*ab[j];
# j! ?$ m1 c% d/ U( m" {5 K   }
   else printf("A%d-&gt;B%d:0\t",i,j);
" Q. o- i0 J1 b- E+ `  putchar('\n');
9 Z* v" L: ~( j4 u' y; s }
printf("\n最低总运费为：%lg\n",sum);
}
8 u$ ~' d3 U2 c</P>

zhongguohelin

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

enrique08

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

hzlhm

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

liunengwu

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