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

plgatc

<>/*************************************************************************
                         表上作业法解运输问题        
" v7 i5 {5 W: k4 d3 ?& L- f
3 g5 I' y& c2 j. w" v; g% _( c 编程环境：VC++6.0     
) `6 Q% i% C7 {( y& l  @ 程序说明：
Vogel法求初始解，位势法检验是否最优，递归搜索闭回路改进解。
*************************************************************************/
6 R4 m) \. v% N1 S#include &lt;stdio.h&gt;
! I% W: k6 t2 ]#include &lt;stdlib.h&gt;</P>
1 x$ D: {& y" {1 [# ~) z<>#define MAX 100
#define M 999999</P>
- |, h' G% n1 v$ W<>int status; //1唯一最优解，-1无穷多最优解</P>
<>int num_a,num_b;
double a[MAX],b[MAX],temp_a[MAX],temp_b[MAX];
4 ]; I- m$ s( P( z2 {% k7 Pdouble u[MAX],v[MAX],pu[MAX],pv[MAX];
double ab[MAX][MAX],temp_ab[MAX][MAX];
double base[MAX][MAX];
+ @; T9 N- K: c8 Eint pbase[MAX][MAX];
struct element {
int r;
: n' C5 W  U! D6 T) }* k int c;
double value;
' \3 c6 _5 Y# Q  `' ~, x' B};
enum direction {mid,up,down,left,right};</P>
0 n7 F  L% T* k  u. w  i% i/ p<>void create();
void banner();
# G& `7 b/ a  i2 s7 \double dabs(double d);
$ W& M# T) Z7 g: `' Qvoid findinit();
. ?) U6 J3 m2 i& R6 Gvoid computeuv();
: o9 [& v* n( Sint check();
int  circle(enum direction dir,struct element cir[],int *t);
void improve();
4 F# @9 K  f5 M  J6 ^void output();</P>
2 K9 P( ~9 o, R0 n- J* B7 v7 U. ~<>void main() {
banner();
create();
6 w! \0 f/ b9 b2 _. `5 F6 j. G# q. J printf("\n按回车确认后开始求解");
getchar();
getchar();
8 r$ r  U! @2 f4 K. G findinit();
7 i- ]) ^3 S5 _! L( ` improve();
6 l4 A- a8 J& }- N  i" ~8 T: M2 {% ] switch(status) {
% J, ?9 ]9 {5 @! W) |6 _  B# Z case 1:
8 C" P4 v' _0 }& v/ s  output();
* B, \, R5 b: k$ _  z6 j  puts("\n原问题有唯一最优解。\n");
  puts("\n按回车结束");
" ]- y# H2 }1 Y' ?( r, [, {  getchar();
% e' k* R& N1 _* s7 _1 Z3 H  exit(0);
" t8 U+ R0 D) a2 }* r: u7 q case -1:
  output();
+ d, B- O, H6 _5 O  puts("\n原问题有无穷多最优解。\n");
  puts("\n按回车结束");
+ N2 V" d* |) L  getchar();
  exit(0);
% L- c6 A. c8 D& J3 W! F  i/ n }
) Q# v( e8 U3 }0 k- E1 i1 d}</P>
4 S5 A* x& H0 M; Y<>void banner() {
printf("\t\t****************************************\n");
) v4 v; d( I6 e( \9 l  Z' Y6 y- G printf("\t\t         表上作业法解运输问题\n");
  {' D7 U: G, B8 L6 | printf("\t\t                              Thunder\n");
! @9 P& @! j& b% l- Q, @ printf("\t\t****************************************\n");
6 b: X; y. d$ H; |. k printf("\n");
9 j* p0 _, n7 C. k* i}</P>
<>void create() {
int i,j;
0 N, G0 }( @* i8 H& S double sum_a,sum_b;
char confirm;
while(1) {
  printf("请输入产地个数：");
  scanf("%d",&amp;num_a);
6 P0 n' n! U; |. T) V; K: E, w  x  for(i=1;i&lt;=num_a;i++) {
   printf("A%d产量：",i);
   scanf("%lf",&amp;a);
  }
  for(i=1;i&lt;=num_a;i++) printf("A%d产量：%lg\t",i,a);
  printf("\n正确吗？：(y/n)");
  s) F3 h" D6 W2 w" O  getchar();
) A) F" i6 [0 w  confirm=getchar();
  if (confirm=='y') break;
3 r/ t1 e# [5 f0 a/ e! U4 |  else if(confirm=='n') continue;
}
$ R* @. V& V6 x$ C# O/ q while(1) {
# Z7 h* b3 H( n% V; O. o  printf("\n请输入销地个数：");
" [+ m0 Q6 r) y2 U& _0 z  scanf("%d",&amp;num_b);
( P9 k4 ^0 b3 ^6 ^  for(i=1;i&lt;=num_b;i++) {
   printf("B%d销量：",i);
0 x4 H$ j. S/ _: Q! w7 E   scanf("%lf",&amp;b);
+ l$ @3 m6 n, C9 P  }
! b' {$ A; `9 {+ Q$ u- q7 K+ C  for(i=1;i&lt;=num_b;i++) printf("B%d销量：%lg\t",i,b);
; @) N: E4 n( L; ?& P( y' k: y  printf("\n正确吗？：(y/n)");
  getchar();
, A1 W' ^5 E. B  confirm=getchar();
  if (confirm=='y') break;
  else if(confirm=='n') continue;
* P6 m. O. x* u5 z }
# {3 o1 W  f; l1 U4 j% t7 _# Y( A putchar('\n');
for(i=1;i&lt;=num_a;i++) {
# b  E) @" V3 }# W2 \6 _3 S4 g* X  for(j=1;j&lt;=num_b;j++) {
% Z& m" f: ^  S. P   printf("A%d到B%d运价：",i,j);
   scanf("%lf",&amp;ab[j]);
+ L+ w% M& W: A* _  p; Z! D  }
* _0 i5 Y9 U% `! H+ @: l  for(j=1;j&lt;=num_b;j++) printf("A%d到B%d：%lg\t",i,j,ab[j]);
  printf("\n正确吗？：(y/n)");
  E, K0 r% L* C1 k2 |  getchar();
  confirm=getchar();
, i& C0 J  n8 m  if(confirm=='n') i--;
. m7 g+ H0 k. p  putchar('\n');
}
2 ?# N0 P: J! c) d //处理产销不平衡的情况
, a, y) N6 O+ h9 `4 \6 I4 ` sum_a=sum_b=0;
% ?# |" d/ N5 z for(i=1;i&lt;=num_a;i++) sum_a+=a;
for(i=1;i&lt;=num_b;i++) sum_b+=b;</P>
( ~* S- t; A9 O, w<> printf("总产量：%lg\t总销量：%lg",sum_a,sum_b);
if(sum_a==sum_b) printf("\t产销平衡。");
1 {  f  p4 S" h  J else if(sum_a&gt;sum_b) {
  printf("\t供大于求，增加假想销地B%d。\n",++num_b);
' @2 z& _, ]% a  b[num_b]=sum_a-sum_b;
  for(i=1;i&lt;=num_a;i++) ab[num_b]=0;
}
0 P; w5 d- ^* T5 `8 R# U else if(sum_a&lt;sum_b){
, c5 Y- v9 j9 v' ^& B5 a  printf("\t供不应求，增加假想产地A%d。\n",++num_a);
& {, A. @  }- r. e$ h% s  a[num_a]=sum_b-sum_a;
  for(i=1;i&lt;=num_b;i++) ab[num_a]=0;
, H1 d4 W8 }; r4 o# V/ x8 o }
$ N( }$ F! ~% g# I7 F% e //求解前的准备
% L& A  Q$ S: Z% B, k for(i=1;i&lt;=num_a;i++)
  for(j=1;j&lt;=num_b;j++)
   base[j]=pbase[j]=0;
9 M0 b8 w( _3 @4 ?/ @ for(i=1;i&lt;=num_a;i++) temp_a=a;
/ r. |  c2 m: h) _* ^8 v! U) I8 _ for(i=1;i&lt;=num_b;i++) temp_b=b;
$ I" R' k; o1 }0 P! q for(i=1;i&lt;=num_a;i++)
for(j=1;j&lt;=num_b;j++) temp_ab[j]=ab[j];
. k( P4 N% P( x- K+ f. b8 I" X //回显问题
printf("\n\n原问题为：\n\n");
( x- _5 N) w6 {$ y   printf("产量：\n ");
for(i=1;i&lt;=num_a;i++) printf("A%d:%lg\t",i,a);
# P1 D4 w1 F' z, C+ ~7 G- K printf("\n运量：\n ");
for(i=1;i&lt;=num_b;i++) printf("B%d:%lg\t",i,b);
/ R8 u4 I5 r5 p' s1 a* |) q printf("\n运价为：\n");
5 ?7 F% [* p- V8 C- }' g' A for(i=1;i&lt;=num_a;i++) {
( c3 F1 J1 x0 k8 I& x. T& `( ^  putchar(' ');
) a/ L' V; u3 t- _' q% A- W- k$ F  for(j=1;j&lt;=num_b;j++)
   printf("A%d-&gt;B%d:%lg\t",i,j,ab[j]);
  putchar('\n');
( k" M( K* _6 X& u3 Y }
3 y  I: V: ]+ e5 b& W: @}</P>
<>double dabs(double d) {
3 I- g3 U0 j8 g  l' S if(d&gt;=0) return d;
else return -d;
}</P>
<>void findinit() {
1 q; r6 G% _* u: `' \; ^$ V; S int i,j,k;
$ _, J% V5 w) k9 R( Q, _9 l# S% B double r_penum[MAX],c_penum[MAX];
struct largest {
  char rc;
  int num;
0 P0 T! f; s  ^; H) v7 c8 t  double value;
% u1 T0 [8 N6 n3 ` };
struct largest lar1,lar2;
int r=0,c=0;
2 M8 U  |/ E8 a- @- M double a1,a2,b1,b2,temp;</P>
<> for(i=1;i&lt;=num_a;i++) {
  temp=temp_ab[1];
$ s& z5 {9 E  C2 c; S+ U  for(j=1;j&lt;=num_b;j++)
% n6 G# h+ O9 ?6 r   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
  a1=a2=temp;
  for(j=1;j&lt;=num_b;j++)
/ l; `6 f, S  @7 I+ w' ~   if(temp_ab[j]&lt;=a1) {
    a2=a1;
    a1=temp_ab[j];
   }
   else if(temp_ab[j]&lt;=a2) a2=temp_ab[j];
  r_penum=dabs(a1-a2);
}</P>
& T2 w5 _- K" E2 f<> for(i=1;i&lt;=num_b;i++) {
7 j& G1 I' c7 C  temp=temp_ab[1];
  for(j=1;j&lt;=num_a;j++)
% O. K$ y7 M% J! ?9 I; r   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
  b1=b2=temp;
  for(j=1;j&lt;=num_a;j++)  
* [: ~8 K' u( F6 B( G   if(temp_ab[j]&lt;=b1) {
    b2=b1;
    b1=temp_ab[j];
   }
   else if(temp_ab[j]&lt;=b2) b2=temp_ab[j];
  c_penum=dabs(b1-b2);
6 _6 L& A" }" y! ?  l5 b }
/*
for(i=1;i&lt;=num_a;i++) printf("pa%d=%lg ",i,r_penum);
putchar('\n');
" D; k1 E# u& l5 g for(i=1;i&lt;=num_b;i++) printf("pb%d=%lg ",i,c_penum);
*/
temp=r_penum[1];
6 }0 X, N, C) d( V' s+ `$ ?3 u for(i=1;i&lt;=num_a;i++) if(r_penum&lt;temp) temp=r_penum;
2 X  o& I9 \& x9 B for(i=1;i&lt;=num_b;i++) if(c_penum&lt;temp) temp=c_penum;</P>
4 k9 Q% s1 L( N7 F<> //考虑了有两个罚数相等的情况，大于两个相等只取其中两个进行比较
lar1.value=lar2.value=temp;
lar1.num=lar2.num=1;
! u$ |7 ^7 q! v- ? lar1.rc=lar2.rc='r';
6 A- j8 U: L  r) [* d for(i=1;i&lt;=num_a;i++)
% o1 [4 d% }# I; p3 t  if(r_penum&gt;=lar1.value) {
. Z) }: e; ^' G  {   lar2=lar1;
   lar1.rc='r';
$ R" f% t4 V( C; D& D& X; }# e; W! b   lar1.num=i;
7 E& d+ M) Z, N% S' \" H, `   lar1.value=r_penum;
  }
