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

plgatc

<>/*************************************************************************
0 b# J1 V1 J$ V$ g/ |$ ~                         表上作业法解运输问题        

& G) v, m8 r% o# b1 f" }! i 编程环境：VC++6.0     
/ D/ L, o+ C% U- n 程序说明：
Vogel法求初始解，位势法检验是否最优，递归搜索闭回路改进解。
*************************************************************************/
( D# v$ @' i' M8 r  n1 W6 I* m7 u#include &lt;stdio.h&gt;
: W3 `2 ?2 J1 v3 x% H#include &lt;stdlib.h&gt;</P>
<>#define MAX 100
#define M 999999</P>
<>int status; //1唯一最优解，-1无穷多最优解</P>
<>int num_a,num_b;
2 h, }4 C# O, }6 Ldouble a[MAX],b[MAX],temp_a[MAX],temp_b[MAX];
: W0 l, E2 N+ o/ fdouble u[MAX],v[MAX],pu[MAX],pv[MAX];
double ab[MAX][MAX],temp_ab[MAX][MAX];
double base[MAX][MAX];
int pbase[MAX][MAX];
) \, [8 j& B- S4 Estruct element {
int r;
int c;
' u" X# c; p, P double value;
};
7 E! `, N5 h" Y  U; f! Y* renum direction {mid,up,down,left,right};</P>
& [! N. ^6 |/ |# K- y<>void create();
void banner();
double dabs(double d);
void findinit();
void computeuv();
, Z) A4 o4 n1 z. f2 Gint check();
int  circle(enum direction dir,struct element cir[],int *t);
; n% W. b. _8 R6 ?8 S4 i4 Y, svoid improve();
void output();</P>
<>void main() {
* i7 s; \# S: H( G/ y banner();
/ I, y- \3 Q9 y, k$ N, J  f9 }4 y create();
. v* h1 X8 S) i printf("\n按回车确认后开始求解");
getchar();
getchar();
findinit();
improve();
switch(status) {
8 x7 V  X+ ~5 z6 K3 I# A1 T case 1:
  output();
  puts("\n原问题有唯一最优解。\n");
  puts("\n按回车结束");
  getchar();
8 |; ?. x. b) M8 u- @$ v% a  exit(0);
# x1 c3 Y# t0 ?  y case -1:
  output();
2 V. `3 _( ]& ]0 }9 J1 w  puts("\n原问题有无穷多最优解。\n");
( |$ F" e7 n, q; l/ u, |  puts("\n按回车结束");
( f( @* U3 z# D, y  getchar();
( C$ X1 q3 e+ r7 I  exit(0);
}
}</P>
<>void banner() {
printf("\t\t****************************************\n");
printf("\t\t         表上作业法解运输问题\n");
& G3 L! V, P, o printf("\t\t                              Thunder\n");
printf("\t\t****************************************\n");
! h/ F! v$ Y4 l) l/ T* Y" u3 f8 a printf("\n");
, d& ~% L/ M# A( o6 G8 t}</P>
# y& c5 h% w2 T- x1 u! d2 j$ M( |0 B<>void create() {
int i,j;
double sum_a,sum_b;
char confirm;
/ H9 k! ~0 d. r8 h while(1) {
* p0 C* L8 y" E% Z4 M  printf("请输入产地个数：");
  scanf("%d",&amp;num_a);
  for(i=1;i&lt;=num_a;i++) {
   printf("A%d产量：",i);
3 @/ K; ?6 o% X- c7 e; K* L1 ~: `   scanf("%lf",&amp;a);
5 B7 ~/ D. p( |  }
) J2 w5 A+ z2 J! c+ P- o  for(i=1;i&lt;=num_a;i++) printf("A%d产量：%lg\t",i,a);
  s& G: z8 |; K: e8 ?  printf("\n正确吗？：(y/n)");
$ q6 W; f9 W9 h, y, C  getchar();
  confirm=getchar();
  if (confirm=='y') break;
  else if(confirm=='n') continue;
