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

plgatc

<>/*************************************************************************
                         表上作业法解运输问题        
) [* {+ Z" G; L7 L5 b: X; ]* Z: {( R
9 |- u4 z9 P* h 编程环境：VC++6.0     
程序说明：
8 b2 Y% ^' p8 F3 A Vogel法求初始解，位势法检验是否最优，递归搜索闭回路改进解。
*************************************************************************/
#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;</P>
<>#define MAX 100
#define M 999999</P>
/ t) |6 V8 ~- s/ p& F# {<>int status; //1唯一最优解，-1无穷多最优解</P>
<>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];
+ Q  q7 X/ d5 Sdouble base[MAX][MAX];
1 v, g2 E$ n# tint pbase[MAX][MAX];
struct element {
int r;
int c;
* d9 M& q) Z1 [2 h# ] double value;
};
enum direction {mid,up,down,left,right};</P>
- J, ]. U# J; C# z6 X1 x. a<>void create();
: W% u7 P/ _4 Evoid banner();
+ s0 f# n& S: Q, I7 e8 `$ Adouble dabs(double d);
3 C# P9 T1 X3 X6 Pvoid findinit();
void computeuv();
int check();
int  circle(enum direction dir,struct element cir[],int *t);
& a! {/ M# F3 v2 O. b' @void improve();
7 e0 K& l" b/ ~void output();</P>
1 R) L$ b) r& A% W$ `. \( \; S<>void main() {
banner();
0 G& s2 I, s" W' Z4 R0 c7 }& k0 Y create();
printf("\n按回车确认后开始求解");
! m* f) \- k$ ^4 ?# ^. ~; M* X5 I getchar();
# ~# ], |& I) k( V& x getchar();
findinit();
improve();
) ^4 Z5 G/ W: x0 w( o) q- d switch(status) {
. M* O8 `+ e8 B case 1:
  output();
  puts("\n原问题有唯一最优解。\n");
  puts("\n按回车结束");
  getchar();
) |$ G  c+ Q* L( z* E$ I4 ^& K  exit(0);
, c6 m( }" r1 l2 p4 H! a case -1:
  j+ C& d# m; K  output();
5 p2 f. ]6 ?$ F# K  puts("\n原问题有无穷多最优解。\n");
  puts("\n按回车结束");
  getchar();
1 N5 G8 R0 E. w( O- F  exit(0);
) ?; ?6 l) g; Q$ x }
" K! |, A" w0 y}</P>
<>void banner() {
printf("\t\t****************************************\n");
1 S% I1 t  c; X- H# k4 G  D! k printf("\t\t         表上作业法解运输问题\n");
2 Q: R) S' i9 D+ y printf("\t\t                              Thunder\n");
4 M8 R) x/ c. N1 f" c printf("\t\t****************************************\n");
printf("\n");
4 d& }- R, d2 a5 B}</P>
<>void create() {
int i,j;
double sum_a,sum_b;
/ z+ M' h# q, J! U9 R% j# f char confirm;
while(1) {
: b+ e0 V% T* l* ^  printf("请输入产地个数：");
  scanf("%d",&amp;num_a);
  for(i=1;i&lt;=num_a;i++) {
   printf("A%d产量：",i);
   scanf("%lf",&amp;a);
$ Z- c6 L5 V$ D' q/ j  }
2 X6 j  P. \) @  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;
/ j; L5 c- a1 W  else if(confirm=='n') continue;
4 e3 J5 ~0 Y* v' B }
while(1) {
+ {" j  p% A0 _* e  printf("\n请输入销地个数：");
* F; a% m4 a  ^9 u& `/ Q! M  scanf("%d",&amp;num_b);
  for(i=1;i&lt;=num_b;i++) {
7 q) g. `2 l) a2 Q   printf("B%d销量：",i);
   scanf("%lf",&amp;b);
3 Y: \* ?& E* A! G  }
- T6 J) R- n% U  z9 _  for(i=1;i&lt;=num_b;i++) printf("B%d销量：%lg\t",i,b);
0 u! a9 j0 q9 ~# R4 ]. |7 Q# U% {9 O  printf("\n正确吗？：(y/n)");
( `' k7 b  T4 j  M9 R  getchar();
% K2 |  [9 }, Q8 {: [  confirm=getchar();
  if (confirm=='y') break;
  else if(confirm=='n') continue;
}
putchar('\n');
) z1 E6 l" r- X0 z; W for(i=1;i&lt;=num_a;i++) {
* z/ i5 I$ T4 w( a8 v$ x  for(j=1;j&lt;=num_b;j++) {
+ y2 O& ~- `7 b  T/ G# c1 j, b   printf("A%d到B%d运价：",i,j);
8 A# k) _! X$ J+ E  d   scanf("%lf",&amp;ab[j]);
  }
! h* |9 f+ c6 k. k/ R  for(j=1;j&lt;=num_b;j++) printf("A%d到B%d：%lg\t",i,j,ab[j]);
' T' c$ a- D/ f/ r* v& u8 u7 O  printf("\n正确吗？：(y/n)");
, V) N0 |0 K) W! Z; l  getchar();
  confirm=getchar();
  if(confirm=='n') i--;
