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

plgatc

<>/*************************************************************************
# Z8 o& h( s- w" T* w7 j/ ]+ }                         表上作业法解运输问题        
( Z1 h* e9 Z9 j3 v4 G
  O4 o9 L9 Q5 u. \ 编程环境：VC++6.0     
# O6 t# {* `* P0 V; _! } 程序说明：
6 q* S( @( p6 i- d" Z' n5 e/ S- R Vogel法求初始解，位势法检验是否最优，递归搜索闭回路改进解。
& O) E3 b$ M$ D *************************************************************************/
#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;</P>
<>#define MAX 100
* Q* \' ]* z) z5 S#define M 999999</P>
<>int status; //1唯一最优解，-1无穷多最优解</P>
( w; B% A' k6 u2 d- y% J, v5 k<>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];
8 ]. i2 [' o7 c2 F6 J5 C+ Y* H. qdouble ab[MAX][MAX],temp_ab[MAX][MAX];
, B! X2 Z) ~, @7 ndouble base[MAX][MAX];
- A  |$ H# p: g+ H0 s- ~# Uint pbase[MAX][MAX];
0 y4 m  ~; E! X: H, xstruct element {
int r;
int c;
double value;
};
' F6 x* V& v7 R; Yenum direction {mid,up,down,left,right};</P>
<>void create();
% x, _1 R) n# ]. u" @- ?void banner();
double dabs(double d);
void findinit();
void computeuv();
+ ~7 i9 B+ M) C/ \# W& k: ~; Uint check();
int  circle(enum direction dir,struct element cir[],int *t);
void improve();
void output();</P>
6 {8 X% K6 F# G4 A5 E<>void main() {
9 G; t: d, I3 R. Y banner();
7 J" v' _, j2 ?4 T3 ~ create();
! z9 t) h8 K& m) o* r printf("\n按回车确认后开始求解");
6 o: ^) R+ x5 {+ E) |. ] getchar();
getchar();
. J0 o( }, v. v  `( N( S. M findinit();
9 I2 @0 l* [* T1 T improve();
0 M, x0 ]/ S' b$ I: q switch(status) {
; i9 B: _0 M( U+ H, ` case 1:
  output();
4 j) C8 O- q5 \! c2 a  puts("\n原问题有唯一最优解。\n");
  puts("\n按回车结束");