# j* g8 K/ O6 ^! K, p- e }
2 `& q, X8 @# A, D/ N while(1) {
  printf("\n请输入销地个数：");
8 s$ t4 L  a- d6 V3 J' f5 z  scanf("%d",&amp;num_b);
5 y- u/ X1 r' Y- ~  for(i=1;i&lt;=num_b;i++) {
' u: f3 a& M* t0 k. x7 H   printf("B%d销量：",i);
   scanf("%lf",&amp;b);
& i# M$ Z0 w/ t9 Z* F  }
  for(i=1;i&lt;=num_b;i++) printf("B%d销量：%lg\t",i,b);
8 O; ]& F' T/ c, L0 A  printf("\n正确吗？：(y/n)");
  getchar();
  confirm=getchar();
  if (confirm=='y') break;
  T. }- v1 B& M# ~5 C, b2 D  else if(confirm=='n') continue;
}
putchar('\n');
: t: s9 W% Q# z, }  S for(i=1;i&lt;=num_a;i++) {
  for(j=1;j&lt;=num_b;j++) {
6 r* V! _$ @0 Z/ h- `   printf("A%d到B%d运价：",i,j);
1 i2 T$ g9 Q' b: N0 k4 h1 _   scanf("%lf",&amp;ab[j]);
  }
  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();
  if(confirm=='n') i--;
  putchar('\n');
+ o& k: c) C; H# } }
//处理产销不平衡的情况
' T. r( y2 l3 c0 _2 K sum_a=sum_b=0;
, Z+ h9 t$ j. v9 Y4 U for(i=1;i&lt;=num_a;i++) sum_a+=a;
for(i=1;i&lt;=num_b;i++) sum_b+=b;</P>
* D2 v0 W1 ?( J9 H( C* G<> printf("总产量：%lg\t总销量：%lg",sum_a,sum_b);
if(sum_a==sum_b) printf("\t产销平衡。");
else if(sum_a&gt;sum_b) {
+ v) @+ \0 D' |% C* G% g  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;
}
: v4 \( F9 G! B5 k& e9 b else if(sum_a&lt;sum_b){
  printf("\t供不应求，增加假想产地A%d。\n",++num_a);
$ z3 e  n1 D) O" Y  a[num_a]=sum_b-sum_a;
  for(i=1;i&lt;=num_b;i++) ab[num_a]=0;
}
1 \% f8 K' W& l2 O# \  f8 X. z6 D //求解前的准备
for(i=1;i&lt;=num_a;i++)
  for(j=1;j&lt;=num_b;j++)
% j0 l% \4 Q+ m5 B- w$ a) C2 b5 f0 Q   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;
! W! J& A' [4 N' U  b& x% a for(i=1;i&lt;=num_a;i++)
, b& h% _. ?6 [1 }$ M( P7 ~. n for(j=1;j&lt;=num_b;j++) temp_ab[j]=ab[j];
0 J/ J6 ^/ q  C1 v/ F //回显问题
1 V1 y% c: P: X! n* j printf("\n\n原问题为：\n\n");
   printf("产量：\n ");
( M  n/ \3 k" ~" q. h& P& r 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);
printf("\n运价为：\n");
; I/ }( z0 k5 x/ H& { 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');
. R* `8 V! ^$ q& B0 X }
- m$ e- h, a5 L' C; t8 S4 ^# p! P}</P>
<>double dabs(double d) {
8 A6 [8 t6 @" ]& ? if(d&gt;=0) return d;
# T5 q. G& c6 b else return -d;
}</P>
8 V3 {; T- s& Q. Z; g# q<>void findinit() {
1 R/ }" h4 c( W  U' e0 n- J int i,j,k;
double r_penum[MAX],c_penum[MAX];
9 P" {8 ^% v$ t$ | struct largest {
. T: T4 R1 y6 h3 Z$ E0 i  char rc;
: d) b. Q9 I# j8 l, K' r) J5 g  int num;
  double value;
};
  o& L% E) Y9 i3 d6 E% {3 a struct largest lar1,lar2;
5 N# ^1 h+ V- P5 \! _1 `9 f int r=0,c=0;
3 n( P# d* f/ @6 P4 q* H* G0 q double a1,a2,b1,b2,temp;</P>
) b4 f3 |, m! }  U' V, }! z6 L<> for(i=1;i&lt;=num_a;i++) {
  temp=temp_ab[1];
  for(j=1;j&lt;=num_b;j++)
3 G) u+ e9 S' H" e! k   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
  a1=a2=temp;
