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

plgatc

<>/*************************************************************************
                         表上作业法解运输问题        
3 W6 n1 w; B5 o! }! o
# u" `8 o+ ?3 K9 [ 编程环境：VC++6.0     
程序说明：
Vogel法求初始解，位势法检验是否最优，递归搜索闭回路改进解。
*************************************************************************/
( F: E2 J7 `- n- v( V#include &lt;stdio.h&gt;
: X) s# W9 c$ Q! |4 v5 J' g#include &lt;stdlib.h&gt;</P>
- ^! S3 y5 I7 N9 Z" P+ X<>#define MAX 100
#define M 999999</P>
& [: |) ?) j5 O' U4 o<>int status; //1唯一最优解，-1无穷多最优解</P>
/ ~- _/ h/ n# I" M9 L4 m0 I  Y<>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];
double base[MAX][MAX];
int pbase[MAX][MAX];
struct element {
) x+ M: {' A: X, ~2 ~) ] int r;
6 |% Q& A/ C/ K, ^ int c;
3 t) l7 Q" J/ |' o; x+ F. ^ double value;
};
enum direction {mid,up,down,left,right};</P>
/ x8 T( V6 C  e; v0 O) c<>void create();
void banner();
double dabs(double d);
7 ]6 l( ?; p, F' j0 M; fvoid findinit();
void computeuv();
- G9 ?. S# Z3 a3 \# M+ H  nint check();
int  circle(enum direction dir,struct element cir[],int *t);
# D/ O4 w3 b: }* @void improve();
& O7 J) S7 f# U' o& e$ W' hvoid output();</P>
<>void main() {
, X. |. f6 ?4 S7 u2 L& L/ x banner();
' y6 S. w% N! A+ A4 [. j create();
0 K$ B% Y5 ?- P3 N, W6 h8 ?2 |- G printf("\n按回车确认后开始求解");
0 i- j  Z4 R3 g, l getchar();
getchar();
/ a& N+ u( k4 m5 C3 |6 ] findinit();
3 n; g# z4 k- Q: _% h. k improve();
2 H" y! X; w0 a$ z switch(status) {
case 1:
% q+ z; ?# A3 ]7 s/ H5 ?: ]# Q  output();
) i* f) C  N* \$ R. C  puts("\n原问题有唯一最优解。\n");
/ b$ V: k8 X: `: I! Z  puts("\n按回车结束");
  getchar();
  exit(0);
case -1:
. h; v! ~, M: M- w8 u  output();
* `  B' ?8 _1 r  puts("\n原问题有无穷多最优解。\n");
  puts("\n按回车结束");
2 z5 I3 n4 G: F' B) C  getchar();
  exit(0);
}
}</P>
<>void banner() {
printf("\t\t****************************************\n");
9 [0 V5 q8 {4 `5 F7 z- F5 E  y printf("\t\t         表上作业法解运输问题\n");
8 a- h5 F' }. A% a+ G! y1 F) W" D printf("\t\t                              Thunder\n");
printf("\t\t****************************************\n");
8 k" E* ~7 ?! G% E4 x  S printf("\n");
3 D$ W- G- _8 l% _}</P>
<>void create() {
  t* |% a4 T* q  g' w int i,j;
double sum_a,sum_b;
- _2 p( s7 b* O# U: H char confirm;
while(1) {
1 A. P: x( W. `2 d/ W  printf("请输入产地个数：");
  scanf("%d",&amp;num_a);
  for(i=1;i&lt;=num_a;i++) {
. m3 d+ w) K1 I8 Z) r  }- J   printf("A%d产量：",i);
   scanf("%lf",&amp;a);
  }
' w& e& m9 E6 @! ~; m  for(i=1;i&lt;=num_a;i++) printf("A%d产量：%lg\t",i,a);
  printf("\n正确吗？：(y/n)");
+ i' j- H- ^& ~5 y1 D% P! l  ]+ O  getchar();
; Q% n' `5 z5 v3 A2 i0 G  confirm=getchar();
  if (confirm=='y') break;
  else if(confirm=='n') continue;
* u4 V! g* n' Z" \: v }
while(1) {
7 u* |) U- U. h! K% t9 T0 z  printf("\n请输入销地个数：");
  scanf("%d",&amp;num_b);
  for(i=1;i&lt;=num_b;i++) {
3 X1 R' n- E9 H) q   printf("B%d销量：",i);
1 ]/ P  l) Y. _" J! Z   scanf("%lf",&amp;b);
  }
( D: Z2 U1 r! A& u7 \  for(i=1;i&lt;=num_b;i++) printf("B%d销量：%lg\t",i,b);
7 e! [4 R1 f& ^5 s4 l  printf("\n正确吗？：(y/n)");
  getchar();
  confirm=getchar();
. {, E9 T3 ^( H2 Q  if (confirm=='y') break;
7 [% R& c; B* y/ q( R  else if(confirm=='n') continue;
0 \3 T& h7 h  V }
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]);
  }
) h7 O5 E. ~7 R7 F/ z' X( Z  for(j=1;j&lt;=num_b;j++) printf("A%d到B%d：%lg\t",i,j,ab[j]);
( y( B5 U# `. g+ Y  printf("\n正确吗？：(y/n)");
  getchar();
  confirm=getchar();
% g" L3 W, u6 S2 W  if(confirm=='n') i--;
$ \, @, M' `* p8 m3 x9 o. n3 e  putchar('\n');
}
//处理产销不平衡的情况
sum_a=sum_b=0;
for(i=1;i&lt;=num_a;i++) sum_a+=a;
for(i=1;i&lt;=num_b;i++) sum_b+=b;</P>
- i: l+ Z, R! h0 r<> printf("总产量：%lg\t总销量：%lg",sum_a,sum_b);
if(sum_a==sum_b) printf("\t产销平衡。");
else if(sum_a&gt;sum_b) {
  printf("\t供大于求，增加假想销地B%d。\n",++num_b);
& H% R8 A7 I, H2 g! }  b[num_b]=sum_a-sum_b;
. Q) n# _/ B5 R. c, q  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);
  a[num_a]=sum_b-sum_a;
+ i# j# o" ?. \' Y, r6 h6 _' l  for(i=1;i&lt;=num_b;i++) ab[num_a]=0;
: b- h8 z8 \& e% ]7 ? }
0 e5 Q2 R# `$ s: R //求解前的准备
  p8 `" x# c2 L) c 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;
for(i=1;i&lt;=num_b;i++) temp_b=b;
for(i=1;i&lt;=num_a;i++)
+ ], L+ n6 v3 x! F9 L for(j=1;j&lt;=num_b;j++) temp_ab[j]=ab[j];
" j7 ^. w# P; o* ^2 O //回显问题
3 j9 P5 v1 B' }$ W1 ?3 _* i printf("\n\n原问题为：\n\n");
   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);
printf("\n运价为：\n");
! l. ~9 {+ Q% v for(i=1;i&lt;=num_a;i++) {
" ]- t: \0 O! C, M1 Q  putchar(' ');
$ Q7 g* k7 f; e: `  for(j=1;j&lt;=num_b;j++)
  }- r+ v2 s9 P& r   printf("A%d-&gt;B%d:%lg\t",i,j,ab[j]);
