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

plgatc

<>/*************************************************************************
                         表上作业法解运输问题        
4 }0 J) D1 j3 I/ o/ B7 F: M
& @# {) ~6 \7 y( A8 _ 编程环境：VC++6.0     
6 _3 R6 o: W' k 程序说明：
; T& u, f5 U: ^ Vogel法求初始解，位势法检验是否最优，递归搜索闭回路改进解。
5 N4 d! y2 `6 O3 H/ m" h *************************************************************************/
) E7 y9 p: `, m- e#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;</P>
<>#define MAX 100
0 t& q4 f3 ?9 J& t#define M 999999</P>
! x: L% @/ Y( }9 _<>int status; //1唯一最优解，-1无穷多最优解</P>
<>int num_a,num_b;
double a[MAX],b[MAX],temp_a[MAX],temp_b[MAX];
* c8 u/ ]. v* s7 idouble u[MAX],v[MAX],pu[MAX],pv[MAX];
/ Q2 S  a9 a3 ]8 y1 jdouble ab[MAX][MAX],temp_ab[MAX][MAX];
double base[MAX][MAX];
& D& T, J4 C% \9 @9 @0 `  R6 ?" Gint pbase[MAX][MAX];
6 b2 z- @2 w7 B9 e% G2 F6 m) x  lstruct element {
% L' ~" \( A& q: W+ N( u7 r int r;
int c;
double value;
};
enum direction {mid,up,down,left,right};</P>
# @0 E0 L) F+ t8 A<>void create();
void banner();
double dabs(double d);
void findinit();
void computeuv();
int check();
; P; g0 p0 D; B3 @9 Zint  circle(enum direction dir,struct element cir[],int *t);
void improve();
void output();</P>
<>void main() {
: C  s' D2 {. {$ {* k2 F% l- A" \, h banner();
create();
% r5 z9 s. s# n2 F% ?* b( M printf("\n按回车确认后开始求解");
2 f$ x) X# ]4 P; b7 v2 U) |  ^7 f getchar();
getchar();
3 e  y& Q# F  V findinit();
; N' V  S0 m  d1 O0 s: o  @ improve();
3 v; o. Z* l* @, F- j0 w switch(status) {
case 1:
  output();
  puts("\n原问题有唯一最优解。\n");
! p0 ^8 V1 N. l' f  puts("\n按回车结束");
/ T! h) [/ s! F# G' C# r3 b0 P- |  getchar();
  exit(0);
case -1:
  output();
  puts("\n原问题有无穷多最优解。\n");
  puts("\n按回车结束");
  getchar();
0 z* `; I1 a/ {% x. r. R8 M$ T  exit(0);
) ]" ?% A" T% ~- v }
6 M2 A  r7 e" }7 r6 ~* u1 Y}</P>
<>void banner() {
printf("\t\t****************************************\n");
- t/ Y) k5 N6 B printf("\t\t         表上作业法解运输问题\n");
printf("\t\t                              Thunder\n");
printf("\t\t****************************************\n");
printf("\n");
( \2 X0 H6 Z3 Q  ?& d8 S}</P>
  `' p2 N  j; D/ @8 a<>void create() {
7 ~! M3 a6 Y( i+ N int i,j;
double sum_a,sum_b;
char confirm;
while(1) {
  printf("请输入产地个数：");
  scanf("%d",&amp;num_a);
  for(i=1;i&lt;=num_a;i++) {
9 J- V, ^# Z7 k   printf("A%d产量：",i);
/ O( Y. S; Y. 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();
" X' E" b  Y$ R9 S* F  confirm=getchar();
  if (confirm=='y') break;
  else if(confirm=='n') continue;
( x' b: Q1 k' u; | }
while(1) {
" F0 e" U' Y; l. U; b  printf("\n请输入销地个数：");
( i  {  b4 e! H( z& K" D  scanf("%d",&amp;num_b);
  for(i=1;i&lt;=num_b;i++) {
# ]/ ~; Q+ f7 @5 M   printf("B%d销量：",i);
   scanf("%lf",&amp;b);
  }
2 [1 W( r4 c+ X4 _  for(i=1;i&lt;=num_b;i++) printf("B%d销量：%lg\t",i,b);
  printf("\n正确吗？：(y/n)");
9 E. J' I! l1 g3 v8 x  getchar();
  confirm=getchar();
9 |! t  N) Y, L7 }/ S4 n; A9 T& b  if (confirm=='y') break;
  else if(confirm=='n') continue;
}
putchar('\n');
9 c6 `6 f2 o. R8 X for(i=1;i&lt;=num_a;i++) {
  for(j=1;j&lt;=num_b;j++) {
   printf("A%d到B%d运价：",i,j);
( O  c4 J; I2 A3 d   scanf("%lf",&amp;ab[j]);
  }
3 M* O7 h2 B/ a+ x( o  for(j=1;j&lt;=num_b;j++) printf("A%d到B%d：%lg\t",i,j,ab[j]);
  printf("\n正确吗？：(y/n)");
  getchar();
  confirm=getchar();
) T! n3 w9 R! e: T  if(confirm=='n') i--;
  putchar('\n');
. M5 x* H& F' A }
- m3 C2 X3 }" R! A, e- X* C //处理产销不平衡的情况
sum_a=sum_b=0;
for(i=1;i&lt;=num_a;i++) sum_a+=a;
0 S  v8 T9 h7 \% I, ^4 A for(i=1;i&lt;=num_b;i++) sum_b+=b;</P>
<> printf("总产量：%lg\t总销量：%lg",sum_a,sum_b);
% I# \. z) L. D: Q if(sum_a==sum_b) printf("\t产销平衡。");
else if(sum_a&gt;sum_b) {
  printf("\t供大于求，增加假想销地B%d。\n",++num_b);
  b[num_b]=sum_a-sum_b;
& p% b  r6 d8 K; ^" q! k0 m  for(i=1;i&lt;=num_a;i++) ab[num_b]=0;
. |: Z3 C  t: F, a1 {$ i- [ }
0 u/ s- f, o/ J else if(sum_a&lt;sum_b){
; H- p: P. J$ f9 K3 W1 t  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;
- `' X/ w( {& T- X4 b }
( Q6 \# `* J2 n  r9 G //求解前的准备
for(i=1;i&lt;=num_a;i++)
  for(j=1;j&lt;=num_b;j++)
   base[j]=pbase[j]=0;
for(i=1;i&lt;=num_a;i++) temp_a=a;
/ r4 ^6 {# X2 \. U' P/ `3 g 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];
//回显问题
printf("\n\n原问题为：\n\n");
7 ^3 g5 x  h' ~' D, m8 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);
6 _) {- M& h/ Y9 L. P7 b1 T7 m printf("\n运价为：\n");
; s) D5 E& p% e. L" r! H for(i=1;i&lt;=num_a;i++) {
4 h: ], M! u/ S  putchar(' ');
+ R, ]# i- d1 `) `! n9 d; r  for(j=1;j&lt;=num_b;j++)
& G0 I3 l. p* w, l  M0 K, Z   printf("A%d-&gt;B%d:%lg\t",i,j,ab[j]);
  putchar('\n');
( a5 F. l$ @, G6 i4 @ }
3 R0 O- _7 S9 b* }}</P>
<>double dabs(double d) {
if(d&gt;=0) return d;
else return -d;
% ~: l% a- S6 S" A# v& {8 L  v' c}</P>
# U9 y& \- J# q7 v<>void findinit() {
" D* [1 P. K7 U int i,j,k;
" R/ W& O8 J% \$ f* l double r_penum[MAX],c_penum[MAX];
struct largest {
  char rc;
  int num;
% A8 K# e% B! b2 _! H  double value;
};
& _, I8 P. G8 v% } struct largest lar1,lar2;
+ k! U, W% ?1 h$ c& _3 J7 P int r=0,c=0;
double a1,a2,b1,b2,temp;</P>
$ w% B% v7 C$ e! d9 O<> for(i=1;i&lt;=num_a;i++) {
, N) D: y# c2 \3 s  temp=temp_ab[1];
  for(j=1;j&lt;=num_b;j++)
+ O) y3 S! Q6 [7 r$ ^1 w! j! R0 [   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
  a1=a2=temp;
* ~! `" \, D2 Y, W! G# U  for(j=1;j&lt;=num_b;j++)
   if(temp_ab[j]&lt;=a1) {
4 f. R# ]% N/ |' |    a2=a1;
    a1=temp_ab[j];
   }
   else if(temp_ab[j]&lt;=a2) a2=temp_ab[j];
4 n9 Q$ ^; i9 V% V9 ^" ?  r_penum=dabs(a1-a2);
}</P>
<> for(i=1;i&lt;=num_b;i++) {
  temp=temp_ab[1];
2 Z8 M* M6 A* K$ i  for(j=1;j&lt;=num_a;j++)
" H0 ~6 U; e5 m   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
$ k4 ]. g% D4 {7 J# ^  b1=b2=temp;
% w! ~2 c9 d- A" S6 R% f  for(j=1;j&lt;=num_a;j++)  
   if(temp_ab[j]&lt;=b1) {
    b2=b1;
    b1=temp_ab[j];
   }
; e( A3 N' K/ F% F   else if(temp_ab[j]&lt;=b2) b2=temp_ab[j];
  c_penum=dabs(b1-b2);
8 m4 Z' m- U1 d$ w" x& m) l }
/*
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);
6 T* D8 `) Y+ J( s$ J5 Y7 D6 M */
- s5 _: X( o- e& M$ d2 ^ 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>
  U% b: }  T) Z7 |3 ^$ A& l; l<> //考虑了有两个罚数相等的情况，大于两个相等只取其中两个进行比较
lar1.value=lar2.value=temp;
7 b, g! y' M9 {: Q lar1.num=lar2.num=1;
8 B4 z& _, z8 F" d9 ^2 j lar1.rc=lar2.rc='r';
. j, G7 j) f' J% o( j for(i=1;i&lt;=num_a;i++)
  if(r_penum&gt;=lar1.value) {
   lar2=lar1;
& _$ q$ J/ M& f7 u  O& H# o1 a" c   lar1.rc='r';
   lar1.num=i;
   lar1.value=r_penum;
  }
0 G2 B1 s& L6 o8 l  s( {9 x  else if(r_penum&gt;=lar2.value) {
   lar2.rc='r';
7 K. S; ~. O! r( j, @* k1 U   lar2.num=i;
   lar2.value=r_penum;
  }</P>
<> for(i=1;i&lt;=num_b;i++)
2 t. J% ~* n/ ?0 f  if(c_penum&gt;=lar1.value) {
0 p% g+ K  _4 {9 r2 A   lar2=lar1;
   lar1.rc='c';
& K  m' A0 U) L( e  z/ A7 g   lar1.num=i;
$ b, @( B( i  t% x4 s! P! R, _4 E, Y5 s   lar1.value=c_penum;
8 C$ @# b/ ^5 N1 S  }
8 R5 U& Z# }8 N% b+ S3 U7 u  else if(c_penum&gt;=lar2.value) {
   lar2.rc='c';
   lar2.num=i;
' n- B6 q4 L. G9 }. l% j1 c   lar2.value=c_penum;
  }</P>
<> if(lar1.value==lar2.value&amp;&amp;(lar1.num!=lar2.num||lar1.rc!=lar2.rc)) {
  if(lar1.rc=='r'&amp;&amp;lar2.rc=='r') {
7 x5 l3 f. W0 D. ?   temp=temp_ab[lar1.num][1];
   r=lar1.num;
' d% G: w1 t& J* F# Q) P      c=1;
   for(i=1;i&lt;=num_b;i++) {
! B' U/ D0 w$ f3 [7 [    if(temp_ab[lar1.num]&lt;temp) {
/ ?: A, ]. G' \0 E5 `/ X) G     temp=temp_ab[lar1.num];
     r=lar1.num;
9 c6 q" V: T# q, R* B     c=i;
( T+ m* v1 S! n" r( P. z. A' t    }
    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
     r=lar2.num;
1 m+ }) v+ g6 L) r7 s     c=i;
5 j% B- U% ?. y: r$ J* O    }
   }
  }
+ m1 X% K6 W2 v" L  if(lar1.rc=='c'&amp;&amp;lar2.rc=='c') {
   temp=temp_ab[1][lar1.num];
   r=1;
      c=lar1.num;
   for(i=1;i&lt;=num_a-1;i++) {
8 v, K8 B* V/ r9 B2 F& o3 M& _$ f    if(temp_ab[lar1.num]&lt;temp) {
  h% Q3 O* W0 a% {0 i% W; V7 W7 P     temp=temp_ab[lar1.num];
     c=lar1.num;
     r=i;
    }
9 k$ z* R  |' {- J0 ^4 b0 m. m    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
+ R8 @' x4 [' u4 i9 s1 {' n7 p     c=lar2.num;
     r=i;
    }
   }
  }
7 t. {% ?/ A0 T, z! y  if(lar1.rc=='r'&amp;&amp;lar2.rc=='c') {
% J- y3 N4 E# d, G7 Y   temp=temp_ab[lar1.num][1];
' ?, Z/ M5 N+ r   r=lar1.num;
1 n0 n4 S6 f. p" T8 S3 H" e# u      c=1;
& R# K5 M+ f1 I2 B, l1 q( r   for(i=1;i&lt;=num_b;i++)
& {: ?* x0 j. i3 q  z3 c    if(temp_ab[lar1.num]&lt;temp) {
. z# v. ^  ]2 i; i6 K6 w9 s0 q     temp=temp_ab[lar1.num];
& F( z8 [7 z8 ~     r=lar1.num;
& C4 d$ S+ C  w7 c9 [     c=i;
    }
   for(i=1;i&lt;=num_a;i++)
2 F( [& L; r! w7 _8 P    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
     c=lar2.num;
     r=i;
$ D! D6 H3 T% j# g    }
  }
* i1 Q- J6 y. k  i  V! |7 [, o) \; H  if(lar1.rc=='c'&amp;&amp;lar2.rc=='r') {
2 q+ w  x" B/ v) n   temp=temp_ab[1][lar1.num];
2 s. S9 r7 Z* S4 y/ m( ~( |/ H   r=1;
      c=lar1.num;
4 I0 Z& N  R' f9 W   for(i=1;i&lt;=num_b;i++)
0 r$ E( z% n- Q5 u    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
+ ~2 y/ y  O( k5 ]0 U# u     r=lar2.num;
* i$ Q2 b  F( z0 L( M2 l2 X     c=i;
7 Q# o  @. O/ o/ \1 E    }
, d$ [# u+ ?- p) g   for(i=1;i&lt;=num_a;i++)
    if(temp_ab[lar1.num]&lt;temp) {
, R9 L/ `% u0 x. N     temp=temp_ab[lar1.num];
8 u5 h: V2 C9 J( h" o     c=lar1.num;
     r=i;
    }
! I3 `" [) r; f+ f/ G" V* U0 L  }
}
else {
; k6 S  E2 ^6 R# k  if(lar1.rc=='r') {
: d2 v) @! ~$ ^) Z5 j' `" W   r=lar1.num;
   c=1;
8 L. x: r. ?' z   temp=temp_ab[lar1.num][1];
   for(i=1;i&lt;=num_b;i++)
; _! v6 L5 n3 z" S    if(temp_ab[lar1.num]&lt;temp) {
( f8 `+ @: @" q     c=i;
" V0 t4 U1 a6 U1 o. k) H     temp=temp_ab[lar1.num];
; z( n7 v$ y6 N& `3 |6 |    }
! A. H7 Q& p3 G1 H0 }  }
$ p) I* |3 z  o  else {
$ p% g; T( \4 M- K8 K" [0 D   r=1;
  l6 O% c& C0 Q' k9 Y$ y4 m+ _7 C   c=lar1.num;
   temp=temp_ab[1][lar1.num];
   for(i=1;i&lt;=num_a;i++)
, h/ X& s  |7 n3 p8 \! |+ G! p    if(temp_ab[lar1.num]&lt;temp) {
     r=i;
; D6 p8 f: p6 u+ ?2 Q8 r     temp=temp_ab[lar1.num];
* }+ E2 `3 o; O* G. ?/ i    }
+ p2 c9 a. O4 e5 O4 @+ I  }
}
8 X8 X( D. t3 Q( p pbase[r][c]=1;
if(temp_a[r]&gt;temp_b[c]) {
  base[r][c]=temp_b[c];
% f5 ?; `) {9 K( {) z- G& }  temp_a[r]=temp_a[r]-temp_b[c];
  temp_b[c]=0;
6 ^3 \9 M! U  \% N+ R  for(i=1;i&lt;=num_a;i++) temp_ab[c]=M;
}
8 f' {  J& N& c; O 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;
- }+ g- K3 X0 u1 M5 g) r  for(i=1;i&lt;=num_b;i++) temp_ab[r]=M;
}
, p  v9 p7 c* L1 ] else if(temp_a[r]==temp_b[c]) {
2 Z/ y' o& k  P  base[r][c]=temp_a[r];
8 M1 S1 C3 h0 h/ I  V8 Y- I  temp_a[r]=temp_b[c]=0;
  s* C/ |! z( l- c  for(i=1;i&lt;=num_a;i++) temp_ab[c]=M;
# P2 C5 W3 T7 b4 u% {  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) {
   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;}
, K# P8 Q' |3 V* M0 i+ H- q   if(k==1) pbase[c]=1;
+ I& |9 ~6 L' X) s9 Y, C6 ~$ l   else if(k==2) pbase[r][j]=1;
  }
5 x/ g8 f; @- M* C }
k=0;
6 Z5 z+ q2 l" C& Z# p+ U for(i=1;i&lt;=num_a;i++) if(temp_a!=0) k=1;
" j- j% v0 e" _3 _* s; i* w for(i=1;i&lt;=num_b;i++) if(temp_b!=0) k=1;
if(k==0) return;
findinit();
}</P>
<>void computeuv() {
0 H% q0 N% |: |& ^5 G0 K int i,j,k;
for(i=1;i&lt;=num_a;i++)
) @, r, r8 p# x7 g5 Y3 y  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==1) {
! l1 T/ K. l3 g% L* k    if(pu==1) {v[j]=ab[j]-u; pv[j]=1;}
# q2 f' ]$ J3 _/ ]2 ]    if(pv[j]==1) {u=ab[j]-v[j]; pu=1;}
" F& X) N7 l" m3 F& j   }
% X6 z9 l. q4 O7 s( \4 `  R& C k=0;
for(i=1;i&lt;=num_a;i++) if(pu==0) k=1;
. v4 ]( V# a2 S for(i=1;i&lt;=num_b;i++) if(pv==0) k=1;
if(k==1) computeuv();
}</P>
<>int check() {
, k9 L' p( J/ }5 m int i,j,k,l;
! A. }1 q4 u' [; W: D k=l=0;
for(i=1;i&lt;=num_a;i++)
) _; r' ^! U! n6 m  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;
/ v1 y) y  ?8 v3 J    else if(base[j]==0) l=1;
. }$ Z  Y1 J' y$ W2 f7 x# c! u   }
! ^/ H) Y2 n6 l2 ?) S8 p/* for(i=1;i&lt;=num_a;i++){
2 K: q  [0 E$ P- N  for(j=1;j&lt;=num_b;j++) printf("base %lg\t",base[j]);
  putchar('\n');}
' F) L6 X1 K# c- I' \6 U 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>
- h4 E7 m, L; t- }" {<>int circle(enum direction dir,struct element cir[],int *t) {
int i,j,k;
4 c- I7 \) \& H6 c  A /*
$ V" G7 l3 f! I putchar('\n');
. I: k" h; o9 z/ t for(i=1;i&lt;=*t;i++) printf("%d: r%d c%d\t",i, cir.r,cir.c);
putchar('\n');
  I" k$ H! v& m0 C& m, k */
if((*t)!=1&amp;&amp;cir[(*t)].r==cir[1].r&amp;&amp;cir[*t].c==cir[1].c) {
7 e' \; U, F% p  t--;
  return 1;
4 x1 k  C9 z9 l" }, S7 l7 j0 n }
if(dir!=down) {
  k=0;
  for(i=cir[*t].r-1;i&gt;=1;i--)
/ `7 p  V: M( I7 }4 I% G5 j5 E4 I   if(pbase[cir[*t].c]==1||(i==cir[1].r&amp;&amp;cir[*t].c==cir[1].c)) {k=1; break;}
* Y$ R( E0 c" i& }4 \1 V  for(j=2;j&lt;=*t;j++) if(i==cir[j].r&amp;&amp;cir[*t].c==cir[j].c) k=0;
7 @* `. U, Q! ?( u6 X: h2 R7 n$ l7 H  if(k==1) {
   if(dir==up) cir[*t].value=0;
   else cir[*t].value=1;
( c( q2 G: h4 U4 z" P: U   (*t)++;
   cir[*t].r=i;
& m% z5 z% ?1 d9 k; p" m( z   cir[*t].c=cir[(*t)-1].c;
; r  u- A/ n0 q- I9 L& J/ V7 R   if(circle(up,cir,t)) return 1;
- g" [3 v  ^6 N2 k1 F  }
( k: j: S. n: C& Y8 Y; x }
2 U, h% b  n' u% I2 I; k if(dir!=up) {
5 Q- r% m# @9 e  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;}
  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;
" @" h; x/ j9 ~1 K- [( d   else cir[*t].value=1;
$ h* g0 N' W& H! e; W   (*t)++;
1 {, b' d) {1 `/ X   cir[*t].r=i;
   cir[*t].c=cir[(*t)-1].c;
   if(circle(down,cir,t)) return 1;
  }
}
if(dir!=right) {
  k=0;
  for(i=cir[*t].c-1;i&gt;=1;i--)
' \( r2 |2 e4 {; }" U   if(pbase[cir[*t].r]==1||(cir[*t].r==cir[1].r&amp;&amp;i==cir[1].c)) {k=1; break;}
( b' G9 T1 Y7 b1 o) w6 o( U  for(j=2;j&lt;=*t;j++) if(cir[*t].r==cir[j].r&amp;&amp;i==cir[j].c) k=0;
5 t4 [9 ~0 k2 L: L* V$ v% }  if(k==1) {
4 K4 r: Z2 e' K9 [. Z$ _   if(dir==left) cir[*t].value=0;
& r% b" H9 _$ x7 {0 Z   else cir[*t].value=1;
( K$ A9 [/ M1 _! }   (*t)++;
   cir[*t].r=cir[(*t)-1].r;
   cir[*t].c=i;
0 _$ A$ e% k, h( {" C# D. Z   if(circle(left,cir,t)) return 1;
) |9 t5 M) p! z$ j2 L* u9 b  }
$ D) G* p% C- Z% E }
9 S3 L1 W4 }9 O if(dir!=left) {
3 i' ~/ v/ A5 S( p% ^  k=0;
  for(i=cir[*t].c+1;i&lt;=num_b;i++)
2 @9 R. Q' P  u6 h% @   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;
2 b- M9 i1 G2 r! `, k2 R% \   else cir[*t].value=1;
   (*t)++;
! C9 p, X* j" P  v9 p! ~! e6 E+ X   cir[*t].r=cir[(*t)-1].r;
   cir[*t].c=i;
: ^! L5 U1 X! a9 O   if(circle(right,cir,t)) return 1;
0 [3 v" y/ c7 F, L  }
}
2 t! n( j( w  }8 } (*t)--;
1 O1 C; d. H- G0 ^5 @ return 0;
}</P>
<>void improve() {
int i,j,k,t;
- A/ }/ n- w3 @ struct element base_in,base_out,cir[2*MAX+1];</P>
<> for(i=1;i&lt;=num_a;i++) pu=0;
" x* [/ h6 {4 t' U for(i=1;i&lt;=num_b;i++) pv=0;
8 Q! E5 Q% [4 `  M u[1]=0; pu[1]=1;
9 y# E* d" @% ^* ` computeuv();
3 l+ o) k! x! G( q2 E4 J if(check()) return;
" x2 y- q, g, d1 m for(i=1;i&lt;=num_a;i++)
* r/ F5 ]! {) N6 c# q1 z- ]  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==0) break;
* E  [" K, b' N" V1 @$ G7 a base_in.r=i;
9 ]9 ?  c$ P, \8 V6 g* f, }: y 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++)
( t# ?9 n; z, ^! T/ g, E   if(pbase[j]==0&amp;&amp;base[j]&lt;base_in.value) {
    base_in.r=i;
    base_in.c=j;
1 |& y: b1 r7 b! j2 ]8 W    base_in.value=base[j];
  F- Y( I9 z, s8 ~: Q5 m   }</P>
<> t=1;
cir[t].r=base_in.r;
8 U/ T8 Q1 ~; f& T' E0 ?) m cir[t].c=base_in.c;
5 x  W' z; C) n- o3 g$ I cir[t].value=1;
if(!circle(mid,cir,&amp;t)) {
5 \. N' ~% p1 U  printf("程序出错！按回车结束");
  getchar();
  exit(0);
}
' O. @9 s7 z  C, M$ Y# w8 t- q t--;
9 K8 s9 h4 n; ~2 b9 X// 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];
; p- d7 F6 Y  k$ K" r 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;
   base_out.value=base[cir.r][cir.c];
, n$ D  L0 S6 r   k++;
# l- K  G8 |3 Z4 r% N+ O7 n1 p  }
# G( R) W, X! u* I0 T6 b# J  else if(cir.value==1) k++;
base[cir[1].r][cir[1].c]=0;
8 v1 ]! k7 n8 p( M2 q0 Y k=1;
for(i=1;i&lt;=t;i++) {
) M7 G8 f$ W1 v8 V6 _; i1 K3 x  if(k%2==1&amp;&amp;cir.value==1) {
   base[cir.r][cir.c]+=base_out.value;
   k++;
$ h/ m4 \- w. C& X. u  }
* w7 s" Y$ W' \1 P6 t  else if(k%2==0&amp;&amp;cir.value==1) {
' D, e" s+ J- k- \$ b2 G, z   base[cir.r][cir.c]-=base_out.value;
) ~7 C9 w4 W1 s/ R( b+ ~   k++;
/ M. Z0 L% k& z$ c; ~" y: _+ D7 D: s  }
}
pbase[base_out.r][base_out.c]=0;
7 U! E( H# h/ a  Q- f6 a) X! h pbase[base_in.r][base_in.c]=1;</P>
<> improve();
}</P>
6 @4 j6 |) J" p$ b" d<>void output() {
int i,j;
; s: B7 [: P, S double sum=0;
* F8 g5 s7 Q4 T( t. C printf("\n运量为：\n");
for(i=1;i&lt;=num_a;i++) {
  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]);
    sum+=base[j]*ab[j];
   }
, `& V5 ^8 V5 [# w; S  F   else printf("A%d-&gt;B%d:0\t",i,j);
& M0 k  M8 V8 U4 A  putchar('\n');
# k8 d6 I5 L$ G5 g }
printf("\n最低总运费为：%lg\n",sum);
}
+ @! d- D3 g) B6 u! l</P>

zhongguohelin

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

enrique08

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

hzlhm

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

liunengwu

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