! ~2 U, @& t+ b' w7 Y  for(j=1;j&lt;=num_b;j++)
* j, I! K# h: @* `( ^. V0 d  a   if(temp_ab[j]&lt;=a1) {
2 d5 B! Q. _2 C: C    a2=a1;
, s+ H. b! v/ Z7 Q8 d3 Q    a1=temp_ab[j];
   }
   else if(temp_ab[j]&lt;=a2) a2=temp_ab[j];
' F4 z( ?  K" z0 \9 W  r_penum=dabs(a1-a2);
! o0 Q  |% h1 e }</P>
" s& ^! O6 w) E6 g/ G<> for(i=1;i&lt;=num_b;i++) {
  temp=temp_ab[1];
  for(j=1;j&lt;=num_a;j++)
  I0 k# \3 K; B: p9 I5 G2 O   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;
5 y2 }6 H$ f  n) G; u: r    b1=temp_ab[j];
   }
   else if(temp_ab[j]&lt;=b2) b2=temp_ab[j];
  c_penum=dabs(b1-b2);
2 e& J( K3 J/ p0 i( K# q. \- n& | }
/*
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);
*/
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>
: A+ r! Y) T0 t+ f<> //考虑了有两个罚数相等的情况，大于两个相等只取其中两个进行比较
lar1.value=lar2.value=temp;
lar1.num=lar2.num=1;
: F2 d0 S: G7 T lar1.rc=lar2.rc='r';
/ v. d1 b! l3 p4 S* X for(i=1;i&lt;=num_a;i++)
  if(r_penum&gt;=lar1.value) {
   lar2=lar1;
   lar1.rc='r';
: I' C9 }' ?6 z$ X$ v! r   lar1.num=i;
   lar1.value=r_penum;
9 X8 E; }) v) j" A$ ~  }
  else if(r_penum&gt;=lar2.value) {
5 n2 R4 g& }& Y  J) S   lar2.rc='r';
   lar2.num=i;
   lar2.value=r_penum;
  }</P>
& a) f: n1 C& A! d, h! e<> for(i=1;i&lt;=num_b;i++)
% H1 M' Z6 `% h3 {+ Y  if(c_penum&gt;=lar1.value) {
   lar2=lar1;
   lar1.rc='c';
9 o4 }/ a; M5 ?5 B* K1 v% J& P# C   lar1.num=i;
- s" F& q6 @8 q9 F$ x   lar1.value=c_penum;
/ a# E2 J) s" ?, O  }
5 q- d: C* J* Q" M9 ?9 U9 j  else if(c_penum&gt;=lar2.value) {
. \4 q) V9 ]% ~- O  U   lar2.rc='c';
   lar2.num=i;
8 U$ i5 W9 t9 u: ?   lar2.value=c_penum;
  }</P>
( N. M( h* K' H<> if(lar1.value==lar2.value&amp;&amp;(lar1.num!=lar2.num||lar1.rc!=lar2.rc)) {
9 ^) g4 F3 ^* c; \$ z  if(lar1.rc=='r'&amp;&amp;lar2.rc=='r') {
   temp=temp_ab[lar1.num][1];
. w/ G* D1 m$ e1 G6 D8 O4 e6 d) z% }   r=lar1.num;
      c=1;
, M0 H# s) O6 x& `   for(i=1;i&lt;=num_b;i++) {
    if(temp_ab[lar1.num]&lt;temp) {
$ }) s% L+ q/ f& I7 y7 N5 S     temp=temp_ab[lar1.num];
* y* w, L" |6 t* V- m) {4 s     r=lar1.num;
9 F( R# d$ l+ D! n     c=i;
    }
6 U" [: B& ~& w! Z6 d    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
     r=lar2.num;
     c=i;