" k' r; d0 _9 w  putchar('\n');
# r( N0 l* d) u' A& G# K. w9 y7 P+ Z5 z }
}</P>
<>double dabs(double d) {
% b  A4 D% X8 }" E& S6 L/ n if(d&gt;=0) return d;
$ Q$ T9 Z) F0 {+ d( w else return -d;
}</P>
+ _9 M7 ?9 O. h% n4 e5 Z! |; U<>void findinit() {
int i,j,k;
double r_penum[MAX],c_penum[MAX];
struct largest {
  _, V7 f1 P% K  char rc;
- Y3 h1 D+ c( e8 G0 ]  int num;
  double value;
};
struct largest lar1,lar2;
int r=0,c=0;
8 W0 E! r+ N$ O6 L, ? double a1,a2,b1,b2,temp;</P>
  o% v4 S) e5 Q( x5 ~<> for(i=1;i&lt;=num_a;i++) {
  temp=temp_ab[1];
  for(j=1;j&lt;=num_b;j++)
% a/ G  |! _- _" P, b   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
  a1=a2=temp;
  for(j=1;j&lt;=num_b;j++)
$ o6 ?0 F" `. v) W; M( @  `   if(temp_ab[j]&lt;=a1) {
5 Q, p& U9 U2 M& \( T; z    a2=a1;
    a1=temp_ab[j];
8 I$ A  T! e+ x9 g   }
) {! G+ u1 ^0 m# ~9 E5 F   else if(temp_ab[j]&lt;=a2) a2=temp_ab[j];
3 R# [# A! u% d' n( m  r_penum=dabs(a1-a2);
}</P>
<> for(i=1;i&lt;=num_b;i++) {
8 O8 H: l! @) m  temp=temp_ab[1];
  for(j=1;j&lt;=num_a;j++)
: A( S* k0 U) K; C& r" \   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
7 i: F3 ~. H- h' s6 m  b1=b2=temp;
* k3 s0 P+ G1 C3 I! g& d  for(j=1;j&lt;=num_a;j++)  
   if(temp_ab[j]&lt;=b1) {
" o, B2 F* d) ]3 n: H. G    b2=b1;
+ T0 v0 u& U0 o8 y2 H    b1=temp_ab[j];
6 K1 D3 q% u4 W/ u0 H& e6 W   }
8 x0 _% y2 ?: |% Z2 _   else if(temp_ab[j]&lt;=b2) b2=temp_ab[j];
  c_penum=dabs(b1-b2);
}
/*
for(i=1;i&lt;=num_a;i++) printf("pa%d=%lg ",i,r_penum);
- }/ H0 |: t7 G  S. o5 X) Y/ e, l putchar('\n');
- Q# v, @) }$ |6 N" q! R* T 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;
6 K& Y# X( n7 G$ |! r for(i=1;i&lt;=num_b;i++) if(c_penum&lt;temp) temp=c_penum;</P>
<> //考虑了有两个罚数相等的情况，大于两个相等只取其中两个进行比较
lar1.value=lar2.value=temp;
lar1.num=lar2.num=1;
' W2 m; T+ n# z4 x lar1.rc=lar2.rc='r';
for(i=1;i&lt;=num_a;i++)
  if(r_penum&gt;=lar1.value) {
8 |: B" @' `, k- h0 J   lar2=lar1;
   lar1.rc='r';
   lar1.num=i;
   lar1.value=r_penum;
" b0 H! w5 A( e2 H3 ?1 e  }
0 i6 n8 x# y! E" B6 U/ j  {/ |, z6 q  else if(r_penum&gt;=lar2.value) {
   lar2.rc='r';
   lar2.num=i;
   lar2.value=r_penum;
  }</P>
6 ?4 I% K; l) q0 W" a% T& G/ C, c- u7 a<> for(i=1;i&lt;=num_b;i++)
1 K: @% |5 X2 Q1 @  if(c_penum&gt;=lar1.value) {
; e- Y$ v2 V' x) |7 i' L4 I! S' U   lar2=lar1;
   lar1.rc='c';
   lar1.num=i;
% }, G/ z* X" c0 u/ k5 j9 _% T   lar1.value=c_penum;
  }
  else if(c_penum&gt;=lar2.value) {
3 e" Y" t# ^) T' ]6 w5 ~9 s   lar2.rc='c';
   lar2.num=i;
8 T7 H2 F: H6 D6 k8 Y   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') {
" W# Q: I. `$ G' H* b  q   temp=temp_ab[lar1.num][1];
   r=lar1.num;
      c=1;
   for(i=1;i&lt;=num_b;i++) {
    if(temp_ab[lar1.num]&lt;temp) {
     temp=temp_ab[lar1.num];
     r=lar1.num;
% _7 |" I  L1 N9 E) L" o& Z+ D     c=i;
6 Z& `' R1 P* _9 h# W+ L8 {7 ^    }
    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
     r=lar2.num;
     c=i;
    }
   }
  }
, j. _+ K, _8 s  if(lar1.rc=='c'&amp;&amp;lar2.rc=='c') {
   temp=temp_ab[1][lar1.num];
   r=1;
      c=lar1.num;
8 q( \0 t( I1 X/ I; Z0 B% X   for(i=1;i&lt;=num_a-1;i++) {
: B* M( F3 {$ @) F, a: R    if(temp_ab[lar1.num]&lt;temp) {
     temp=temp_ab[lar1.num];
     c=lar1.num;
+ z4 K$ J/ \; o& m7 p8 j9 _+ @     r=i;
/ V+ L8 k) L1 O1 h    }
/ n$ V6 B0 z  y    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
     c=lar2.num;
     r=i;
    }
. E* q7 ~2 E% F( I3 S3 t- x/ Z   }
  }
  if(lar1.rc=='r'&amp;&amp;lar2.rc=='c') {
+ Y' g+ d3 g7 C0 K   temp=temp_ab[lar1.num][1];
6 G+ j: Y% z. M2 c   r=lar1.num;
* K: K( i9 Q1 c" s8 C: @: m      c=1;
+ j) D( L- d1 p. g" Z* }   for(i=1;i&lt;=num_b;i++)
    if(temp_ab[lar1.num]&lt;temp) {
     temp=temp_ab[lar1.num];
     r=lar1.num;
     c=i;
    }
5 ]. q" B0 F6 ]; x   for(i=1;i&lt;=num_a;i++)
, ~# E; d+ L* x! b    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
     c=lar2.num;
     r=i;
/ {2 F% s6 {/ l/ g  j    }
/ I9 H1 o7 L' X& h* _  }
  if(lar1.rc=='c'&amp;&amp;lar2.rc=='r') {
# D4 ]5 y- t% ~$ Z9 R. \   temp=temp_ab[1][lar1.num];
9 \& s* F4 }3 I4 o/ D: P   r=1;
      c=lar1.num;
* p" k. L* m3 E   for(i=1;i&lt;=num_b;i++)
    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
- W; Y+ G6 Z9 p7 A: _2 M+ y7 ]     r=lar2.num;
     c=i;
    }
   for(i=1;i&lt;=num_a;i++)
) ~! v  k" i7 ?  ]! O  w, }  N' h) F    if(temp_ab[lar1.num]&lt;temp) {
! W& g) F: d  r     temp=temp_ab[lar1.num];
2 e: y" \9 [. M! c8 G     c=lar1.num;
     r=i;
    }
  }
& `: g7 K. F0 f8 e2 D0 w2 G7 q  a }
& N) L# o, W4 c else {
) o# U/ t: N$ I3 A  if(lar1.rc=='r') {
: f* q5 F+ |( ~   r=lar1.num;
   c=1;
   temp=temp_ab[lar1.num][1];
3 Q& D5 L1 ~2 w  X! p; g9 O   for(i=1;i&lt;=num_b;i++)
- g7 N2 |" X" Q    if(temp_ab[lar1.num]&lt;temp) {
     c=i;
2 P& A3 L, \9 {5 z# j) R) Z0 ?     temp=temp_ab[lar1.num];
$ K, b: v6 K, M4 r$ L    }
  }
  else {
4 Z+ K8 \- W# G   r=1;
   c=lar1.num;
   temp=temp_ab[1][lar1.num];
   for(i=1;i&lt;=num_a;i++)
    if(temp_ab[lar1.num]&lt;temp) {
     r=i;
     temp=temp_ab[lar1.num];
1 S3 ^3 x5 Z1 W  q9 [1 f    }
$ P  W6 Y8 C* q) @  }
}
pbase[r][c]=1;
  _2 B: _# b4 r! W( R3 Y 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;
/ A; K* g. U; P, |; w* ^* j }
0 z9 m) x; n( Y0 |# {* G else if(temp_a[r]&lt;temp_b[c]) {
$ f& F# _1 X+ m: Y- `  base[r][c]=temp_a[r];
  temp_b[c]=temp_b[c]-temp_a[r];
  q! S+ q; b2 M/ B& _  temp_a[r]=0;
6 C2 v$ ^1 D. V. v  L, i9 ~& Z1 a  for(i=1;i&lt;=num_b;i++) temp_ab[r]=M;
}
8 A; x5 U2 t3 \  r$ z else if(temp_a[r]==temp_b[c]) {
" g# _+ W* v  x  base[r][c]=temp_a[r];
- t- [& G& M+ ~: A9 _  temp_a[r]=temp_b[c]=0;
* T' i; z- y. ^  for(i=1;i&lt;=num_a;i++) temp_ab[c]=M;
5 ]  x1 O5 }( T- N/ n4 e  for(i=1;i&lt;=num_b;i++) temp_ab[r]=M;
  k=0;
& }/ s8 a& p( J8 z% T: F+ n' \% X  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;
   else if(k==2) pbase[r][j]=1;
  }
8 q% m8 O' w# a }
, s' v8 Q0 X: _  j" Y# y k=0;
3 h& A* ~' l" a( g1 Z 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) return;
5 B7 b% {1 |. p- p2 M+ E4 ` findinit();
( p% d  y9 S: D# D9 q; `' M}</P>
  s0 a% x) r% Z' C( B0 Y<>void computeuv() {
3 L4 z; I: I) @6 C* g/ ~ int i,j,k;
for(i=1;i&lt;=num_a;i++)
  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==1) {
    if(pu==1) {v[j]=ab[j]-u; pv[j]=1;}
    if(pv[j]==1) {u=ab[j]-v[j]; pu=1;}
8 X, v& n5 S/ O" [2 f6 a  e) r) b   }
k=0;
: L0 o( f. A9 T% x for(i=1;i&lt;=num_a;i++) if(pu==0) k=1;
* f# }& o0 w3 }4 P2 P+ M9 M$ |$ t for(i=1;i&lt;=num_b;i++) if(pv==0) k=1;
# v* n6 n$ a9 W& T if(k==1) computeuv();
}</P>
9 M. q% t8 i: r8 _<>int check() {
' G% l2 R# d5 a. I int i,j,k,l;
- n  B* a# C9 C/ ], o4 F k=l=0;
* z1 u9 d6 h( q, d for(i=1;i&lt;=num_a;i++)
  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==0) {
9 C  Q6 U" K. h4 }- Z    base[j]=ab[j]-u-v[j];
! D& {' |: U. {/ _; D3 J5 b    if(base[j]&lt;0) k=1;
! M( K+ x! \- Z" A/ Y$ j    else if(base[j]==0) l=1;
   }
) `  v. M: s! c7 s! a" P/* for(i=1;i&lt;=num_a;i++){
& J) b' n9 b7 G- p& M+ ?! G  for(j=1;j&lt;=num_b;j++) printf("base %lg\t",base[j]);
! l) z8 f4 g+ D  putchar('\n');}
) D" [- d9 O/ X  n) C0 O* P( g9 G for(i=1;i&lt;=num_a;i++){
  for(j=1;j&lt;=num_b;j++) printf("pbase %d\t",pbase[j]);
  putchar('\n');}
+ h# e1 p. ^4 o$ u" P5 A*/
# `2 Z0 d! Z" k& ~/ k if(k==0&amp;&amp;l==0) {status=1; return 1;}
else if(k==0&amp;&amp;l!=0) {status=-1; return 1;}
: {7 C& o) X: l4 Y- Y else return 0;
% M4 V0 q( y- }% D4 \, d: s}</P>
<>int circle(enum direction dir,struct element cir[],int *t) {
+ a+ {6 d0 r" z int i,j,k;
/*
" z( H6 ~2 ^1 ^# r8 I/ d8 H putchar('\n');
' s) t% O" p* W$ @1 j* s! ] for(i=1;i&lt;=*t;i++) printf("%d: r%d c%d\t",i, cir.r,cir.c);
/ M4 F) {: j) w+ Z6 Q& G9 { putchar('\n');
/ o4 j5 K5 A, t  W, a3 W8 r. ^ */
0 ]6 d( N& A! ` if((*t)!=1&amp;&amp;cir[(*t)].r==cir[1].r&amp;&amp;cir[*t].c==cir[1].c) {
  t--;
  return 1;
}
+ `  N  V9 r% t6 Q$ c+ P if(dir!=down) {
  k=0;
5 Q$ H, G! [5 N! j  for(i=cir[*t].r-1;i&gt;=1;i--)
  b, x% W7 @+ H/ _3 E   if(pbase[cir[*t].c]==1||(i==cir[1].r&amp;&amp;cir[*t].c==cir[1].c)) {k=1; break;}
, @9 i+ B- {+ K7 B9 \' R- i2 W  for(j=2;j&lt;=*t;j++) if(i==cir[j].r&amp;&amp;cir[*t].c==cir[j].c) k=0;
: `: d+ }6 r$ `5 D, }% u1 N  if(k==1) {
4 f# R9 t. t# b6 d; {, f) A1 V   if(dir==up) cir[*t].value=0;
   else cir[*t].value=1;
   (*t)++;
( ]" a) c( ^7 Y! V   cir[*t].r=i;
9 G- H5 s$ n5 @- Z/ o0 g2 k( A! S: F   cir[*t].c=cir[(*t)-1].c;
( n: y+ }* T0 M! m   if(circle(up,cir,t)) return 1;
" t, A9 G3 B! o- q7 O# d! N3 t7 ?/ u  }
}
% Z+ Z+ j* k* h* ?" {" j; z if(dir!=up) {
! q' _& y4 C$ J+ ]6 b  k=0;
- J6 S% R- S* f/ `  N! `  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;
7 X9 O$ o/ O6 Y, R7 o1 T2 [  if(k==1) {
   if(dir==down) cir[*t].value=0;
1 [# i" _. p  N/ h8 v  f   else cir[*t].value=1;
   (*t)++;
0 z* e6 \6 Z! o5 _% _   cir[*t].r=i;
$ \# k3 ?6 {/ h! s   cir[*t].c=cir[(*t)-1].c;
   if(circle(down,cir,t)) return 1;
, X. T3 L1 z- H. b( R' ~. w" d8 u  }
}
  B5 @2 S) x4 i5 g8 @  k if(dir!=right) {
; h8 `: l4 z: k9 s5 q; e  k=0;
, p+ z. c5 t1 w* {  for(i=cir[*t].c-1;i&gt;=1;i--)
$ \2 d) ]4 o4 P1 v. D. F   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;
+ p& A3 l! D) O  U% a) y  if(k==1) {
/ W. b3 z$ h! Y( e; ?% y% R   if(dir==left) cir[*t].value=0;
   else cir[*t].value=1;
  B- L6 L4 u6 C. x   (*t)++;
   cir[*t].r=cir[(*t)-1].r;
: C+ V: h% O3 }6 c% I/ D   cir[*t].c=i;
5 ^0 H; v. v* S% J; h1 u/ {  }% r   if(circle(left,cir,t)) return 1;
  }
}
6 {, e9 E- D* n' d9 c# \ if(dir!=left) {
  k=0;
. @2 k0 n. G5 \  for(i=cir[*t].c+1;i&lt;=num_b;i++)
7 O1 w( B) E3 g0 ?0 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;
  C( |2 g0 a' @! Q" H2 u) L   else cir[*t].value=1;
   (*t)++;
" [6 M) J: {$ ~. O   cir[*t].r=cir[(*t)-1].r;
9 {: N" r4 u% o& {2 X   cir[*t].c=i;
   if(circle(right,cir,t)) return 1;
  }
' m& @& e' Y2 k( U }
9 L! m/ T+ C" } (*t)--;
6 h: H/ I+ Y( H( L* Y" l return 0;
}</P>
! k. @/ T6 N" W9 \" ^6 @<>void improve() {
! o+ [$ k4 h, T: C int i,j,k,t;
( p9 w1 Z- ?" k1 a* h( | struct element base_in,base_out,cir[2*MAX+1];</P>
<> for(i=1;i&lt;=num_a;i++) pu=0;
3 c9 _2 h5 g5 A( o9 f: o for(i=1;i&lt;=num_b;i++) pv=0;
  \3 N: D7 J! ^ u[1]=0; pu[1]=1;
computeuv();
8 r1 v9 k, d0 u7 ] if(check()) return;
for(i=1;i&lt;=num_a;i++)
  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==0) break;
base_in.r=i;
base_in.c=j;
8 F+ j/ J2 ~; h9 E% C, n4 S: l- O2 d0 c. T base_in.value=base[j];</P>
( `- K7 H7 Y/ m0 _+ K5 T<> for(i=1;i&lt;=num_a;i++)
$ F/ f  E* R1 E' p3 X8 Y  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==0&amp;&amp;base[j]&lt;base_in.value) {
    base_in.r=i;
) p( c( \; S- ^/ M' i; S4 f    base_in.c=j;
    base_in.value=base[j];
   }</P>
- Q' ]: m  R" `) ]0 H6 \3 V/ P<> t=1;
' w3 D) ?. I& G6 W, @, f cir[t].r=base_in.r;
cir[t].c=base_in.c;
cir[t].value=1;
if(!circle(mid,cir,&amp;t)) {
9 y% i3 S+ _) d% y# N* j' ]  printf("程序出错！按回车结束");
  getchar();
  exit(0);
  d0 H9 P7 S; T1 Q, A5 _ }
; ~6 h. @$ S. I. r7 \ t--;
2 n3 [7 l0 X- {3 P+ A- F# h// 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];
k=1;
7 o; o$ P; a$ @! r for(i=1;i&lt;=t;i++)
" a- C* n; j. p" g) i& B2 b  if(k%2==0&amp;&amp;cir.value==1&amp;&amp;base[cir.r][cir.c]&lt;base_out.value) {
   base_out=cir;
9 L; x3 P, m0 S2 J+ q   base_out.value=base[cir.r][cir.c];
* u2 i5 {) \8 D' z" T   k++;
  }
  else if(cir.value==1) k++;
base[cir[1].r][cir[1].c]=0;
" ?  u" D/ m. r k=1;
for(i=1;i&lt;=t;i++) {
5 E6 _4 P! w4 f* B. N  `+ ~3 p& m& w  if(k%2==1&amp;&amp;cir.value==1) {
   base[cir.r][cir.c]+=base_out.value;
   k++;
. f3 _+ o+ G: x- F" Q* t1 `9 ~; t  }
  else if(k%2==0&amp;&amp;cir.value==1) {
   base[cir.r][cir.c]-=base_out.value;
$ d0 B! [0 R+ C. S0 G   k++;
7 V- `- p( e1 G/ M5 _  }
}
pbase[base_out.r][base_out.c]=0;
pbase[base_in.r][base_in.c]=1;</P>
- b' S, @; v0 K) p* [6 H7 I4 U<> improve();
; a9 @6 e7 f/ K, I}</P>
<>void output() {
; z5 ~5 O1 W* F0 _: G6 { int i,j;
! ?  w# b' M' n5 \; y2 p7 J8 _7 E$ z double sum=0;
& m( n+ _4 A4 F printf("\n运量为：\n");
for(i=1;i&lt;=num_a;i++) {
  putchar(' ');
  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==1) {
$ L0 @9 ~. [# S3 ]# Z8 M    printf("A%d-&gt;B%d:%lg\t",i,j,base[j]);
    sum+=base[j]*ab[j];
& t1 m9 ~3 T  V4 s- M   }
   else printf("A%d-&gt;B%d:0\t",i,j);
  putchar('\n');
" u9 U" ~( B. W }
3 k% Q: W: M5 c& [  g" ?1 q printf("\n最低总运费为：%lg\n",sum);
# v6 m8 F# L$ t4 V7 m. [}
</P>

zhongguohelin

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

enrique08

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

hzlhm

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

liunengwu

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