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

plgatc

<>/*************************************************************************
                         表上作业法解运输问题        

, e( S  `0 m4 m) v7 I2 H 编程环境：VC++6.0     
1 \6 `4 D) i( h* x 程序说明：
* A- ^( u/ D2 W8 K6 ~% z Vogel法求初始解，位势法检验是否最优，递归搜索闭回路改进解。
1 k" R# }6 g; Z *************************************************************************/
; h5 W' w1 i$ ]" V0 g! W#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;</P>
7 u; [, D& k! z3 l<>#define MAX 100
. H: K3 q( H3 s0 S  X* _( S#define M 999999</P>
7 f$ z% S1 g5 a/ @  B3 Q. B, Q<>int status; //1唯一最优解，-1无穷多最优解</P>
" ^% u  ?$ g. n<>int num_a,num_b;
double a[MAX],b[MAX],temp_a[MAX],temp_b[MAX];
  H& |" Q. m! {6 F: X; Y% V4 Z* c+ xdouble u[MAX],v[MAX],pu[MAX],pv[MAX];
* c6 e. J! a. G, g& y* B& g7 hdouble ab[MAX][MAX],temp_ab[MAX][MAX];
6 m1 y! T* X+ d7 E9 X# _double base[MAX][MAX];
' P: [# U9 b% B. Z, r, Sint pbase[MAX][MAX];
struct element {
" k' `9 H/ t" i* s# \ int r;
+ u. j" G5 X% w$ }4 {% T, n# _ int c;
double value;
};
enum direction {mid,up,down,left,right};</P>
; Y2 p6 A! l- B<>void create();
2 T5 c4 [, Z6 D2 m8 J% Jvoid banner();
double dabs(double d);
: r  ?# K. N: V8 }void findinit();
0 j6 D: A" p/ u9 Bvoid computeuv();
# M+ e% B" ?4 H2 |0 ?+ v: }" P6 Nint check();
int  circle(enum direction dir,struct element cir[],int *t);
8 M) L2 V, A/ f6 c! l' G8 Bvoid improve();
void output();</P>
4 \0 q7 ~' U' }: g: a: ]  L8 g* u: @<>void main() {
2 X) K& X0 q" F banner();
create();
" D# C/ A2 L* `& y3 W printf("\n按回车确认后开始求解");
getchar();
getchar();
findinit();
3 Q4 m7 Y+ v; }( j improve();
switch(status) {
" N9 Q6 b# d- m$ b! Q case 1:
  output();
  puts("\n原问题有唯一最优解。\n");
  puts("\n按回车结束");
  getchar();
# k+ w% P) J. U1 Z. s  exit(0);
case -1:
  output();
  puts("\n原问题有无穷多最优解。\n");
1 W, n1 b. q1 K4 _! T8 X  puts("\n按回车结束");
- P# {1 [6 b4 F9 p( L  getchar();
7 k: I+ |( z4 o1 _9 \  exit(0);
}
7 ?9 x% I; O# D" i$ p; K! Y) [}</P>
! j. F6 L9 i, q' w- O<>void banner() {
printf("\t\t****************************************\n");
printf("\t\t         表上作业法解运输问题\n");
, a1 H2 m" ?* ` printf("\t\t                              Thunder\n");
2 B, W3 b6 z8 K- M+ ^, E1 j printf("\t\t****************************************\n");
printf("\n");
}</P>
* L1 N$ h3 O$ c* z2 Z8 T) Z& k+ m<>void create() {
int i,j;
+ Y! L5 f/ b9 q4 Z double sum_a,sum_b;
' o" v! l; t. ?% R& b& p) r+ r char confirm;
while(1) {
  printf("请输入产地个数：");
0 T. A) @5 ^# H: h% Z  E  scanf("%d",&amp;num_a);
  for(i=1;i&lt;=num_a;i++) {
   printf("A%d产量：",i);
   scanf("%lf",&amp;a);
* C" c! N% d& {: c1 ?- Q  }
: V! D! u! q- n  for(i=1;i&lt;=num_a;i++) printf("A%d产量：%lg\t",i,a);
  printf("\n正确吗？：(y/n)");
  getchar();
! \0 d0 l/ J. D! |# U+ N6 r) L7 {  confirm=getchar();
) O0 Z) R/ H6 C6 f# v* `  G/ x  if (confirm=='y') break;
  else if(confirm=='n') continue;
) ^3 j  l: U& z2 T5 X7 n }
' V) k% u/ r' S( z" z3 Y while(1) {
  printf("\n请输入销地个数：");
  scanf("%d",&amp;num_b);
+ C/ J& ?* G% x2 O2 R  for(i=1;i&lt;=num_b;i++) {
$ n" \3 M6 k4 b. o   printf("B%d销量：",i);
   scanf("%lf",&amp;b);
  }
  for(i=1;i&lt;=num_b;i++) printf("B%d销量：%lg\t",i,b);
; ~5 T8 P& e: W9 j3 {  printf("\n正确吗？：(y/n)");
  getchar();
  l# d( A5 F# y: F( F  confirm=getchar();
  if (confirm=='y') break;
  else if(confirm=='n') continue;
}
putchar('\n');
& X% \7 p8 \$ p for(i=1;i&lt;=num_a;i++) {
  for(j=1;j&lt;=num_b;j++) {
4 U. G- Z: |0 L   printf("A%d到B%d运价：",i,j);
' i% V* }7 L& Y   scanf("%lf",&amp;ab[j]);
5 K; A, c& r: R  e8 J  }
  for(j=1;j&lt;=num_b;j++) printf("A%d到B%d：%lg\t",i,j,ab[j]);
$ S$ r5 p- q/ |' S' t$ P: e  printf("\n正确吗？：(y/n)");
  getchar();
  confirm=getchar();
: q8 K) S$ s# b  if(confirm=='n') i--;
  putchar('\n');
9 X4 ^7 ]/ `! d; k5 ?. M }
//处理产销不平衡的情况
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>
<> printf("总产量：%lg\t总销量：%lg",sum_a,sum_b);
+ Q- I5 a! s& I  \$ S if(sum_a==sum_b) printf("\t产销平衡。");
else if(sum_a&gt;sum_b) {
( s% D/ d* k! Y7 _  printf("\t供大于求，增加假想销地B%d。\n",++num_b);
  b[num_b]=sum_a-sum_b;
: C. R7 {8 b: Y5 U  I6 w  for(i=1;i&lt;=num_a;i++) ab[num_b]=0;
}
: W# Z; J$ j9 a. T3 p' O* x else if(sum_a&lt;sum_b){
  printf("\t供不应求，增加假想产地A%d。\n",++num_a);
  a[num_a]=sum_b-sum_a;
% J: X7 n4 f4 R7 t) m3 H& I, E  for(i=1;i&lt;=num_b;i++) ab[num_a]=0;
}
3 ]) \, }, E: a0 j) }; X //求解前的准备
+ V" M! p" d3 m: e2 y$ e for(i=1;i&lt;=num_a;i++)
  for(j=1;j&lt;=num_b;j++)
   base[j]=pbase[j]=0;
# n8 G( _2 O3 x6 f0 o( e3 U 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++)
for(j=1;j&lt;=num_b;j++) temp_ab[j]=ab[j];
//回显问题
: ~. f8 n5 R% l5 L6 T1 d( | printf("\n\n原问题为：\n\n");
% F# l8 B* |! D) |0 u/ ]   printf("产量：\n ");
$ z& {, B0 L  b6 D8 d2 k. s. p 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);
( W' F/ z" S  W, A9 ?! o1 \3 b printf("\n运价为：\n");
for(i=1;i&lt;=num_a;i++) {
& }: k- {5 g3 ?" n0 t8 |4 L  putchar(' ');
) K: u# E7 a# [# m% Q: H$ E$ l) v  for(j=1;j&lt;=num_b;j++)
   printf("A%d-&gt;B%d:%lg\t",i,j,ab[j]);
9 o5 O2 I6 _; |% G4 T3 a0 V) Q  putchar('\n');
}
2 k# @7 S! A! ?" u! q4 c}</P>
- z# ]$ S7 s  c% D<>double dabs(double d) {
% o6 y, C- Y+ w& S if(d&gt;=0) return d;
1 ^3 @3 w  h3 g, j4 [8 R else return -d;
( }4 x4 I# J1 @# N% ^; R. I}</P>
<>void findinit() {
int i,j,k;
double r_penum[MAX],c_penum[MAX];
2 z' q7 [% l3 _$ e struct largest {
  char rc;
  int num;
  double value;
- H; w& a  a9 q/ F8 ~ };
struct largest lar1,lar2;
int r=0,c=0;
1 t9 W! R, b" ~' }4 q  d4 j double a1,a2,b1,b2,temp;</P>
- T. e; k# l: H2 j) d5 A<> for(i=1;i&lt;=num_a;i++) {
* p; I* E9 [) a  temp=temp_ab[1];
3 Z0 f+ d" k" Z' S  for(j=1;j&lt;=num_b;j++)
3 y. P! P. h  I9 t% x7 H   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
' j/ j( C9 [4 R6 \* m$ l9 T  a1=a2=temp;
  for(j=1;j&lt;=num_b;j++)
   if(temp_ab[j]&lt;=a1) {
    a2=a1;
1 I: J; C+ c% V' a( l0 z6 Y    a1=temp_ab[j];
   }
   else if(temp_ab[j]&lt;=a2) a2=temp_ab[j];
) m( y+ `2 G* q  r_penum=dabs(a1-a2);
0 Y( p6 Y: b0 V5 p7 U }</P>
<> for(i=1;i&lt;=num_b;i++) {
  temp=temp_ab[1];
  for(j=1;j&lt;=num_a;j++)
5 P$ W0 w& }% B  c, m   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
& Z- E- d: R6 o% ?# m  b1=b2=temp;
- Y7 w. E- D6 X- d% N+ M  for(j=1;j&lt;=num_a;j++)  
- ]- \* M4 O7 W4 a8 d4 h   if(temp_ab[j]&lt;=b1) {
7 p6 F: D% @3 Y: B2 C    b2=b1;
    b1=temp_ab[j];
$ F) o. w4 b# t  n* z   }
  F, }/ C* T- f) x0 Y   else if(temp_ab[j]&lt;=b2) b2=temp_ab[j];
  c_penum=dabs(b1-b2);