; T2 l, n) b( r( t# K  else if(r_penum&gt;=lar2.value) {
   lar2.rc='r';
   lar2.num=i;
   lar2.value=r_penum;
  }</P>
' r+ ^; f# p2 w5 F$ i" s# f, ~<> for(i=1;i&lt;=num_b;i++)
4 |/ m8 ^& I: ]+ Q, ^  if(c_penum&gt;=lar1.value) {
   lar2=lar1;
; e( ]. p+ H* O8 N# s2 u   lar1.rc='c';
/ @( E9 q2 ^$ B+ G) V! Y* E3 x& g   lar1.num=i;
  P. Y4 C  J7 ?! g3 _   lar1.value=c_penum;
# q6 {0 x4 j  f# h  }
" Z% o% f- ?+ e$ T0 d  else if(c_penum&gt;=lar2.value) {
   lar2.rc='c';
   lar2.num=i;
: u" d3 Y! h# L; H   lar2.value=c_penum;
  }</P>
<> if(lar1.value==lar2.value&amp;&amp;(lar1.num!=lar2.num||lar1.rc!=lar2.rc)) {
- r/ ]; t9 e) ^( ~: i; s+ {1 i  f. ^  if(lar1.rc=='r'&amp;&amp;lar2.rc=='r') {
   temp=temp_ab[lar1.num][1];
8 x) f5 S8 O1 i   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];
( A2 G( u( w6 j! |     r=lar1.num;
     c=i;
    }
    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
3 r6 X, i1 g( u' p     r=lar2.num;
     c=i;
: ~0 O9 H8 N2 b1 ^7 B    }
, Z5 ~+ g3 F. c8 z8 @   }
3 c. z; N- s: F% E% U  }
  if(lar1.rc=='c'&amp;&amp;lar2.rc=='c') {
  O. Y& M2 D7 S* V7 H   temp=temp_ab[1][lar1.num];
   r=1;
      c=lar1.num;
   for(i=1;i&lt;=num_a-1;i++) {
% N$ Y( a$ _- h8 ~0 K    if(temp_ab[lar1.num]&lt;temp) {
     temp=temp_ab[lar1.num];
     c=lar1.num;
9 c9 `6 `! z5 `# j/ b     r=i;
    }
% r" g% |/ }9 U9 b) W    if(temp_ab[lar2.num]&lt;temp) {
; v$ a, W  @1 O. x     temp=temp_ab[lar2.num];
     c=lar2.num;
- P* q; \" ~' r! U0 w     r=i;
    }
' E) j2 S  S: r6 `7 \" x7 u. Q   }
  }
6 e1 D8 s% ~5 V( e+ |  if(lar1.rc=='r'&amp;&amp;lar2.rc=='c') {
6 ~( h2 X9 E/ {  @   temp=temp_ab[lar1.num][1];
! W5 [& s6 i, b   r=lar1.num;
      c=1;
   for(i=1;i&lt;=num_b;i++)
, L" z3 {! \$ n: E6 z- ]' M  ]    if(temp_ab[lar1.num]&lt;temp) {
: ?# X( l- H4 }% I! a0 K     temp=temp_ab[lar1.num];
9 k  x- D" y% G+ k5 R5 U     r=lar1.num;
3 z) g, E; u" ~7 W/ x; {     c=i;
3 ?% \6 q9 p5 D. `" C    }
   for(i=1;i&lt;=num_a;i++)
, r+ Z' J6 S: e, d0 l' m- C# P    if(temp_ab[lar2.num]&lt;temp) {
" i% _; G2 T; ]     temp=temp_ab[lar2.num];
     c=lar2.num;
     r=i;
! {, N* K" j  g7 W4 E4 J3 N    }
  }
3 Y8 j# p* {! C% ?  N3 z7 g  if(lar1.rc=='c'&amp;&amp;lar2.rc=='r') {
   temp=temp_ab[1][lar1.num];
   r=1;
6 {0 ?2 {- R5 r. T6 B      c=lar1.num;
% j, @; M3 R0 k( ]. U$ e   for(i=1;i&lt;=num_b;i++)
    if(temp_ab[lar2.num]&lt;temp) {
$ C. ]7 J8 i2 ]     temp=temp_ab[lar2.num];
     r=lar2.num;
     c=i;
    }
, i( B5 A' v8 ~5 R) d7 [% o   for(i=1;i&lt;=num_a;i++)
( \, q6 p3 B% G4 V' {: \. v/ P4 W    if(temp_ab[lar1.num]&lt;temp) {
9 V* a* J) U7 F% S     temp=temp_ab[lar1.num];
. w/ h5 m/ i/ f( w     c=lar1.num;
     r=i;
1 B& p8 s$ ?5 B+ V* A: h    }
  }
}
) {- V4 _7 z5 @# W1 A else {
3 v9 ?% O3 S, H! G/ ?/ W4 m  if(lar1.rc=='r') {
   r=lar1.num;
   c=1;
   temp=temp_ab[lar1.num][1];
5 Z3 K8 V8 J% Z; X3 v. s+ l   for(i=1;i&lt;=num_b;i++)
8 e) O: `/ P' Q  ?    if(temp_ab[lar1.num]&lt;temp) {
2 ~8 N0 x, |* l     c=i;
     temp=temp_ab[lar1.num];
    }
  }
  else {
) o8 Y( d. G; D' y0 g   r=1;
   c=lar1.num;
, z9 V; `$ i) ?% W5 W% z' r. {   temp=temp_ab[1][lar1.num];
" V0 r& i3 N4 {3 J/ o   for(i=1;i&lt;=num_a;i++)
    if(temp_ab[lar1.num]&lt;temp) {
9 f4 ?2 e. \! g& J# |" B9 p8 e3 J     r=i;
$ T# o  {( ]4 e0 B1 _& ^0 R     temp=temp_ab[lar1.num];
    }
* b8 k0 v" G9 l) e& T1 P: L2 `  }
1 u) W+ q+ e- A: v }
  I: @* l3 J9 G" ]' [ pbase[r][c]=1;
if(temp_a[r]&gt;temp_b[c]) {
% q" b. w9 A  _) o  base[r][c]=temp_b[c];
& A2 X: d" D4 E* @$ H5 {  temp_a[r]=temp_a[r]-temp_b[c];
4 b  @# C# y5 P, F( X3 q& t  temp_b[c]=0;
& M* ^( C& `1 U* f8 @( v  for(i=1;i&lt;=num_a;i++) temp_ab[c]=M;
}
$ ~/ v0 C( Q) ?& D! _8 Y2 ] else if(temp_a[r]&lt;temp_b[c]) {
) f8 j& ]' L/ i8 r: R6 u' m3 N  base[r][c]=temp_a[r];
" |8 S' y1 f0 h$ |  temp_b[c]=temp_b[c]-temp_a[r];
0 z8 j& p! R0 z# W: _  temp_a[r]=0;
  for(i=1;i&lt;=num_b;i++) temp_ab[r]=M;
}
else if(temp_a[r]==temp_b[c]) {
  base[r][c]=temp_a[r];
4 `7 B. p$ H6 N; e% L  temp_a[r]=temp_b[c]=0;
: r" f& G; @- d  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;
  for(i=1;i&lt;=num_b;i++) if(temp_b!=0) k=1;
  if(k!=0) {
2 u. l# v' y8 g0 |   k=0;
1 E% O2 P$ ^9 R; w* {! b6 B   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;}
. U6 g# v: R5 n1 L; V) o   if(k==1) pbase[c]=1;
3 D1 K( A8 {$ r3 Q1 n8 _   else if(k==2) pbase[r][j]=1;
  }
( D% [. V$ m" {; t: C6 R }
k=0;
0 ^( X7 i$ y& G, ]  }6 b 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;
findinit();
* b. ~( _8 X: P, V3 T}</P>
<>void computeuv() {
! e+ f0 S7 v' T" N int i,j,k;
0 o6 ^. R, p( {4 y( P) U for(i=1;i&lt;=num_a;i++)
  for(j=1;j&lt;=num_b;j++)
5 t# X/ b0 c  ~( U   if(pbase[j]==1) {
& j3 {. W5 Z1 b    if(pu==1) {v[j]=ab[j]-u; pv[j]=1;}
    if(pv[j]==1) {u=ab[j]-v[j]; pu=1;}
6 Y. H+ L- f& O8 q! x+ Q   }
" g- M9 e) ?' \/ I k=0;
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;
8 y0 Z( _& q0 g- M if(k==1) computeuv();
}</P>
<>int check() {
: e1 ~7 o7 y6 U0 g% e; r" H int i,j,k,l;
k=l=0;
/ Z& W. K2 c0 k1 ~% a. n# I for(i=1;i&lt;=num_a;i++)
  for(j=1;j&lt;=num_b;j++)
8 O  d( D. X: D   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;
   }
; {2 [" W- Q6 r& ?$ b8 H: r/* for(i=1;i&lt;=num_a;i++){
4 i. o- R: v  T# y8 V) i* A  V  for(j=1;j&lt;=num_b;j++) printf("base %lg\t",base[j]);
' D& V' n: |+ l  putchar('\n');}
% Q3 b" y$ ~6 { for(i=1;i&lt;=num_a;i++){
  for(j=1;j&lt;=num_b;j++) printf("pbase %d\t",pbase[j]);
  putchar('\n');}
8 g4 ~' B- K1 O; c" t*/
if(k==0&amp;&amp;l==0) {status=1; return 1;}
else if(k==0&amp;&amp;l!=0) {status=-1; return 1;}
1 ?) k4 J& u& s! A6 R else return 0;
}</P>
<>int circle(enum direction dir,struct element cir[],int *t) {
int i,j,k;
3 g9 Q( |) o- G2 f) e /*
putchar('\n');
0 w2 L$ z' P2 f for(i=1;i&lt;=*t;i++) printf("%d: r%d c%d\t",i, cir.r,cir.c);
; X* k3 H, J2 o; \3 x9 b5 H. }; Q, q putchar('\n');
" j5 h& q( n; l9 w0 d */
if((*t)!=1&amp;&amp;cir[(*t)].r==cir[1].r&amp;&amp;cir[*t].c==cir[1].c) {
" [8 N6 R7 V3 Y+ s  t--;
  return 1;
5 d  \! M* @4 M) E( |+ f }
if(dir!=down) {
) J6 b# q9 o$ R3 S, h8 d0 P  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;}
* l! ~# C3 V% s, P0 ^9 u9 {9 C0 k  for(j=2;j&lt;=*t;j++) if(i==cir[j].r&amp;&amp;cir[*t].c==cir[j].c) k=0;
( O( ~1 J" W0 I: m& {5 z8 `4 c  if(k==1) {
% A) Y; Z& R0 L3 U; ^2 J. y   if(dir==up) cir[*t].value=0;
   else cir[*t].value=1;
   (*t)++;
  L& J2 z6 ^4 |   cir[*t].r=i;
2 o* `% O) v6 V' X2 D$ Z4 |2 b   cir[*t].c=cir[(*t)-1].c;
5 P2 v5 L& y: a; f( t   if(circle(up,cir,t)) return 1;
+ i* R3 z/ L7 K/ G2 p1 S: h+ R9 G4 m  }
9 J5 X; m/ X, x; P1 \8 r }
! X5 T" t; P" b# h2 W* g( Z if(dir!=up) {
  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;}
! A; ?# u1 Q$ i( X$ v  a  for(j=2;j&lt;=*t;j++) if(i==cir[j].r&amp;&amp;cir[*t].c==cir[j].c) k=0;
1 b3 }! D! ~, d7 A  if(k==1) {
   if(dir==down) cir[*t].value=0;
   else cir[*t].value=1;
   (*t)++;
' `: X/ v- }% R3 k- u  }   cir[*t].r=i;
6 a/ y% _; [& i( m" X0 l: D   cir[*t].c=cir[(*t)-1].c;
9 Q, I! M4 }% U" D$ x   if(circle(down,cir,t)) return 1;
; A6 p1 ?8 v. ~; A  }
! @4 s' D4 ?  f }
if(dir!=right) {
4 i6 ]& I' N' H& j9 @  k=0;
  for(i=cir[*t].c-1;i&gt;=1;i--)
: m; l0 ~/ O& I* g- I2 |( G   if(pbase[cir[*t].r]==1||(cir[*t].r==cir[1].r&amp;&amp;i==cir[1].c)) {k=1; break;}
; s, k' z& @/ I! q$ a" J+ |5 Y  for(j=2;j&lt;=*t;j++) if(cir[*t].r==cir[j].r&amp;&amp;i==cir[j].c) k=0;
% _- F+ S2 Y8 @+ k% D  if(k==1) {
- R0 X1 o7 H- x3 I' Z' e; l   if(dir==left) cir[*t].value=0;
. t7 I# c  M; i   else cir[*t].value=1;
3 t& H6 v; |3 ~( k1 V   (*t)++;
  Y& d1 Y4 I7 `+ M( E   cir[*t].r=cir[(*t)-1].r;
2 }9 O) s5 u( d  Y& _& q% k  N& R   cir[*t].c=i;
   if(circle(left,cir,t)) return 1;
  }
}
if(dir!=left) {
0 g* d, @8 X1 p! Q  k=0;
  for(i=cir[*t].c+1;i&lt;=num_b;i++)
* s) T: u! D$ J  G8 H. ^7 w   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;
7 }! A( s" _3 |+ J* p; ?& N2 O% ]  if(k==1) {
9 n, e+ ^6 o2 G! O7 ?$ V! Z! e   if(dir==right) cir[*t].value=0;
   else cir[*t].value=1;
$ s7 a( @! _. \9 }) F3 B# x! V   (*t)++;
6 j( |3 K, P( V, }* D9 X- ]   cir[*t].r=cir[(*t)-1].r;
   cir[*t].c=i;
   if(circle(right,cir,t)) return 1;
; A. M" w$ a4 U% X, B$ {! a  }
$ ]. z5 K4 T# n7 f' t- W }
# _# C  y2 }9 d7 ]2 Q# P" C (*t)--;
, K7 q% H" R  r$ Q9 @ return 0;
9 [6 B/ c" V- ?( b% f; w! w}</P>
<>void improve() {
int i,j,k,t;
struct element base_in,base_out,cir[2*MAX+1];</P>
<> for(i=1;i&lt;=num_a;i++) pu=0;
for(i=1;i&lt;=num_b;i++) pv=0;
u[1]=0; pu[1]=1;
computeuv();
if(check()) return;
for(i=1;i&lt;=num_a;i++)
) `# G$ b' t$ k, A. ?. I5 S  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==0) break;
base_in.r=i;
8 l% X9 L2 l/ M 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++)
   if(pbase[j]==0&amp;&amp;base[j]&lt;base_in.value) {
    base_in.r=i;
    base_in.c=j;
2 c: L* B& ]' Q) {    base_in.value=base[j];
   }</P>
& g4 I: v9 n6 X$ V<> t=1;
% i1 @) G6 y5 t& E3 N/ `% D# V cir[t].r=base_in.r;
cir[t].c=base_in.c;
8 |6 G1 U1 w2 C+ M8 _% r cir[t].value=1;
if(!circle(mid,cir,&amp;t)) {
' T* s8 r$ A  _, v6 E6 S4 d5 T  printf("程序出错！按回车结束");
# e' ?! G. b, E$ n3 v8 `9 _2 g0 H  getchar();
5 A; C* q' `4 _* E/ _  exit(0);
}
t--;
// for(i=1;i&lt;=t;i++) printf("%d:r%d c%d v%lg\t",i,cir.r,cir.c,cir.value);
! E4 v2 e% {0 S9 `4 I1 ]; H/ Y// putchar('\n');</P>
( i8 h) l) I& B' \$ W+ v<> for(i=2;i&lt;=t;i++) if(cir.value==1) break;
: z' n. u/ j$ f! X9 ]0 i+ G base_out=cir;
base_out.value=base[cir.r][cir.c];
k=1;
/ ~9 ?/ t: o1 Q) Y: ?; M for(i=1;i&lt;=t;i++)
( I$ z/ p- M' P  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];
   k++;
, x, w" i! f5 n5 b( p! z2 M3 v  }
  else if(cir.value==1) k++;
base[cir[1].r][cir[1].c]=0;
k=1;
for(i=1;i&lt;=t;i++) {
; y3 O! G0 Z/ A9 i6 o/ m& i  if(k%2==1&amp;&amp;cir.value==1) {
   base[cir.r][cir.c]+=base_out.value;
( B# e9 a, C. {- B+ G# c- [   k++;
  }
  else if(k%2==0&amp;&amp;cir.value==1) {
% {/ u4 j  g, Q. t# [   base[cir.r][cir.c]-=base_out.value;
   k++;
8 U5 t3 M4 G, Q; q  }
% W( N/ }  d/ K. z$ V8 {# T }
  S  g5 I& L3 Z& I pbase[base_out.r][base_out.c]=0;
0 @2 U. J4 {* `- d. l pbase[base_in.r][base_in.c]=1;</P>
<> improve();
0 e/ S; \* u3 Q$ L/ `/ V}</P>
<>void output() {
3 j/ J1 O! I6 h0 E int i,j;
double sum=0;
7 ^4 `- a# e. f* f" O  M' o printf("\n运量为：\n");
2 p' i+ C+ w# O, }, q0 }' F for(i=1;i&lt;=num_a;i++) {
  putchar(' ');
) j- s) g. y7 E9 N% R5 R  for(j=1;j&lt;=num_b;j++)
6 c# E" h& N7 \   if(pbase[j]==1) {
! j; F0 l: Z. {7 K! c    printf("A%d-&gt;B%d:%lg\t",i,j,base[j]);
% W6 g/ L3 v' x2 Q  |    sum+=base[j]*ab[j];
) }3 K2 V. {- C   }
3 [3 {2 ]/ n3 o! O8 A$ h) N$ {   else printf("A%d-&gt;B%d:0\t",i,j);
! R8 U' y+ d' K. M5 [* ^6 w  putchar('\n');
: g$ T! D: y1 c. u. l. d5 Q- D$ | }
% y- d0 _5 o$ l1 b3 A" C printf("\n最低总运费为：%lg\n",sum);
}
& \! N$ Q3 J2 `' \% j; D</P>

zhongguohelin

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

enrique08

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

hzlhm

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

liunengwu

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