1 C7 k# h1 ^' h5 N0 \* z" \" j; K4 j  putchar('\n');
/ U+ l7 {  ]1 C5 e# r) I }
8 H! ]- ~6 G8 ]$ S //处理产销不平衡的情况
sum_a=sum_b=0;
for(i=1;i&lt;=num_a;i++) sum_a+=a;
  H' a5 P( N. q. m for(i=1;i&lt;=num_b;i++) sum_b+=b;</P>
7 A2 W! i' m5 k: Q<> printf("总产量：%lg\t总销量：%lg",sum_a,sum_b);
if(sum_a==sum_b) printf("\t产销平衡。");
$ [) \) H# E8 ~; l' [- i* R& u5 @ else if(sum_a&gt;sum_b) {
/ X, z, d. W, u# h/ N  printf("\t供大于求，增加假想销地B%d。\n",++num_b);
  b[num_b]=sum_a-sum_b;
% X5 j3 O# @* V7 Y  for(i=1;i&lt;=num_a;i++) ab[num_b]=0;
}
else if(sum_a&lt;sum_b){
" ^! W9 t6 I! L3 F8 z; R  printf("\t供不应求，增加假想产地A%d。\n",++num_a);
# O) J" ^( Y2 [7 Y/ w5 n" t( L; M! z  a[num_a]=sum_b-sum_a;
0 i2 v: ^7 X, {" K  for(i=1;i&lt;=num_b;i++) ab[num_a]=0;
! L. T5 s1 g  Z9 I1 @# Y* G( V5 A }
//求解前的准备
for(i=1;i&lt;=num_a;i++)
7 Y) J7 _6 v; c$ ~1 X, O2 d' h  for(j=1;j&lt;=num_b;j++)
   base[j]=pbase[j]=0;
/ g) b  ?: z4 [2 t- q4 w7 [" c for(i=1;i&lt;=num_a;i++) temp_a=a;
for(i=1;i&lt;=num_b;i++) temp_b=b;
9 u7 _* a8 _( A7 H" H( J+ j for(i=1;i&lt;=num_a;i++)
for(j=1;j&lt;=num_b;j++) temp_ab[j]=ab[j];
//回显问题
; h- l  k% J9 s8 D, Q. F printf("\n\n原问题为：\n\n");
% f$ X3 s! F/ _2 A   printf("产量：\n ");
for(i=1;i&lt;=num_a;i++) printf("A%d:%lg\t",i,a);
printf("\n运量：\n ");
& F/ ?  q0 n2 a 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(' ');
% B1 b+ n2 R; f: Q5 Y* T9 l  for(j=1;j&lt;=num_b;j++)
   printf("A%d-&gt;B%d:%lg\t",i,j,ab[j]);
  putchar('\n');
}
}</P>
<>double dabs(double d) {
" a/ p; [5 y* x$ W3 y3 p if(d&gt;=0) return d;
! F4 B5 U1 u/ j1 \, E else return -d;
}</P>
6 S5 {# Q. i, @1 O9 y<>void findinit() {
2 ^. g7 h- N# a. d int i,j,k;
# r( }5 C8 x0 D6 h& D. N+ ` double r_penum[MAX],c_penum[MAX];
struct largest {
; N7 u2 Y" S, B' E2 p% x  `  char rc;
  int num;
8 ~8 Y; o) U9 X9 `! V7 s8 _  double value;
};
3 f  t& g" Q5 O; r# W/ ~/ S struct largest lar1,lar2;
int r=0,c=0;
% X  C, N+ b' c2 m8 L" D double a1,a2,b1,b2,temp;</P>
<> for(i=1;i&lt;=num_a;i++) {
! m5 h" n8 _. ~$ Z8 h  \& w  temp=temp_ab[1];
  for(j=1;j&lt;=num_b;j++)
1 q: p4 }* X3 `0 S) t3 k+ E   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
) X9 U$ H- U5 v, ?  a1=a2=temp;
  for(j=1;j&lt;=num_b;j++)