* q/ G6 U3 x  _  |! \ }
# t* A7 h! H5 _6 m6 y /*
for(i=1;i&lt;=num_a;i++) printf("pa%d=%lg ",i,r_penum);
# A  n# H+ h; F  E putchar('\n');
for(i=1;i&lt;=num_b;i++) printf("pb%d=%lg ",i,c_penum);
" F9 |" W+ o- Y! r */
' ]0 z, ]  ~7 f4 Y9 s$ b& i 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>
5 @) U1 w/ D( y* W$ w& w<> //考虑了有两个罚数相等的情况，大于两个相等只取其中两个进行比较
5 l; J* {1 M9 [ lar1.value=lar2.value=temp;
' R& {7 O# M% O" o' j lar1.num=lar2.num=1;
& @  i+ \( z, y# e+ [: q- D lar1.rc=lar2.rc='r';
for(i=1;i&lt;=num_a;i++)
9 u- j% V5 Y7 t& F+ ?  if(r_penum&gt;=lar1.value) {
/ q7 \$ H8 I  U. M- [3 k   lar2=lar1;
   lar1.rc='r';
0 q) H2 u, H6 D   lar1.num=i;
+ N8 z" U  k3 B1 D+ h   lar1.value=r_penum;
- c" I. p' m' f2 V  }
  r# s6 Z" s/ Z! R  else if(r_penum&gt;=lar2.value) {
( R* ~- P+ `$ i2 _# q" b   lar2.rc='r';
" z+ A+ A  S1 r/ n7 u5 _" y& n2 q' \7 s   lar2.num=i;
   lar2.value=r_penum;
1 O9 o+ b& L. r. I! {  }</P>
! @. f0 D& S* Q<> for(i=1;i&lt;=num_b;i++)
0 A2 Y; U  e4 p3 d  i  if(c_penum&gt;=lar1.value) {
3 Z# E  k. r) d$ V* S+ {" R   lar2=lar1;
$ h0 z' G: _9 U' j   lar1.rc='c';
7 t. H1 C( X" f5 w   lar1.num=i;
   lar1.value=c_penum;
  }
% r$ \7 p. `3 E6 p) n  else if(c_penum&gt;=lar2.value) {
   lar2.rc='c';
$ P" q7 [2 P. k* i/ m3 N   lar2.num=i;
6 Z- b% n( r& f5 ?3 Q; [   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') {
8 L. S7 I+ t9 L( V- a, {   temp=temp_ab[lar1.num][1];
   r=lar1.num;
      c=1;
   for(i=1;i&lt;=num_b;i++) {
7 K9 T+ P7 X* ^0 }  Y! Y! _0 f    if(temp_ab[lar1.num]&lt;temp) {
     temp=temp_ab[lar1.num];
# y6 z$ f  ?4 f: K& Y4 r     r=lar1.num;
* T, s; B* U0 \     c=i;
% o2 ]2 S, r  W! `) A$ P    }
    if(temp_ab[lar2.num]&lt;temp) {
7 c6 |2 f  ]5 W. Q" x& c/ g- C) {1 k     temp=temp_ab[lar2.num];
; I8 ]* J. a# L  N! B$ W     r=lar2.num;
6 i! T4 S* K& h- q8 b' P     c=i;
  ^9 Z1 A0 Q/ ^  N, v+ S9 w    }
   }
. v3 d6 H) D  V1 r  I* M' D  }
- _: ^  r9 {: E* A; E  if(lar1.rc=='c'&amp;&amp;lar2.rc=='c') {
   temp=temp_ab[1][lar1.num];
: h7 V: Y/ [. e' r1 }* M+ z   r=1;
8 k  C' l/ l5 S4 b9 w      c=lar1.num;
9 r: L  K; i- ~: H& W   for(i=1;i&lt;=num_a-1;i++) {
    if(temp_ab[lar1.num]&lt;temp) {
* H  f- m# E4 \2 j5 E     temp=temp_ab[lar1.num];
& U4 F0 V5 W! J6 g9 X, i: M     c=lar1.num;
/ ~8 ]! J7 r+ B. y" z     r=i;
    }
    if(temp_ab[lar2.num]&lt;temp) {
: T+ }  x; @& ^& H     temp=temp_ab[lar2.num];
     c=lar2.num;
& H" w! |4 y5 y8 H: a, B/ A& G5 w9 c     r=i;
    }
2 o7 P% R" g6 M& \   }
9 V% @" W' |) R# a3 d* d  }
  if(lar1.rc=='r'&amp;&amp;lar2.rc=='c') {
4 j" K, m4 B! H   temp=temp_ab[lar1.num][1];
+ X. [7 x: G' m2 ]! |+ y   r=lar1.num;
      c=1;
   for(i=1;i&lt;=num_b;i++)
    if(temp_ab[lar1.num]&lt;temp) {
+ I8 L/ v- `! c) y! T4 `     temp=temp_ab[lar1.num];
     r=lar1.num;
9 y. j2 R. Q( a) Z     c=i;
    }
   for(i=1;i&lt;=num_a;i++)
    if(temp_ab[lar2.num]&lt;temp) {
. O4 t( H- O  l+ u+ P3 D4 D     temp=temp_ab[lar2.num];
     c=lar2.num;
& W* E5 d9 f# s& N     r=i;
    }
; r/ W. C( D, e8 R$ l1 A- D  }
  if(lar1.rc=='c'&amp;&amp;lar2.rc=='r') {
   temp=temp_ab[1][lar1.num];
   r=1;
      c=lar1.num;
) e! Q" [. Y( `8 |   for(i=1;i&lt;=num_b;i++)
    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
     r=lar2.num;
& V1 d7 m1 J" I1 f     c=i;
$ x" l! C, q& X. D. ~# H9 q4 P    }
3 V& G8 A, r+ ^2 W6 y   for(i=1;i&lt;=num_a;i++)
$ ~6 Y8 V* ~+ m7 s% k* e/ W, D. K& x    if(temp_ab[lar1.num]&lt;temp) {
+ N. G/ [% s$ ~: l% V     temp=temp_ab[lar1.num];
     c=lar1.num;
2 w5 I) W5 a. Z, U     r=i;
$ ]0 _9 \1 v5 [# u' O    }
6 |9 ?( `" Z, X! J- w  }
/ G  G0 i1 I+ v& V. G. _, \ }
; l: L  E1 q, @  A, l+ Z# ^) ^ else {
$ Q  x. T6 l6 U! A0 x  if(lar1.rc=='r') {
9 _2 T+ b6 ]6 O8 H   r=lar1.num;
   c=1;
) u5 k4 a4 g3 R# C! B! V/ h0 Z: e+ g   temp=temp_ab[lar1.num][1];
   for(i=1;i&lt;=num_b;i++)
4 C1 Q& @5 v4 s# F5 e3 I6 M    if(temp_ab[lar1.num]&lt;temp) {
     c=i;
0 t: ^: u- f, j; j2 n# N     temp=temp_ab[lar1.num];
    }
  }
/ l! o$ f# v3 R  else {
* z  X+ V1 c% ]" @8 k4 r$ e   r=1;
   c=lar1.num;
   temp=temp_ab[1][lar1.num];
& h2 m( g5 T" {) f2 ^# e8 `- X# h7 e   for(i=1;i&lt;=num_a;i++)
    if(temp_ab[lar1.num]&lt;temp) {
     r=i;
7 q" K. Q+ I* ]/ m, o* i) X, n) C     temp=temp_ab[lar1.num];
    }
  }
% H$ X$ \, M2 @$ k2 Y' b }
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;
! S* L: n+ E6 u7 p- D  for(i=1;i&lt;=num_a;i++) temp_ab[c]=M;
* l; L# d$ {7 u9 a% Q- y- B }
else if(temp_a[r]&lt;temp_b[c]) {
  base[r][c]=temp_a[r];
  temp_b[c]=temp_b[c]-temp_a[r];
  temp_a[r]=0;
1 S+ f6 b9 y  _2 \2 ?3 S) \) F  for(i=1;i&lt;=num_b;i++) temp_ab[r]=M;
}
else if(temp_a[r]==temp_b[c]) {
2 z3 H# f/ m+ I, H3 t  base[r][c]=temp_a[r];
/ ]& r" T. [& J* |; z* M  temp_a[r]=temp_b[c]=0;
1 l$ Y. j, U) I! ]$ `  for(i=1;i&lt;=num_a;i++) temp_ab[c]=M;
) b! Q) N/ k6 I0 g, h1 u  for(i=1;i&lt;=num_b;i++) temp_ab[r]=M;
  t8 ?: D  ?1 v' |' J  k=0;
( L- @7 ?: T- n: j. 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;
  if(k!=0) {
   k=0;
: w% N9 X  k5 y: h. ^$ r   for(i=1;i&lt;=num_a;i++) if(pbase[c]!=1) {k=1;break;}
# h" G. M! i7 I3 v! Z+ E6 Q   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;
* W8 Z. R! ~4 S) H7 L  }
}
! {# D3 r& Q5 v2 ^ k=0;
for(i=1;i&lt;=num_a;i++) if(temp_a!=0) k=1;
; ?! D% `/ B# i7 V1 ^9 M' q6 ] for(i=1;i&lt;=num_b;i++) if(temp_b!=0) k=1;
# ]6 s6 Y) r; a: i9 ~ if(k==0) return;
findinit();
" p2 ~7 o7 J' F; [}</P>
7 ~) v3 ~2 V* l# D8 R* P$ B<>void computeuv() {
int i,j,k;
) l+ V" a' e" [: t& @1 A" n for(i=1;i&lt;=num_a;i++)
9 E- ^: g3 P, X$ @: \  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==1) {
    if(pu==1) {v[j]=ab[j]-u; pv[j]=1;}
1 h5 W: X4 K+ E/ [    if(pv[j]==1) {u=ab[j]-v[j]; pu=1;}
+ T/ h1 d( O% O$ O, Y+ n0 M   }
' U7 [) Q- [% Z8 q0 N, _3 I k=0;
for(i=1;i&lt;=num_a;i++) if(pu==0) k=1;
4 s, I; L) t' g$ K for(i=1;i&lt;=num_b;i++) if(pv==0) k=1;
* x: ?  ]8 R" P; T  b. X if(k==1) computeuv();
% S' P# a/ L7 b% W0 g( m% c}</P>
<>int check() {
int i,j,k,l;
/ m" K3 y0 V$ q8 z k=l=0;
( H6 m. Q+ X  j8 c0 A for(i=1;i&lt;=num_a;i++)
5 N1 C- v' c" @" E! {  for(j=1;j&lt;=num_b;j++)
- }+ V" v0 \- H: D2 D# H" @' E0 k   if(pbase[j]==0) {
* M6 U3 `. T; O- A5 m0 `    base[j]=ab[j]-u-v[j];
    if(base[j]&lt;0) k=1;
& C/ C: v$ [1 W" M8 `  d6 K$ l    else if(base[j]==0) l=1;
! [1 k  Z- C# |4 Z# k# X# T   }
/* for(i=1;i&lt;=num_a;i++){
  for(j=1;j&lt;=num_b;j++) printf("base %lg\t",base[j]);
  putchar('\n');}
! Z% j( y$ p4 p! N. `$ q4 P for(i=1;i&lt;=num_a;i++){
. P' }  a& O# o, h& k0 j  for(j=1;j&lt;=num_b;j++) printf("pbase %d\t",pbase[j]);
  putchar('\n');}
5 c- N" B" Z: \3 A; ~*/
if(k==0&amp;&amp;l==0) {status=1; return 1;}
% o" S" q6 O! r+ ~8 [! k( C- q else if(k==0&amp;&amp;l!=0) {status=-1; return 1;}
# g! A4 R, H% V: f! V/ w else return 0;
" |( B& I; Y8 W}</P>
<>int circle(enum direction dir,struct element cir[],int *t) {
int i,j,k;
/*
putchar('\n');
for(i=1;i&lt;=*t;i++) printf("%d: r%d c%d\t",i, cir.r,cir.c);
4 A$ W4 V/ W* y" h. v putchar('\n');
*/
5 O- M0 _" b' a4 e# Y) W$ E. H if((*t)!=1&amp;&amp;cir[(*t)].r==cir[1].r&amp;&amp;cir[*t].c==cir[1].c) {
* H! @8 V0 H$ h6 P/ I' p1 S% ?  t--;
  return 1;
' e/ }0 `: F, A6 b2 j, o! z; h }
if(dir!=down) {
  k=0;
  for(i=cir[*t].r-1;i&gt;=1;i--)
  r( s6 M9 H) t2 W# F) J$ q8 U4 w   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;
4 Y! a2 F$ G1 x' `* d8 K  if(k==1) {
5 H* r% Q- z& y. O: y   if(dir==up) cir[*t].value=0;
9 B0 ~$ ]* E" @" v: w4 Y" e   else cir[*t].value=1;
   (*t)++;
. }) `) V0 j* ?8 D" @   cir[*t].r=i;
   cir[*t].c=cir[(*t)-1].c;
4 S, L0 j6 I( Y2 l   if(circle(up,cir,t)) return 1;
+ t: c( |' A, d  }
}
if(dir!=up) {
  k=0;
  for(i=cir[*t].r+1;i&lt;=num_a;i++)
( q9 m; k& F  Z   if(pbase[cir[*t].c]==1||(i==cir[1].r&amp;&amp;cir[*t].c==cir[1].c)) {k=1; break;}
9 i& y% g1 I: }8 U  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) {
- ]/ y4 |, V" t, Y* ?- h   if(dir==down) cir[*t].value=0;
   else cir[*t].value=1;
$ M" X$ {- r: F/ e) Z   (*t)++;
5 k# C4 e# ^# \, @8 U! n8 b3 p   cir[*t].r=i;
' E9 V6 L8 J7 U8 H5 O& o* Q1 \) T   cir[*t].c=cir[(*t)-1].c;
) R5 E- Z/ N/ ^2 [- g/ U( f3 O   if(circle(down,cir,t)) return 1;
  }
! @+ p) n$ o8 Q) G: u3 M7 I }
if(dir!=right) {
  k=0;
  for(i=cir[*t].c-1;i&gt;=1;i--)
. S6 r+ x5 \) 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;
  if(k==1) {
9 K" ~! a) S" @7 `  I# w, ?   if(dir==left) cir[*t].value=0;
   else cir[*t].value=1;
5 E! v9 p# q5 u. E1 \6 H   (*t)++;
   cir[*t].r=cir[(*t)-1].r;
7 T  ~7 [+ ]6 ]% Z  p7 D   cir[*t].c=i;
* I6 M5 u+ k8 V6 m. B   if(circle(left,cir,t)) return 1;
+ N- L) T; S0 g6 `  }
}
if(dir!=left) {
" C- n0 K1 u) U! |- g  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;
1 m* H7 B( d( V+ F  f/ n  if(k==1) {
- N- a4 H1 {, w% V% }   if(dir==right) cir[*t].value=0;
: s) W6 s! }5 a  v& I0 k& h   else cir[*t].value=1;
   (*t)++;
4 u! X& f; x3 a2 ]" R3 }   cir[*t].r=cir[(*t)-1].r;
   cir[*t].c=i;
   if(circle(right,cir,t)) return 1;
  }
}
- {3 H- |: N# {" `( B( y# V (*t)--;
- i- l% s1 U9 z  G; d return 0;
) d1 v: }; @) s& R}</P>
<>void improve() {
int i,j,k,t;
! Z+ X: q0 s' b5 J* C struct element base_in,base_out,cir[2*MAX+1];</P>
$ @& Q7 i" o! i8 C5 l<> for(i=1;i&lt;=num_a;i++) pu=0;
8 J; e0 c' s( L+ }, M for(i=1;i&lt;=num_b;i++) pv=0;
% O$ n3 ^( `+ q) R) B5 c7 E! M( V u[1]=0; pu[1]=1;
; J9 x: \, K" k' C5 ~. N computeuv();
/ x$ V( e  E+ @6 P* b, ]1 Z 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;
: m/ h- ?( R  p: p1 M5 u0 V base_in.c=j;
base_in.value=base[j];</P>
# y2 K3 C9 H4 ]* N<> 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;
' q5 p- {) Q% x    base_in.c=j;
  {9 w0 ^3 P% G4 t' e3 O) {4 ?    base_in.value=base[j];
   }</P>
8 M4 a  u! G+ v% t" I, V, }<> t=1;
cir[t].r=base_in.r;
3 [+ N) y* w6 h$ k2 Q9 R7 T cir[t].c=base_in.c;
cir[t].value=1;
if(!circle(mid,cir,&amp;t)) {
  printf("程序出错！按回车结束");
  getchar();
  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);
// putchar('\n');</P>
' d3 X* v0 R/ q<> for(i=2;i&lt;=t;i++) if(cir.value==1) break;
base_out=cir;
base_out.value=base[cir.r][cir.c];
* x$ R' {- l' V" C0 @, E k=1;
4 T+ f/ ~3 f( ]8 m* 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) {
7 J" e" e% y" }) k+ A9 Z   base_out=cir;
6 e* c& ]# o3 Y   base_out.value=base[cir.r][cir.c];
   k++;
  }
4 B( M$ A5 t+ l& @/ R  else if(cir.value==1) k++;
4 }1 s& f% ]3 I1 q base[cir[1].r][cir[1].c]=0;
k=1;
$ c& G+ F& Q, U: }6 h4 x  G$ U1 m for(i=1;i&lt;=t;i++) {
  if(k%2==1&amp;&amp;cir.value==1) {
   base[cir.r][cir.c]+=base_out.value;
+ Z7 Z3 O5 s- C8 E" E$ J0 r   k++;
  }
" b8 [: p( {5 x  Q/ T2 X4 c( V  else if(k%2==0&amp;&amp;cir.value==1) {
# J; f+ h- z; w# _# f' d   base[cir.r][cir.c]-=base_out.value;
   k++;
9 F: V$ J3 Q! f5 u! S# c/ C. T  }
8 ~5 a: n9 r$ B6 G4 Y }
pbase[base_out.r][base_out.c]=0;
pbase[base_in.r][base_in.c]=1;</P>
<> improve();
}</P>
<>void output() {
' \* }& V$ }" P" T$ o3 x int i,j;
4 q" I" t7 Z: u* i double sum=0;
% C$ e; k; j; b' K) l/ R6 W. [ printf("\n运量为：\n");
for(i=1;i&lt;=num_a;i++) {
  putchar(' ');
5 k. E  B, K! |: y. t) `! S0 d  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==1) {
; R) Y% x+ `# o( o# t8 Y    printf("A%d-&gt;B%d:%lg\t",i,j,base[j]);
    sum+=base[j]*ab[j];
6 E4 G3 j% a4 f: l/ |9 N   }
# @+ ^1 J7 L: M" o+ G   else printf("A%d-&gt;B%d:0\t",i,j);
0 E# {0 N, Y1 ?2 {* h0 x  putchar('\n');
, I' ]( @$ k, g8 s; D }
2 M% f7 B4 W& z& g. c7 E# |- n8 T6 v% i printf("\n最低总运费为：%lg\n",sum);
}
</P>

liunengwu

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

hzlhm

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

enrique08

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

zhongguohelin

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