6 v: ]8 |( b1 X  getchar();
  exit(0);
case -1:
5 w5 A% u7 |8 y. Z6 q" R# R  output();
; B2 N& E$ P& _  puts("\n原问题有无穷多最优解。\n");
) q  o* I5 F$ Q5 k# }, _( Z  puts("\n按回车结束");
  getchar();
) `( o/ s: J" ^5 _2 o  exit(0);
3 C' D  q1 ^: F5 }; p5 Z }
}</P>
<>void banner() {
7 ]; M; u" G$ S0 w* f4 I printf("\t\t****************************************\n");
printf("\t\t         表上作业法解运输问题\n");
printf("\t\t                              Thunder\n");
! W+ t- `7 x% b, _3 d printf("\t\t****************************************\n");
/ t+ h8 O7 a( ^7 D0 i printf("\n");
}</P>
2 s; z" _& t6 c  o+ V<>void create() {
- }( `+ S& ^: [7 a, n1 T; K int i,j;
double sum_a,sum_b;
char confirm;
) x' s2 d- b' w( B% C, z- p while(1) {
  printf("请输入产地个数：");
  T. [0 _) [7 j# p3 v  scanf("%d",&amp;num_a);
  for(i=1;i&lt;=num_a;i++) {
6 r0 F. t: A8 s   printf("A%d产量：",i);
   scanf("%lf",&amp;a);
+ x" M# p1 F* P" J2 B! s  }
! y" E8 F5 ~9 V6 z, c! F+ |  for(i=1;i&lt;=num_a;i++) printf("A%d产量：%lg\t",i,a);
3 H' o) M( C% Z3 e$ B  printf("\n正确吗？：(y/n)");
  getchar();
  confirm=getchar();
/ \3 c5 `# n5 |, [2 w+ c( u' `' H  if (confirm=='y') break;
9 S& I% {6 T/ [. r  else if(confirm=='n') continue;
}
% {5 I: d! @- G' \ while(1) {
" e" j; ^$ k; |: j* }/ \( n  printf("\n请输入销地个数：");
  scanf("%d",&amp;num_b);
' R9 \: q$ C; @* B) v* A: q: p0 K  for(i=1;i&lt;=num_b;i++) {
   printf("B%d销量：",i);
* J" m: D& Y: s   scanf("%lf",&amp;b);
  }
: o: Y+ j6 t# `! _' _  for(i=1;i&lt;=num_b;i++) printf("B%d销量：%lg\t",i,b);
( I3 E% n; ], B8 e( J  printf("\n正确吗？：(y/n)");
  getchar();
7 L* b6 A  Z! z( P  confirm=getchar();
) r- N% [- Z# |0 W$ P' Q1 V2 S. y  if (confirm=='y') break;
  else if(confirm=='n') continue;
. [4 K7 h; x( E" z }
putchar('\n');
, u: l3 z4 c) w2 t/ q for(i=1;i&lt;=num_a;i++) {
( `1 E9 Y. W' c- g1 h* S# j  for(j=1;j&lt;=num_b;j++) {
8 Y/ f) e; I* _   printf("A%d到B%d运价：",i,j);
4 Y  w: j9 q+ Q! `) a   scanf("%lf",&amp;ab[j]);
  }
  for(j=1;j&lt;=num_b;j++) printf("A%d到B%d：%lg\t",i,j,ab[j]);
8 z1 U  r* F$ c! r" Y! a( o  z  printf("\n正确吗？：(y/n)");
" N) g8 z9 D& }" N4 \! t  getchar();
; P6 Y5 \, F1 |2 E  confirm=getchar();
  if(confirm=='n') i--;
  putchar('\n');
" ]3 {+ r! D* ^4 p5 U1 w) o& T7 o }
//处理产销不平衡的情况
sum_a=sum_b=0;
2 d5 L1 J1 ^7 O1 k" G6 x for(i=1;i&lt;=num_a;i++) sum_a+=a;
for(i=1;i&lt;=num_b;i++) sum_b+=b;</P>
; ^' F6 x. z* Y$ b% i4 a<> printf("总产量：%lg\t总销量：%lg",sum_a,sum_b);
if(sum_a==sum_b) printf("\t产销平衡。");
else if(sum_a&gt;sum_b) {
' e4 l: |3 B# _- F9 U  printf("\t供大于求，增加假想销地B%d。\n",++num_b);
. K: |3 o4 [. a" H0 f! j" G0 E5 q  b[num_b]=sum_a-sum_b;
  for(i=1;i&lt;=num_a;i++) ab[num_b]=0;
}
& T% E1 e* ]- V$ k else if(sum_a&lt;sum_b){
  printf("\t供不应求，增加假想产地A%d。\n",++num_a);
# t/ ^+ e, T4 z& v5 l  a[num_a]=sum_b-sum_a;
  for(i=1;i&lt;=num_b;i++) ab[num_a]=0;
}
//求解前的准备
4 [% T, D. T5 s1 |7 c4 G0 V. J, @2 } for(i=1;i&lt;=num_a;i++)
. v/ f5 b, H2 {8 d/ w0 i% x& F  for(j=1;j&lt;=num_b;j++)
+ V; U- z/ k0 P0 p   base[j]=pbase[j]=0;
for(i=1;i&lt;=num_a;i++) temp_a=a;
& \: c- q5 n$ O0 C1 J for(i=1;i&lt;=num_b;i++) temp_b=b;
9 C9 ]- l4 M) |  q: @0 `# { for(i=1;i&lt;=num_a;i++)
for(j=1;j&lt;=num_b;j++) temp_ab[j]=ab[j];
//回显问题
! G: F3 K8 z; F7 w printf("\n\n原问题为：\n\n");
' S  m2 Y* M; d0 Q6 m. ?   printf("产量：\n ");
+ r- K  x+ h/ a8 b for(i=1;i&lt;=num_a;i++) printf("A%d:%lg\t",i,a);
printf("\n运量：\n ");
" c( r6 Y# E4 F. j$ q for(i=1;i&lt;=num_b;i++) printf("B%d:%lg\t",i,b);
4 b# S: X- p/ \$ v1 R printf("\n运价为：\n");
" T" E- W0 J( L% A. g2 \& @( j for(i=1;i&lt;=num_a;i++) {
1 |( {6 W  Y' U/ h  putchar(' ');
, H' L; O: r/ O: @1 i+ |# c  for(j=1;j&lt;=num_b;j++)
   printf("A%d-&gt;B%d:%lg\t",i,j,ab[j]);
& H! e8 k0 m/ O' Q2 M  putchar('\n');
# ]5 V0 C# J( {. @9 n }
}</P>
<>double dabs(double d) {
if(d&gt;=0) return d;
else return -d;
}</P>
/ T" ~0 I# K, N: o; Q$ @! i<>void findinit() {
7 Y9 B' s/ g: s int i,j,k;
, G& O, V  Q9 n  F* B6 o double r_penum[MAX],c_penum[MAX];
; [" R8 h3 |- y; C1 X) Q struct largest {
) e* X* P1 L4 S8 M6 _  char rc;
) z: q2 [" g% c. k5 m1 q- N- g  int num;
# N3 ], O) Z" B1 c( X  double value;
};
) Y& w4 g+ t& R2 ^1 o: p: o struct largest lar1,lar2;
int r=0,c=0;
1 h" ^" \/ k( C4 N, |/ Q double a1,a2,b1,b2,temp;</P>
<> for(i=1;i&lt;=num_a;i++) {
  temp=temp_ab[1];
& {6 B# `. d5 c& V. \  for(j=1;j&lt;=num_b;j++)
   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
8 F! {1 T( `/ {# b  a1=a2=temp;
  for(j=1;j&lt;=num_b;j++)
4 F3 f6 |4 a" e1 J) K   if(temp_ab[j]&lt;=a1) {
# g0 A" r" E3 v5 a* K& v* B$ t    a2=a1;
2 Q0 R9 y/ L0 U# z! L$ `  x    a1=temp_ab[j];
   }
   else if(temp_ab[j]&lt;=a2) a2=temp_ab[j];
  r_penum=dabs(a1-a2);
}</P>
1 A2 e; p* W2 M4 b# n9 a% q" j<> for(i=1;i&lt;=num_b;i++) {
  temp=temp_ab[1];
  for(j=1;j&lt;=num_a;j++)
   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
& w( c4 F  B" }' r# v  b1=b2=temp;
  for(j=1;j&lt;=num_a;j++)  
  a4 L" q4 ~% _& w7 M   if(temp_ab[j]&lt;=b1) {
# O0 K5 j: d1 g' ]6 C, n    b2=b1;
5 N" v! |4 w# k    b1=temp_ab[j];
   }
   else if(temp_ab[j]&lt;=b2) b2=temp_ab[j];
  c_penum=dabs(b1-b2);
}
0 y( d% w5 S" z' v: {6 U5 { /*
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);
*/
; N' ]2 T1 A9 S8 L5 ? temp=r_penum[1];
% W' `. }& I0 X1 q( X( o for(i=1;i&lt;=num_a;i++) if(r_penum&lt;temp) temp=r_penum;
( }, N8 `! ~# V) H6 z+ T for(i=1;i&lt;=num_b;i++) if(c_penum&lt;temp) temp=c_penum;</P>
7 G* L+ _" L4 Z; n$ x<> //考虑了有两个罚数相等的情况，大于两个相等只取其中两个进行比较
5 g8 K9 ?' t( ?* z8 a lar1.value=lar2.value=temp;
lar1.num=lar2.num=1;
$ m9 o8 V3 ~4 G& [' \4 ?1 Z) ^6 ` lar1.rc=lar2.rc='r';
0 W' M% k  X4 y for(i=1;i&lt;=num_a;i++)
( }% t3 i- Z; J2 c  if(r_penum&gt;=lar1.value) {
3 L" T/ h$ t' C3 L8 j* |( U9 e& A   lar2=lar1;
# Y$ a- {. _5 {  i5 p   lar1.rc='r';
/ T& \! |# V; [( ^# j) t, x1 l   lar1.num=i;
   lar1.value=r_penum;
  }
# A# U6 s) y5 d  Z( `" }  E3 V  else if(r_penum&gt;=lar2.value) {
# V& ~1 \8 v; L( g, o  m   lar2.rc='r';
# g, m% W- _' v: M   lar2.num=i;
" x8 b# ^9 G  G/ n4 [6 x6 I( g   lar2.value=r_penum;
  }</P>
# S' Z$ I; Z0 D) ^5 @<> for(i=1;i&lt;=num_b;i++)
/ @: Y5 Y# @) M; V3 ?8 i7 P  if(c_penum&gt;=lar1.value) {
   lar2=lar1;
/ m' R; b4 L  M   lar1.rc='c';
   lar1.num=i;
0 p- z/ y# J  S+ s   lar1.value=c_penum;
  }
  else if(c_penum&gt;=lar2.value) {
' ~9 B$ Q# b/ h% q' X& a   lar2.rc='c';
   lar2.num=i;
9 x8 b, ]2 w* `8 U   lar2.value=c_penum;
  }</P>
<> if(lar1.value==lar2.value&amp;&amp;(lar1.num!=lar2.num||lar1.rc!=lar2.rc)) {
% R5 ]  M; V  }( |. i) T  if(lar1.rc=='r'&amp;&amp;lar2.rc=='r') {
   temp=temp_ab[lar1.num][1];
   r=lar1.num;
# Z1 @( _( o/ I8 |      c=1;
, j4 r7 @& }5 z" p   for(i=1;i&lt;=num_b;i++) {
    if(temp_ab[lar1.num]&lt;temp) {
     temp=temp_ab[lar1.num];
% F7 N, W1 {: t/ A5 j     r=lar1.num;
     c=i;
! o% Y8 g3 W! N5 Z8 W7 ]    }
9 s* h1 j, T7 ^" X$ k: n    if(temp_ab[lar2.num]&lt;temp) {
  X8 g3 Z4 Q! @) [" J) @7 E5 R     temp=temp_ab[lar2.num];
     r=lar2.num;
     c=i;
: x8 {6 k# ]- K: E3 j9 W) }7 t    }
, x4 H6 f0 j4 {( g1 H. f$ g; i   }
  }
: I* W' R2 s8 y  if(lar1.rc=='c'&amp;&amp;lar2.rc=='c') {
   temp=temp_ab[1][lar1.num];
- l5 @! E, S4 A' E# R, {   r=1;
      c=lar1.num;
   for(i=1;i&lt;=num_a-1;i++) {
    if(temp_ab[lar1.num]&lt;temp) {
4 e% d5 {2 E' x# g     temp=temp_ab[lar1.num];
     c=lar1.num;
     r=i;
    }
    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
4 |4 l! v7 q8 I     c=lar2.num;
     r=i;
  f3 n/ C7 `' Z' B7 h    }