" N. |; q+ F6 O! A4 M" Q1 D! \7 M   if(temp_ab[j]&lt;=a1) {
    a2=a1;
    a1=temp_ab[j];
; E" ^& T' r5 q1 A( a   }
   else if(temp_ab[j]&lt;=a2) a2=temp_ab[j];
  r_penum=dabs(a1-a2);
}</P>
<> for(i=1;i&lt;=num_b;i++) {
  temp=temp_ab[1];
+ O+ s! m: S  v: B5 T9 U  for(j=1;j&lt;=num_a;j++)
   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
+ P5 A, Z' z" h# H5 n: D; A  b1=b2=temp;
  for(j=1;j&lt;=num_a;j++)  
   if(temp_ab[j]&lt;=b1) {
( h+ O8 Q& P- x    b2=b1;
    b1=temp_ab[j];
* P% Y) o/ ^3 n' o) P! I   }
   else if(temp_ab[j]&lt;=b2) b2=temp_ab[j];
  c_penum=dabs(b1-b2);
}
. m, u& s9 a; K7 F( b: K3 e* M, u /*
for(i=1;i&lt;=num_a;i++) printf("pa%d=%lg ",i,r_penum);
putchar('\n');
  D" r/ z6 \* h4 R* D& J for(i=1;i&lt;=num_b;i++) printf("pb%d=%lg ",i,c_penum);
*/
) i% a1 `- |( p5 p 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>
9 Q5 E: c- P' @$ G% V: F* h<> //考虑了有两个罚数相等的情况，大于两个相等只取其中两个进行比较
lar1.value=lar2.value=temp;
lar1.num=lar2.num=1;
lar1.rc=lar2.rc='r';
for(i=1;i&lt;=num_a;i++)
, J- h' [9 ^3 J* H  if(r_penum&gt;=lar1.value) {
   lar2=lar1;
9 s3 Y" U& {. _# G0 w   lar1.rc='r';
   lar1.num=i;
   lar1.value=r_penum;
  }
$ ?5 `" o7 I0 ~% n  else if(r_penum&gt;=lar2.value) {
9 y* ?0 A# l+ e1 T1 S6 h6 n, R/ j   lar2.rc='r';
- h6 J- a, I2 R   lar2.num=i;
   lar2.value=r_penum;
  }</P>
<> for(i=1;i&lt;=num_b;i++)
  if(c_penum&gt;=lar1.value) {
8 j2 V5 M8 F- ]1 E: W   lar2=lar1;
/ G6 D5 U' i- ?( Z   lar1.rc='c';
* I0 t- N) @. g   lar1.num=i;
   lar1.value=c_penum;
+ K3 g6 j: A4 F" M" A) ~7 `  }
  else if(c_penum&gt;=lar2.value) {
   lar2.rc='c';
   lar2.num=i;
   lar2.value=c_penum;
& k8 I. o# K. m5 N4 U  }</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') {
+ p5 N+ t, ^5 g8 x   temp=temp_ab[lar1.num][1];
   r=lar1.num;
      c=1;
; b. i6 y, E! \3 h' O   for(i=1;i&lt;=num_b;i++) {
5 ^9 u- R0 d  w! R/ ^    if(temp_ab[lar1.num]&lt;temp) {
     temp=temp_ab[lar1.num];
     r=lar1.num;
) \- A8 u4 P4 D2 ~8 C! `     c=i;
: I0 q& s, w/ g* Z7 s( M" `' K0 Y    }
    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
     r=lar2.num;
3 @4 C6 ?9 ?! P8 M9 c     c=i;
    }
  v5 @) t* _" Q: G   }