( \) ^: }' N( b% C& S/ n    }
  y+ Z8 Z7 `% i8 Q. |7 x7 l' m, f   }
6 e0 }( t( h  D4 C  }
" F) T3 \0 s% D; c$ i  if(lar1.rc=='c'&amp;&amp;lar2.rc=='c') {
# B" ?' y$ p. Y4 b* h4 }2 q   temp=temp_ab[1][lar1.num];
   r=1;
9 z/ E- W' B4 a% z; N      c=lar1.num;
; e$ `: e: ^! N7 T* E   for(i=1;i&lt;=num_a-1;i++) {
    if(temp_ab[lar1.num]&lt;temp) {
' T7 N% H( b# N2 o. B+ k6 ?     temp=temp_ab[lar1.num];
# Q' N' H& t. p+ f$ g& l     c=lar1.num;
. W  c1 X, w- a( H     r=i;
    }
% F6 M8 C. \$ Y! p    if(temp_ab[lar2.num]&lt;temp) {
- T  j( L; z) v& a+ F. X- @; Z- m     temp=temp_ab[lar2.num];
     c=lar2.num;
; ~$ V+ W5 |5 I+ _: {" d) z. ]4 x& Z     r=i;
    }
2 T: E" r+ k, h4 Y3 R' l, Q1 \- K8 \   }
# q. R4 J  l& \7 c) M  }
  e4 i7 f. K/ a4 T5 b/ `5 e* {! v- O1 W  if(lar1.rc=='r'&amp;&amp;lar2.rc=='c') {
( j0 H; R+ B, T% I9 j0 z   temp=temp_ab[lar1.num][1];
( k" |5 Z: ]( d% W& Q; h   r=lar1.num;
1 I& V+ ^- I! C" I) k      c=1;
   for(i=1;i&lt;=num_b;i++)
    if(temp_ab[lar1.num]&lt;temp) {
8 a! u5 d7 L1 c& c/ L0 I     temp=temp_ab[lar1.num];
     r=lar1.num;
     c=i;
    }
   for(i=1;i&lt;=num_a;i++)
    if(temp_ab[lar2.num]&lt;temp) {
2 E7 _. L; Q, d) [) \) `* g     temp=temp_ab[lar2.num];
     c=lar2.num;
& l; I) j2 @+ f" A* _2 t     r=i;
  H# r2 T! L7 ]    }
  s! `% X# t* D/ R5 v% w1 ^  }
  if(lar1.rc=='c'&amp;&amp;lar2.rc=='r') {
   temp=temp_ab[1][lar1.num];
   r=1;
      c=lar1.num;
; K" |( X. I; k0 h   for(i=1;i&lt;=num_b;i++)
    if(temp_ab[lar2.num]&lt;temp) {
3 k. r" |1 v0 K4 S     temp=temp_ab[lar2.num];
     r=lar2.num;
     c=i;
    }
4 N9 I/ m' \# P( x3 P) J6 w   for(i=1;i&lt;=num_a;i++)
    if(temp_ab[lar1.num]&lt;temp) {
     temp=temp_ab[lar1.num];
3 W5 O" H& E' X+ R" e2 \) d2 K( z     c=lar1.num;
+ w% G! A$ `1 N# a) ]0 A     r=i;
    }
* f/ G( Q1 l+ T+ }+ n$ E  }
3 i: ~) z0 }& ~8 W, g }
else {
  if(lar1.rc=='r') {
. H  P7 a* }, ~$ l. W. h   r=lar1.num;
, @" Z+ l( j4 V$ s# k1 r( v   c=1;
5 ?' r' I1 A  N   temp=temp_ab[lar1.num][1];
   for(i=1;i&lt;=num_b;i++)
1 r3 y9 F3 q) P; q- J8 U    if(temp_ab[lar1.num]&lt;temp) {
     c=i;
- j  b* {4 ?, Y" Z$ W5 C5 X- G$ ~  V     temp=temp_ab[lar1.num];
    }
  }
  else {
: O- q) M7 y* T) f) h   r=1;
3 J* y- o2 E0 U, D! f, \" m   c=lar1.num;
7 I7 I$ b/ f4 L; T4 M% \8 H   temp=temp_ab[1][lar1.num];
  @9 R6 V! f1 C7 B( {. V  `7 P   for(i=1;i&lt;=num_a;i++)
% Y$ I+ W2 B( K1 |( O0 Z% g0 ~  Z    if(temp_ab[lar1.num]&lt;temp) {
: w9 U) R0 N6 e, J" q6 P+ _" z     r=i;
* u* `$ z! p; _) ]3 y     temp=temp_ab[lar1.num];
  V2 k& \0 m% T) g8 ~, c: R    }