/ \/ |+ h. T) a  C4 L# W* @   }
' e; `% C5 t( D- l  ]  }
" r4 A( t: g/ u, I+ c8 r# G  if(lar1.rc=='r'&amp;&amp;lar2.rc=='c') {
( x/ X' ?. I2 p1 K* q4 e' ^   temp=temp_ab[lar1.num][1];
9 Q& p+ w8 f5 g2 U* J   r=lar1.num;
      c=1;
  {; M; _3 u3 r$ N1 Z8 S   for(i=1;i&lt;=num_b;i++)
6 }% a/ S& |2 r/ `* }6 B    if(temp_ab[lar1.num]&lt;temp) {
     temp=temp_ab[lar1.num];
     r=lar1.num;
: Q6 C2 D' O. w5 e: g     c=i;
    }
   for(i=1;i&lt;=num_a;i++)
    if(temp_ab[lar2.num]&lt;temp) {
% j; H, @6 h! `4 C     temp=temp_ab[lar2.num];
) K  x- i& x$ W( B3 K5 ~7 O# `     c=lar2.num;
2 W. t, d$ e) D0 D" D- Y     r=i;
$ a. G7 h( k3 u' g0 V    }
  }
& v6 @, }/ k5 v! n. @  if(lar1.rc=='c'&amp;&amp;lar2.rc=='r') {
( ]9 P1 T7 U( [% K+ m6 W7 n1 w   temp=temp_ab[1][lar1.num];
4 S6 z6 G4 Y/ H1 d   r=1;
4 [6 j$ T& g1 V8 \! w! @      c=lar1.num;
  @" `$ F% Z: J, a& a   for(i=1;i&lt;=num_b;i++)
    if(temp_ab[lar2.num]&lt;temp) {
; }9 Z; d. j& F5 y9 J$ [     temp=temp_ab[lar2.num];
2 m/ b7 b2 L  [' T7 w- m  O     r=lar2.num;
# I- w6 E: h; c1 b( z  G     c=i;
. [) X0 G/ F, A  @    }
   for(i=1;i&lt;=num_a;i++)
5 m4 c7 \2 _, z( t  E  t    if(temp_ab[lar1.num]&lt;temp) {
     temp=temp_ab[lar1.num];
     c=lar1.num;
     r=i;
% p/ z# I+ L! L5 f6 U' T+ l# K. ~( |    }
  }
2 G! X# C( ]3 R1 a }
else {
  if(lar1.rc=='r') {
; n1 h7 U; L" a3 }3 B; Z% W   r=lar1.num;
8 o$ [: t6 k, C% a   c=1;
   temp=temp_ab[lar1.num][1];
# O+ e, D# D8 t) ?/ f! Y   for(i=1;i&lt;=num_b;i++)
    if(temp_ab[lar1.num]&lt;temp) {
! ^2 T# H! E$ m5 n5 A     c=i;
& p" H6 G, G, E' {& Z7 q     temp=temp_ab[lar1.num];
2 {) K1 Q9 K( Q* S( D    }
  }
  else {
   r=1;
! ]8 L8 V9 {4 f3 T- h0 ]/ r   c=lar1.num;
9 s$ X- U& f7 T* a6 ~   temp=temp_ab[1][lar1.num];
. W) K# E$ ^/ {7 Q# I; i9 o   for(i=1;i&lt;=num_a;i++)
    if(temp_ab[lar1.num]&lt;temp) {
3 v% K4 T/ j3 s! c1 p) ]& {9 U" G     r=i;
, [9 m/ S+ P# F6 O0 _     temp=temp_ab[lar1.num];
5 \$ g8 ?6 N$ v% _0 J$ k; `2 v    }
  }
( M/ x- V3 Z7 n- y }
pbase[r][c]=1;
9 A! k6 |8 |, }+ I, F2 b- `0 h if(temp_a[r]&gt;temp_b[c]) {
/ ~( W1 R/ d( \, j4 w- i  base[r][c]=temp_b[c];
% H) a9 ^9 ?: L( l  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 k# v, g4 w2 C* G else if(temp_a[r]&lt;temp_b[c]) {
  base[r][c]=temp_a[r];
- ?+ l' Y8 ~* s. j( n+ B4 K9 F  temp_b[c]=temp_b[c]-temp_a[r];
4 x! @+ |# l/ c1 |  temp_a[r]=0;
  for(i=1;i&lt;=num_b;i++) temp_ab[r]=M;
# I6 W5 t) M& v& ?! e, W* V, B0 W }
else if(temp_a[r]==temp_b[c]) {
( |, |5 r" h4 w# H) A( h  base[r][c]=temp_a[r];
  temp_a[r]=temp_b[c]=0;
  for(i=1;i&lt;=num_a;i++) temp_ab[c]=M;
" p0 Y5 f: D; I+ C4 b7 @. o3 I  for(i=1;i&lt;=num_b;i++) temp_ab[r]=M;
0 z' p' k0 i2 ?* R- G1 j2 X% e2 @  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;
* e' x5 ~8 x8 K8 u  if(k!=0) {
   k=0;
$ [4 g% F5 e& C5 I, }% }   for(i=1;i&lt;=num_a;i++) if(pbase[c]!=1) {k=1;break;}
7 S6 o. s' j* Z" z( s) w" R2 B   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;
# L5 Y" V& ]; |  }
! m! z; M2 ~0 J7 [/ d2 ~& b0 M }
# w  @7 i5 S2 P, e. o5 d8 D k=0;
' q* p+ n- V/ y6 o- ^% |9 U 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();
}</P>
$ E6 z2 b( l9 Z7 k( e<>void computeuv() {
int i,j,k;
! g6 d4 X. ]" r# q- W6 w" ` for(i=1;i&lt;=num_a;i++)
0 h% w# I) s" h4 Y9 n  for(j=1;j&lt;=num_b;j++)
6 U8 u! o' U* n; [9 {   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;}
   }
k=0;
for(i=1;i&lt;=num_a;i++) if(pu==0) k=1;
% a, \& q: `1 S& x for(i=1;i&lt;=num_b;i++) if(pv==0) k=1;
# c/ N0 V1 k* e$ Z$ Q if(k==1) computeuv();
7 }& G+ [$ j+ |# D}</P>
- `$ g3 l# Z9 R, R( A! m. p<>int check() {
int i,j,k,l;
7 g/ L3 Z. t7 q k=l=0;
& t& h5 c( A% Y3 } for(i=1;i&lt;=num_a;i++)
% h: }( z) P2 `+ P  for(j=1;j&lt;=num_b;j++)
4 G" a2 F) D% |7 z! o' W6 U* n" N   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;
* f0 p7 V% B9 E/ T   }
! k4 \* F& [1 I5 N5 D, E! J* d% ~$ b/* for(i=1;i&lt;=num_a;i++){
  for(j=1;j&lt;=num_b;j++) printf("base %lg\t",base[j]);
7 t" z; |2 E) X, G  putchar('\n');}
for(i=1;i&lt;=num_a;i++){
& o6 U7 a, `4 P9 K3 P+ i  for(j=1;j&lt;=num_b;j++) printf("pbase %d\t",pbase[j]);
  putchar('\n');}
*/
7 ]" R( N1 e) L- M3 _ 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;
9 n( f( c1 a) F7 ?9 X" x) D" a1 `}</P>
' s! C; g( _+ T- q( S<>int circle(enum direction dir,struct element cir[],int *t) {
int i,j,k;
2 U  `& j% _$ Q' n5 z9 L' y /*
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--;
, D# h" i/ B, ~! I; u: i  return 1;
4 [# g5 `/ R9 C }
" R7 z* P" B0 R5 w4 V1 h* M* c7 f if(dir!=down) {
  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;}
  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) {
9 z" ]1 ^, n+ b, J$ L   if(dir==up) cir[*t].value=0;
) v/ @* r7 \/ q0 L( Z4 c   else cir[*t].value=1;
( H+ h6 |' W- l" k   (*t)++;
& k6 `. `) R- q   cir[*t].r=i;
   cir[*t].c=cir[(*t)-1].c;
8 M# s- L+ u6 U# g) ?   if(circle(up,cir,t)) return 1;
+ h, e! j  K7 F0 j8 H  }
8 o3 `6 L3 {; o6 E }
2 @3 o3 [% H9 d9 o5 _; Z5 q if(dir!=up) {
7 ]* J  m" s& H' D  k=0;
+ u$ x9 N8 Y6 L: l/ z) D* O  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;}
( {" y) ~1 P. A% g  for(j=2;j&lt;=*t;j++) if(i==cir[j].r&amp;&amp;cir[*t].c==cir[j].c) k=0;
: P$ _  t) ~; y9 C6 U' [" O' g0 h  if(k==1) {
   if(dir==down) cir[*t].value=0;
! i; u2 _& j! F% H   else cir[*t].value=1;
   (*t)++;
   cir[*t].r=i;
   cir[*t].c=cir[(*t)-1].c;
+ g4 w+ R4 g; E# G! j- H% I5 J   if(circle(down,cir,t)) return 1;
  }
6 m/ L1 T9 B7 h$ n4 Q, O  _; r) k5 R }
if(dir!=right) {
  k=0;
  for(i=cir[*t].c-1;i&gt;=1;i--)
   if(pbase[cir[*t].r]==1||(cir[*t].r==cir[1].r&amp;&amp;i==cir[1].c)) {k=1; break;}
9 C' W8 T& y5 D; W  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==left) cir[*t].value=0;
/ K4 C0 A3 w" l( a+ ^2 e8 l, p   else cir[*t].value=1;
& A1 }; M% `, L   (*t)++;
4 b' R, h8 u* U& R1 X' W   cir[*t].r=cir[(*t)-1].r;
   cir[*t].c=i;
' H9 v( m6 ?: }# {   if(circle(left,cir,t)) return 1;
  }
' p5 u' `2 N4 K7 N  C }
if(dir!=left) {
  k=0;
  for(i=cir[*t].c+1;i&lt;=num_b;i++)
5 `. x  {  L- c# K+ C* o2 P( v   if(pbase[cir[*t].r]==1||(cir[*t].r==cir[1].r&amp;&amp;i==cir[1].c)) {k=1; break;}
# u( p0 A6 a# I/ N' r# |  J! c! @4 L  for(j=2;j&lt;=*t;j++) if(cir[*t].r==cir[j].r&amp;&amp;i==cir[j].c) k=0;
' o: {! M- h/ T( u, N  if(k==1) {
& J! V: ~% V/ ^# |7 A" p   if(dir==right) cir[*t].value=0;
   else cir[*t].value=1;
   (*t)++;
   cir[*t].r=cir[(*t)-1].r;
1 O. H: y$ }* |9 O: M2 V; b2 W   cir[*t].c=i;
   if(circle(right,cir,t)) return 1;
* L! i( V: C  W0 v) j  }
}
(*t)--;
return 0;
}</P>
! u. m& f7 d+ I+ O& ~<>void improve() {
int i,j,k,t;
struct element base_in,base_out,cir[2*MAX+1];</P>
9 E, C) N; B* a1 @$ l4 K- t5 d<> 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;
* q- k- S7 P$ K  d* I computeuv();
) f2 D5 ~9 R% a- o, x0 o- W$ s4 R if(check()) return;
9 o8 y4 q0 p- b' c# y/ p for(i=1;i&lt;=num_a;i++)
5 `# r2 D: `: B  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==0) break;
' {+ N4 e/ P+ D/ O base_in.r=i;
- i" w+ q, j: W; n. U base_in.c=j;
* W' J9 d/ L) t/ ^; C5 E base_in.value=base[j];</P>
# B: _3 l% R3 R% ~<> for(i=1;i&lt;=num_a;i++)
7 ~6 H, E0 w: z+ w; Z  for(j=1;j&lt;=num_b;j++)
' e, z! l3 a5 }9 A9 D7 F   if(pbase[j]==0&amp;&amp;base[j]&lt;base_in.value) {
    base_in.r=i;
0 v$ F8 m( v/ p/ m2 ?6 _    base_in.c=j;
    base_in.value=base[j];
8 k- J1 J3 _  F' D  {7 x/ Y   }</P>
) d7 i7 k1 M7 T4 f, Z: y<> t=1;
cir[t].r=base_in.r;
cir[t].c=base_in.c;
cir[t].value=1;
9 g* }8 n/ _( U$ |; G- `8 @7 Z- W' ? if(!circle(mid,cir,&amp;t)) {
' c+ M7 T" }9 N! r5 ^" v7 |" p) n* J  printf("程序出错！按回车结束");
7 G. |0 {2 K6 q* p( K  getchar();
  exit(0);
}
t--;
( z2 o4 q5 ~1 F8 e8 @) c* t// for(i=1;i&lt;=t;i++) printf("%d:r%d c%d v%lg\t",i,cir.r,cir.c,cir.value);
* R( V0 Y. K. ]; z( y// putchar('\n');</P>
' }1 a* \. v. W: b- R<> for(i=2;i&lt;=t;i++) if(cir.value==1) break;
) G* ^' u+ j! h, M9 L base_out=cir;
4 [2 W4 }7 D8 [  g) \7 q6 v6 c base_out.value=base[cir.r][cir.c];
k=1;
( z- T0 z! o" O( `7 N1 w 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) {
+ u6 n( w; N7 J1 z0 G7 a; f   base_out=cir;
   base_out.value=base[cir.r][cir.c];
   k++;
  }
( A  n; N6 H! K8 j  Y) r* G" \  else if(cir.value==1) k++;
+ j; y' V1 Z, m: X  k- c base[cir[1].r][cir[1].c]=0;
* e- y' b. Y* a4 e7 O k=1;
: h$ \" J; _2 C. c/ q/ c for(i=1;i&lt;=t;i++) {
  if(k%2==1&amp;&amp;cir.value==1) {
   base[cir.r][cir.c]+=base_out.value;
5 Z9 R: e  i7 P: p   k++;
  }
& Y* a3 d" t8 r9 r- q3 ?3 @  else if(k%2==0&amp;&amp;cir.value==1) {
   base[cir.r][cir.c]-=base_out.value;
, o, c1 u: w/ q( G9 y: q- @   k++;
  }
}
pbase[base_out.r][base_out.c]=0;
+ t0 ?* p0 y: G pbase[base_in.r][base_in.c]=1;</P>
<> improve();
0 X; a" M. o+ j% Z+ g2 V8 d}</P>
) A+ f3 h% c  Z<>void output() {
, t: B2 }- F" w7 J int i,j;
double sum=0;
& A$ B  J  Z4 _) K9 V" n printf("\n运量为：\n");
$ I. M% Y6 a" Q for(i=1;i&lt;=num_a;i++) {
  putchar(' ');
  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==1) {
. t; V  ^& L4 ]) l    printf("A%d-&gt;B%d:%lg\t",i,j,base[j]);
% C, E& U6 O5 P* k5 h8 |, D    sum+=base[j]*ab[j];
   }
   else printf("A%d-&gt;B%d:0\t",i,j);
  putchar('\n');
; [# A: ~: y; r, E: ~ }
printf("\n最低总运费为：%lg\n",sum);
}
</P>

liunengwu

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

hzlhm

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

enrique08

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

zhongguohelin

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