( y- @* S( K7 h7 _' ]/ d  }
8 s% T, L2 G; {! O9 X' N5 t  if(lar1.rc=='c'&amp;&amp;lar2.rc=='c') {
) e2 A& c) [/ F: ^. r2 m1 i7 N; K) E   temp=temp_ab[1][lar1.num];
   r=1;
7 v/ ^) H' [+ q/ b% Q* g      c=lar1.num;
! B9 |- |4 Z2 r* f3 K   for(i=1;i&lt;=num_a-1;i++) {
    if(temp_ab[lar1.num]&lt;temp) {
' P7 _) x7 [3 l' X9 G4 C     temp=temp_ab[lar1.num];
     c=lar1.num;
     r=i;
    }
    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
4 g& I4 ~1 g. K6 Z- z1 G. d     c=lar2.num;
4 s# U8 {' P2 I     r=i;
    }
. {( |7 |6 U4 V+ M   }
  }
6 ?3 e' [! C7 @3 ~. I  if(lar1.rc=='r'&amp;&amp;lar2.rc=='c') {
2 q: @) P, h* a$ o* Z! b; u   temp=temp_ab[lar1.num][1];
   r=lar1.num;
      c=1;
/ I3 T. z& Q$ {# a" P/ C/ O   for(i=1;i&lt;=num_b;i++)
    if(temp_ab[lar1.num]&lt;temp) {
     temp=temp_ab[lar1.num];
) G! Y2 k! f7 E( }; p. Q     r=lar1.num;
7 K9 i& N. `- B     c=i;
    }
+ Y1 ]7 I" j# X. r   for(i=1;i&lt;=num_a;i++)
" m0 A: H7 m9 B    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
& V7 M: E. C+ k6 q     c=lar2.num;
' A; w, m4 V& p- D0 L     r=i;
    }
  }
  if(lar1.rc=='c'&amp;&amp;lar2.rc=='r') {
( J, C% _8 q" D* ~/ }   temp=temp_ab[1][lar1.num];
   r=1;
      c=lar1.num;
5 Q3 m% d* t; d  b7 k+ @   for(i=1;i&lt;=num_b;i++)
    if(temp_ab[lar2.num]&lt;temp) {
8 {* L# W, T) S! x0 [& N     temp=temp_ab[lar2.num];
     r=lar2.num;
     c=i;
& g3 P) K; ^  G- S4 K7 l    }
9 @* N+ v7 H$ R   for(i=1;i&lt;=num_a;i++)
% L# x- ]4 f9 b# M# L    if(temp_ab[lar1.num]&lt;temp) {
" Z! J/ H4 x. d$ I8 C% h     temp=temp_ab[lar1.num];
" E$ h: e- h* I+ n# F     c=lar1.num;
! ]6 j& l: |' i4 g* o. s& Y; T     r=i;
    }
7 _$ N) ?0 E' [6 O  }
}
else {
$ M+ C! k$ J1 X  if(lar1.rc=='r') {
   r=lar1.num;
   c=1;
   temp=temp_ab[lar1.num][1];
$ T$ }4 C# v, j! d   for(i=1;i&lt;=num_b;i++)
    if(temp_ab[lar1.num]&lt;temp) {
4 P7 g5 Y( F7 [6 _+ }8 q' I     c=i;
# i! [5 S  S8 j$ S6 E7 L2 H     temp=temp_ab[lar1.num];
) v! j1 _& j- }. P    }
  }
  else {
& j0 K1 h, L* m# F* D$ [7 _8 J# r8 u   r=1;
   c=lar1.num;
   temp=temp_ab[1][lar1.num];
6 S$ Z+ T6 \: O! o1 P( [   for(i=1;i&lt;=num_a;i++)
    if(temp_ab[lar1.num]&lt;temp) {
     r=i;
     temp=temp_ab[lar1.num];
7 j! g) Y: k5 _: D% d    }
  [7 G+ F3 d- l$ M  }
}
pbase[r][c]=1;
if(temp_a[r]&gt;temp_b[c]) {
  base[r][c]=temp_b[c];
  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;
6 Y7 t9 z  D0 @4 y9 R4 t }
else if(temp_a[r]&lt;temp_b[c]) {
  base[r][c]=temp_a[r];
  temp_b[c]=temp_b[c]-temp_a[r];
6 i- e7 W3 A- b& E  temp_a[r]=0;
  for(i=1;i&lt;=num_b;i++) temp_ab[r]=M;
}
4 B8 L0 Z6 s9 H" X else if(temp_a[r]==temp_b[c]) {
. C8 R3 h! e9 ~  base[r][c]=temp_a[r];
5 C8 R4 O4 C' ^  I. ?$ l  temp_a[r]=temp_b[c]=0;
% r7 q$ d  H+ `  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;
  for(i=1;i&lt;=num_a;i++) if(temp_a!=0) k=1;
/ u  x! P" a' K! F- v6 M  for(i=1;i&lt;=num_b;i++) if(temp_b!=0) k=1;
; O+ ?. a  |+ h9 Y8 M  if(k!=0) {
   k=0;
" D+ Z' ^2 |  ?" P# Z$ O   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;
# z1 b# J  _9 @% x) i   else if(k==2) pbase[r][j]=1;
  }
% q; P$ E; X/ d  V+ R* n' ^4 w }
k=0;
for(i=1;i&lt;=num_a;i++) if(temp_a!=0) k=1;
/ G& T$ U: ~$ D. g9 ?5 K( \ for(i=1;i&lt;=num_b;i++) if(temp_b!=0) k=1;
if(k==0) return;
$ v: _' L* ]2 `+ A  g- z4 A findinit();
* j( r# k1 `" o, g8 ?6 z}</P>
<>void computeuv() {
int i,j,k;
for(i=1;i&lt;=num_a;i++)
, D- I. P' f0 T2 _2 y3 w* @% J  for(j=1;j&lt;=num_b;j++)
3 Q; k' M2 X; l, L   if(pbase[j]==1) {
" {( C2 w$ T' X+ f3 H6 G    if(pu==1) {v[j]=ab[j]-u; pv[j]=1;}
3 ?/ [3 t* H5 Z& p" d    if(pv[j]==1) {u=ab[j]-v[j]; pu=1;}
/ Y  `* W# ]: q% C3 B& _3 U   }
k=0;
for(i=1;i&lt;=num_a;i++) if(pu==0) k=1;
, ~4 [6 O7 }0 o. k! K! L$ s for(i=1;i&lt;=num_b;i++) if(pv==0) k=1;
if(k==1) computeuv();
}</P>
<>int check() {
- h9 c1 a; v7 R6 A int i,j,k,l;
( x% P3 H9 f; T5 T) s k=l=0;
for(i=1;i&lt;=num_a;i++)
  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==0) {
    base[j]=ab[j]-u-v[j];
/ O) N1 t& J; Z, |. M9 G    if(base[j]&lt;0) k=1;
    else if(base[j]==0) l=1;
   }
# t" n6 Q' `: v. U9 Y/* for(i=1;i&lt;=num_a;i++){
  for(j=1;j&lt;=num_b;j++) printf("base %lg\t",base[j]);
! W3 \) D+ w8 S# c: T7 f  putchar('\n');}
. X9 |) x9 u3 C$ F for(i=1;i&lt;=num_a;i++){
1 U' Q( k2 n$ X. p: Z  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;
7 I0 \7 Y; u) _4 t( K- K5 [! s, G4 T}</P>
1 t' X% n( E1 ]( y6 Q<>int circle(enum direction dir,struct element cir[],int *t) {
int i,j,k;
9 T* y. |  I% y( I /*
6 Z3 B+ W" {# f$ E putchar('\n');
for(i=1;i&lt;=*t;i++) printf("%d: r%d c%d\t",i, cir.r,cir.c);
putchar('\n');
6 U! w+ z3 Z7 q. O* y; R; Q */
if((*t)!=1&amp;&amp;cir[(*t)].r==cir[1].r&amp;&amp;cir[*t].c==cir[1].c) {
3 e7 _6 a; E5 |$ h, D  t--;
  return 1;
' O8 U  H4 A: U4 O, f* Z2 R }
if(dir!=down) {
  k=0;
  for(i=cir[*t].r-1;i&gt;=1;i--)
9 {# f3 X7 }2 N. F: Y. l   if(pbase[cir[*t].c]==1||(i==cir[1].r&amp;&amp;cir[*t].c==cir[1].c)) {k=1; break;}
! c) j7 E$ M* a* H  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) {
( L- }+ S$ e8 O/ c/ r2 ~% ]   if(dir==up) cir[*t].value=0;
   else cir[*t].value=1;
   (*t)++;
* X* ?* D1 _1 I. ?* s% a4 F   cir[*t].r=i;
- x2 F$ `; s# n9 C1 p3 P8 j% H   cir[*t].c=cir[(*t)-1].c;
6 \& I9 y( c  O; U   if(circle(up,cir,t)) return 1;
1 X9 ^2 f6 n8 Q: g* s4 M  }
) i- V2 V* m# g9 v }
if(dir!=up) {
# Z/ X5 C, {2 ^( S3 p" M5 A  k=0;
0 b$ L! m' w9 Y+ Q! ~$ i9 N9 G  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;
& M/ J+ r8 W! C; W' H  if(k==1) {
   if(dir==down) cir[*t].value=0;
. L  c: O& [$ C6 d   else cir[*t].value=1;
   (*t)++;
( ?8 e1 ], u$ r. Q$ A   cir[*t].r=i;
& D" C* F' c8 g' n3 s0 d' e   cir[*t].c=cir[(*t)-1].c;
   if(circle(down,cir,t)) return 1;
4 t, t# F; @( T% B( v% v  }
9 A, @$ k: U; u9 O0 x }
3 |1 ?+ \5 ~! h2 H' u& k" a& u% O if(dir!=right) {
5 t7 O: I) ]/ h  k=0;
  for(i=cir[*t].c-1;i&gt;=1;i--)
/ D- }5 O: x9 x/ |   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;
+ I, r2 c4 l( Y0 O  if(k==1) {
   if(dir==left) cir[*t].value=0;
* V+ X: F; @" e   else cir[*t].value=1;
: X6 R. W" L& x& d   (*t)++;
   cir[*t].r=cir[(*t)-1].r;
   cir[*t].c=i;
   if(circle(left,cir,t)) return 1;
0 L/ p$ L* I4 B8 _" j  }
4 ^0 K$ H, o; \/ I" t- `. m5 j }
if(dir!=left) {
  k=0;
  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;
  if(k==1) {
0 [' K7 l9 {! X+ h) u3 ?* d& f   if(dir==right) cir[*t].value=0;
6 F: _; q) m) M' p1 d4 a  V/ u: |   else cir[*t].value=1;
4 F. s/ K) t) B* W! ]' |+ O! G   (*t)++;
- M7 o7 _0 w6 V/ G8 u   cir[*t].r=cir[(*t)-1].r;
. z/ \. A: d* K2 m, B0 u   cir[*t].c=i;
; v* _+ m" j# c& Z( x   if(circle(right,cir,t)) return 1;
  }
6 w: s' g0 n5 p$ h6 }) D+ @ }
(*t)--;
return 0;
}</P>
<>void improve() {
int i,j,k,t;
3 R$ O9 y: L1 n# a struct element base_in,base_out,cir[2*MAX+1];</P>
1 `/ b% F& l9 r% r) _<> for(i=1;i&lt;=num_a;i++) pu=0;
% \( r' W: V( K) q, D% s' E for(i=1;i&lt;=num_b;i++) pv=0;
$ z: O5 k  \3 y  e3 m7 q- Q) } u[1]=0; pu[1]=1;
computeuv();
6 ?% F- ]4 v2 W: m$ i  Q, Q if(check()) return;
for(i=1;i&lt;=num_a;i++)
- A; }7 e3 e. \1 v7 V, Q$ U  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==0) break;
4 ~1 U" _: L9 x9 u base_in.r=i;
* D1 i3 |$ }; L" B3 e7 p base_in.c=j;
base_in.value=base[j];</P>
$ u$ N$ Z4 U  y7 s" a! _<> for(i=1;i&lt;=num_a;i++)
) y- n( @/ K. h! Z3 t' z0 w  for(j=1;j&lt;=num_b;j++)
; }  p7 Q  T$ i" N   if(pbase[j]==0&amp;&amp;base[j]&lt;base_in.value) {
2 }$ U3 g7 E! ]' Z    base_in.r=i;
1 _8 h+ N+ K, w, |! E0 k: v- I    base_in.c=j;
: }( ^) m) |2 K: f: s% `- B    base_in.value=base[j];
. C+ ~) P" p( @% Y   }</P>
5 _$ Q: y5 ~7 F. I/ B6 L/ X, v# F& e<> t=1;
  c& ]- G+ Z- E6 y# F2 M cir[t].r=base_in.r;