! B/ c- u" q/ U- N  }
5 {0 I; p! ?# d3 b+ M2 {: q" Q }
% c& A- A2 \8 F- _9 h6 ~ 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;
) i& `+ _7 v, L. r/ M" @* l# Q0 R  for(i=1;i&lt;=num_a;i++) temp_ab[c]=M;
}
$ D7 W& R# B1 h$ T9 c else if(temp_a[r]&lt;temp_b[c]) {
+ t! k1 D) G4 |8 l* u+ X$ G  base[r][c]=temp_a[r];
' T+ L& R* E( q% L  temp_b[c]=temp_b[c]-temp_a[r];
  temp_a[r]=0;
* w% B$ a% E8 w- \$ ~7 @  _% _  for(i=1;i&lt;=num_b;i++) temp_ab[r]=M;
# ^# @% {6 Y5 S }
. Y6 X. B, Y/ B2 F& ~# y else if(temp_a[r]==temp_b[c]) {
5 G/ V0 k7 ^0 E  base[r][c]=temp_a[r];
  temp_a[r]=temp_b[c]=0;
/ D1 h. _% ^. q0 i0 {; ?; x! K  for(i=1;i&lt;=num_a;i++) temp_ab[c]=M;
  for(i=1;i&lt;=num_b;i++) temp_ab[r]=M;
3 r/ E; l5 M" u, i  ?# l  k=0;
6 `( B- f: A0 m  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;
5 _" ]# E4 Z2 @9 r2 j  if(k!=0) {
   k=0;
  C  |" M4 }% j+ k9 V3 S2 e   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;
$ D% E1 a- y# E! ]* V9 d   else if(k==2) pbase[r][j]=1;
  }