2 I. E9 p% k" ^& C cir[t].c=base_in.c;
# D# U0 @! \( \* ~: o cir[t].value=1;
if(!circle(mid,cir,&amp;t)) {
2 O+ y% j! B! b  printf("程序出错！按回车结束");
  getchar();
5 b8 O# f! x- q8 X3 F/ Z( T' ?  exit(0);
}
) g1 W- U$ ~7 Z$ E( r' r+ E t--;
- G8 [! K0 a. N" E6 j' `// 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;
# o4 Q1 x3 b' V% u. a1 ? base_out=cir;
5 ~6 a! {5 K) e6 b base_out.value=base[cir.r][cir.c];
k=1;
  }- }9 C$ y+ }* E for(i=1;i&lt;=t;i++)
& e$ b6 k. x3 f% W5 x  if(k%2==0&amp;&amp;cir.value==1&amp;&amp;base[cir.r][cir.c]&lt;base_out.value) {
   base_out=cir;
9 u$ B2 D. O+ n0 ^; w   base_out.value=base[cir.r][cir.c];
+ a, v2 E3 Q0 h" b4 q   k++;
6 K: M1 P# b0 ^( d; X/ M+ d5 l+ W8 j  }
- `& j' B- z* M4 P& X3 @- ~5 h) G  else if(cir.value==1) k++;
base[cir[1].r][cir[1].c]=0;
8 `' z1 w+ Q+ T" \8 l" W/ { k=1;
2 y1 d" R, r. z  i- e* ~5 _% O for(i=1;i&lt;=t;i++) {
  if(k%2==1&amp;&amp;cir.value==1) {
7 N; Z" v# y: v1 @' M   base[cir.r][cir.c]+=base_out.value;
5 K: H5 g7 Q0 z4 R. ^0 z! T   k++;
% V' u: z  v  Y6 S! p; a  }
( C- E' e. \+ X' P0 P  else if(k%2==0&amp;&amp;cir.value==1) {
- ?9 ~$ d. e% d! M4 {& ~   base[cir.r][cir.c]-=base_out.value;
' P' f+ C# ^' T   k++;
# t3 B; L' I$ G  P$ u  }
}
pbase[base_out.r][base_out.c]=0;
pbase[base_in.r][base_in.c]=1;</P>
. b8 m  N# ]: R<> improve();
( z7 F1 x, ~+ g0 y}</P>
<>void output() {
+ P+ _( {) ]1 N int i,j;
double sum=0;
  H, X, ?  z; Z3 S- ?& ^- W+ o4 y" X printf("\n运量为：\n");
for(i=1;i&lt;=num_a;i++) {
  putchar(' ');
. |  q7 ]. A* r6 z" C2 K  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==1) {
    printf("A%d-&gt;B%d:%lg\t",i,j,base[j]);
; \' O  m9 \" K" M    sum+=base[j]*ab[j];
. u! T# u8 e7 B1 z# ^! C   }
1 G4 M3 ]3 e( q' q1 U   else printf("A%d-&gt;B%d:0\t",i,j);
  putchar('\n');
}
printf("\n最低总运费为：%lg\n",sum);
  X+ h: V7 z0 ~1 v  B. g" v}
  E; s7 [. d$ f! K8 q9 L8 z) z! m</P>

zhongguohelin

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

enrique08

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

hzlhm

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

liunengwu

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