( m& W- m, |. {, ^  [% W }
! a9 D/ u  t" Z k=0;
# f- r; i! V8 s7 W for(i=1;i&lt;=num_a;i++) if(temp_a!=0) k=1;
. @" J9 L/ i5 j/ U* J for(i=1;i&lt;=num_b;i++) if(temp_b!=0) k=1;
. h( H4 F% m$ h2 ` if(k==0) return;
$ |5 ~/ d; r  j: w- Y. E2 Y' v findinit();
}</P>
<>void computeuv() {
; p* y' _' \" y/ q2 i; b int i,j,k;
1 l, n" n+ e' ]. o for(i=1;i&lt;=num_a;i++)
  for(j=1;j&lt;=num_b;j++)
1 t9 z* x: x* b1 p# F) b0 z9 K   if(pbase[j]==1) {
/ F: H1 U( @+ x" r- [" w0 ~% ?& m* m    if(pu==1) {v[j]=ab[j]-u; pv[j]=1;}
* n. f6 B( N2 c; j+ i    if(pv[j]==1) {u=ab[j]-v[j]; pu=1;}
5 b1 y# a& z( B9 Y7 b) l   }
# j$ P2 ~  ]$ T+ [* x k=0;
5 R' M4 `& W% M1 Q* Y" b for(i=1;i&lt;=num_a;i++) if(pu==0) k=1;
: Z: q  l, M% m6 ~7 ~' w for(i=1;i&lt;=num_b;i++) if(pv==0) k=1;
if(k==1) computeuv();
}</P>
<>int check() {
int i,j,k,l;
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];
6 O2 t" P9 g' w$ J    if(base[j]&lt;0) k=1;
    else if(base[j]==0) l=1;
+ l: }5 ?& B3 G   }
/* for(i=1;i&lt;=num_a;i++){
5 o* ~( ~1 h: U0 S  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. m8 _& p! s  for(j=1;j&lt;=num_b;j++) printf("pbase %d\t",pbase[j]);
9 M# J9 ~/ X1 q+ q  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>
9 @& K; M  i! G2 i8 _<>int circle(enum direction dir,struct element cir[],int *t) {
: e" W: n% \: Q6 e8 Z+ t8 L+ b int i,j,k;
6 |+ R  K& N6 G" }2 N* L/ \ /*
putchar('\n');
for(i=1;i&lt;=*t;i++) printf("%d: r%d c%d\t",i, cir.r,cir.c);
putchar('\n');
*/
if((*t)!=1&amp;&amp;cir[(*t)].r==cir[1].r&amp;&amp;cir[*t].c==cir[1].c) {
  t--;
" ~, J& I; J+ R* ^/ ^% I' B  return 1;
}
if(dir!=down) {
& y, e5 m. u# R; W# r9 @; g+ l8 r  k=0;
3 `: ?" U5 V. c  for(i=cir[*t].r-1;i&gt;=1;i--)
. ?) i/ ~5 K/ }/ k* P   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;
  e9 e2 a/ [  H) w# T  if(k==1) {
   if(dir==up) cir[*t].value=0;
) o, T: n# T4 c3 a   else cir[*t].value=1;
/ W( U' F8 e0 B! K0 Z/ P   (*t)++;
   cir[*t].r=i;
! d! I0 f2 J# d7 [1 N  p) |7 Y   cir[*t].c=cir[(*t)-1].c;
! p4 N' g7 n. t4 x7 G" |: x- p   if(circle(up,cir,t)) return 1;
  }
}
if(dir!=up) {
8 X! ?- f% q( h& Q5 T/ b  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;
7 q. p! c8 l: t! M& M- k1 U6 u   else cir[*t].value=1;
   (*t)++;
   cir[*t].r=i;
   cir[*t].c=cir[(*t)-1].c;
3 G6 R4 F- ~# N8 [( E, A   if(circle(down,cir,t)) return 1;
1 B* _  E" i8 v2 ~1 b$ A  }
}
if(dir!=right) {
  k=0;
  for(i=cir[*t].c-1;i&gt;=1;i--)
' C/ P: @  S; Q) ^   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;
9 K. n( f$ w" U* O; X' y+ t! V  if(k==1) {
! l- t9 H, {. `- k2 c. v5 a   if(dir==left) cir[*t].value=0;
   else cir[*t].value=1;
0 C& l& A8 M. y  m: `9 F( h5 S   (*t)++;
   cir[*t].r=cir[(*t)-1].r;
   cir[*t].c=i;
   if(circle(left,cir,t)) return 1;
  }
1 B( ]6 R, l/ I; ~9 }4 }8 a }
+ d3 h- @% J: _- d( H! K if(dir!=left) {
8 h! n  L) t1 ^  k=0;
  for(i=cir[*t].c+1;i&lt;=num_b;i++)
$ y- o& w& U* j- l5 I   if(pbase[cir[*t].r]==1||(cir[*t].r==cir[1].r&amp;&amp;i==cir[1].c)) {k=1; break;}
6 V3 k# `1 `* O2 k+ ~. x: U5 M( l  for(j=2;j&lt;=*t;j++) if(cir[*t].r==cir[j].r&amp;&amp;i==cir[j].c) k=0;
+ x$ ?+ F3 j' v1 g0 C' _  if(k==1) {
3 g, U( A0 k; ]# t- _: v   if(dir==right) cir[*t].value=0;
   else cir[*t].value=1;
2 V  D2 N- b7 N: u3 G   (*t)++;
   cir[*t].r=cir[(*t)-1].r;
   cir[*t].c=i;
   if(circle(right,cir,t)) return 1;
0 M& Z. k" z) q, ]  }
9 H! A  H, J: }2 j1 Y' F# t }
  h' G' i! [$ {3 y (*t)--;
( S  q: K; D& W8 J1 v* g2 i8 d, [ return 0;
}</P>
<>void improve() {
9 ~) x7 K/ Y. _  g' v( ~ int i,j,k,t;
) u$ y/ k6 E$ i) G: \4 l struct element base_in,base_out,cir[2*MAX+1];</P>
<> for(i=1;i&lt;=num_a;i++) pu=0;
# [4 N9 \+ o% x7 j9 ~+ ] for(i=1;i&lt;=num_b;i++) pv=0;
u[1]=0; pu[1]=1;
computeuv();
6 \; H" o7 T  d6 o: L& b if(check()) return;
for(i=1;i&lt;=num_a;i++)
% Z8 }+ n! p$ _2 ^7 k/ m" I  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==0) break;
base_in.r=i;
6 W+ R+ p) f" ?1 Z9 x base_in.c=j;
' O3 Z! y# c7 E9 L base_in.value=base[j];</P>
<> for(i=1;i&lt;=num_a;i++)
  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==0&amp;&amp;base[j]&lt;base_in.value) {
9 m4 J7 n, x2 q3 M: V    base_in.r=i;
    base_in.c=j;
    base_in.value=base[j];
   }</P>
<> t=1;
cir[t].r=base_in.r;
' c( }' X9 z" }( `; e cir[t].c=base_in.c;
& d/ W  H; [; s: M# \8 Y* V& k. j cir[t].value=1;
* _3 p* T5 \: ~, q/ a* x if(!circle(mid,cir,&amp;t)) {
  printf("程序出错！按回车结束");
3 D, M- b; s2 P& z, d2 O  getchar();
  exit(0);
}
0 d( L4 D, Z  a, p9 u2 e7 \. ^ t--;
8 W2 B9 M! u( l% i1 B// 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;
6 S' o4 H5 [8 Z, p) _$ z7 ^6 Y3 r base_out=cir;
/ `' S  s- T8 m( x3 ? base_out.value=base[cir.r][cir.c];
k=1;
/ m+ B$ z5 z1 m  V3 i2 E for(i=1;i&lt;=t;i++)
7 m6 D9 }, s& }6 L) Q1 S1 p  if(k%2==0&amp;&amp;cir.value==1&amp;&amp;base[cir.r][cir.c]&lt;base_out.value) {
9 x0 \& a7 }: N; x  \4 o# ?   base_out=cir;
   base_out.value=base[cir.r][cir.c];
- ?1 F/ _  k+ {& W0 r# ~   k++;
/ r3 {, F' f6 q' ]- _3 P1 `  }
  else if(cir.value==1) k++;
& a: o- X0 f  F: s base[cir[1].r][cir[1].c]=0;
: m. t4 X$ j; s5 v: |+ q0 E k=1;
for(i=1;i&lt;=t;i++) {
6 \, G8 Q+ s, g% |1 _0 R0 c  if(k%2==1&amp;&amp;cir.value==1) {
1 E; h1 u# D0 c8 V5 P7 F   base[cir.r][cir.c]+=base_out.value;
   k++;
  |0 b* q, l; y/ z  }
* q9 C/ H0 i& Y. o% s5 z! d  else if(k%2==0&amp;&amp;cir.value==1) {
   base[cir.r][cir.c]-=base_out.value;
2 Y( z% w: P  O+ f   k++;
. n5 t; m; H! {8 P2 w0 G  }
0 w, e2 E! F: X" U }
; z" q& q6 _8 j$ o/ z pbase[base_out.r][base_out.c]=0;
* `4 p) A8 J( O; b( a pbase[base_in.r][base_in.c]=1;</P>
. ?' Z4 }" Y* M/ U* O% T# |<> improve();
" L+ Y3 k, ~7 V0 o3 R& d7 I}</P>
<>void output() {
int i,j;
! d( J1 P# H  y; z  f# X double sum=0;
' I$ Q  l1 n& @* s printf("\n运量为：\n");
for(i=1;i&lt;=num_a;i++) {
  putchar(' ');
  for(j=1;j&lt;=num_b;j++)
7 W* [( F5 Y: f3 Q) n   if(pbase[j]==1) {
4 ^6 s. ^( S& f' q3 u* A    printf("A%d-&gt;B%d:%lg\t",i,j,base[j]);
2 P' S: B" j$ {1 }$ m+ |    sum+=base[j]*ab[j];
   }
   else printf("A%d-&gt;B%d:0\t",i,j);
" B, P* ?  F( y  b2 k/ p# S0 c  putchar('\n');
( Y! @: H  i+ q' e) G }
printf("\n最低总运费为：%lg\n",sum);
}
4 n- U$ F* ]/ g! @+ J2 P3 O</P>

zhongguohelin

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

enrique08

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

hzlhm

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

liunengwu

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