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

plgatc

<>/*************************************************************************
                         表上作业法解运输问题        
& Q9 s& r7 c1 a; w
, B/ a! `0 `  W- r1 _9 j1 K 编程环境：VC++6.0     
# J, G4 R$ E% K% N8 N 程序说明：
Vogel法求初始解，位势法检验是否最优，递归搜索闭回路改进解。
*************************************************************************/
#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;</P>
6 S% A+ E" Y# D+ y) c<>#define MAX 100
#define M 999999</P>
+ h8 O' G' M  v& _9 C9 O$ o<>int status; //1唯一最优解，-1无穷多最优解</P>
+ p2 Z. K8 a) `& E8 j" }<>int num_a,num_b;
5 z* y7 ?) r6 y4 ~( |double a[MAX],b[MAX],temp_a[MAX],temp_b[MAX];
double u[MAX],v[MAX],pu[MAX],pv[MAX];
* Q, S+ \$ h+ M# `- _6 C1 ?3 r4 }& {8 hdouble ab[MAX][MAX],temp_ab[MAX][MAX];
double base[MAX][MAX];
int pbase[MAX][MAX];
6 e& V: ~) R  [7 [9 xstruct element {
int r;
int c;
8 E0 H" U- Z8 F/ t- U, O( W double value;
};
, h1 Q( s) g6 [# U% Tenum direction {mid,up,down,left,right};</P>
<>void create();
6 p% k/ L3 x* W( i2 U' m! p2 jvoid banner();
7 k4 W4 |# a1 d9 b6 Mdouble dabs(double d);
void findinit();
void computeuv();
int check();
+ i  `5 r) X  Q$ p2 ~int  circle(enum direction dir,struct element cir[],int *t);
/ L* n' R1 }) S! ]6 m) lvoid improve();
1 f# E8 c& E0 c1 D! a& ?+ xvoid output();</P>
<>void main() {
; d1 j% Y% E6 r5 w( I* S  _5 p banner();
* b3 O! y8 A( V3 C3 _- G create();
printf("\n按回车确认后开始求解");
getchar();
getchar();
findinit();
3 f) H* T) ^% g# s' I3 ~1 d+ ? improve();
( @: _! U( ]9 ]0 E; u1 v switch(status) {
! v! k- W  f/ {5 u3 d  b/ | case 1:
  output();
9 W. ]/ ~, N' y* Z  puts("\n原问题有唯一最优解。\n");
  puts("\n按回车结束");
  getchar();
, A) k) K$ Z" {  exit(0);
4 v& B, g: ^$ X. N4 a/ K4 @; d7 v case -1:
. }7 X/ Q. |3 S) u5 m" ~- J* o  output();
$ _9 z! X, ]8 [$ G5 ?$ J  puts("\n原问题有无穷多最优解。\n");
  puts("\n按回车结束");
+ V  f  {  z" l  getchar();
& ~% v2 l7 H" Z9 E. x- J5 s  exit(0);
}
}</P>
<>void banner() {
# O* U9 ~# ^( v$ R% J6 _- m printf("\t\t****************************************\n");
printf("\t\t         表上作业法解运输问题\n");
printf("\t\t                              Thunder\n");
printf("\t\t****************************************\n");
printf("\n");
}</P>
+ Y: X: F1 B: i# h; j( Z<>void create() {
, C5 ~9 \/ I6 {) ^  j& g int i,j;
. w: V* y, s1 x( |+ h, r double sum_a,sum_b;
char confirm;
# z2 N% v) p( h& Z( y3 V7 Q while(1) {
3 _% R0 C6 f+ D  printf("请输入产地个数：");
4 k! k1 d. R1 ~; |: \! O8 y: N: P7 e  scanf("%d",&amp;num_a);
  for(i=1;i&lt;=num_a;i++) {
   printf("A%d产量：",i);
# o$ B* L# ~- H   scanf("%lf",&amp;a);
  }
, j  r) k$ [/ X% c' f  for(i=1;i&lt;=num_a;i++) printf("A%d产量：%lg\t",i,a);
- F* k* y% f% }; R, }% @* d9 @( l  printf("\n正确吗？：(y/n)");
: j9 ^1 d' L% z! U  getchar();
  confirm=getchar();
  if (confirm=='y') break;
  else if(confirm=='n') continue;
}
) U: x3 q) G* V4 E6 v while(1) {
. C' d6 F' x+ a  A+ L0 w7 o8 k  printf("\n请输入销地个数：");
- {- |% \3 d: \! E3 \3 a3 L  scanf("%d",&amp;num_b);
2 `, J+ q1 o7 D( T  for(i=1;i&lt;=num_b;i++) {
" m+ g1 s# o7 `" E- U   printf("B%d销量：",i);
( ~, T2 X4 |# C) i5 f   scanf("%lf",&amp;b);
: v! p2 Q( s: r# i; x2 I  }
; l. O" h# v# ~9 w% i( }. K& s: z  for(i=1;i&lt;=num_b;i++) printf("B%d销量：%lg\t",i,b);
  printf("\n正确吗？：(y/n)");
  getchar();
  confirm=getchar();
0 z6 v' u# C; }9 g  ^+ K7 Y  if (confirm=='y') break;
( c7 D: T3 ~1 A, o% x, f  c4 s  else if(confirm=='n') continue;
}
$ l, n5 r& P4 d6 L  p, u# A1 E9 B putchar('\n');
8 ]4 o1 }" J6 G! X" J for(i=1;i&lt;=num_a;i++) {
7 p% B/ V& ^% n* V" `8 ~; n  for(j=1;j&lt;=num_b;j++) {
2 |0 e0 V" {+ B/ _3 _; [& ~   printf("A%d到B%d运价：",i,j);
   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');
}
& N. A) M3 k) k: |9 L( U //处理产销不平衡的情况
sum_a=sum_b=0;
, Y% F/ ]+ W7 h& N3 {3 v2 } for(i=1;i&lt;=num_a;i++) sum_a+=a;
* X6 y4 u; \$ H for(i=1;i&lt;=num_b;i++) sum_b+=b;</P>
; H$ R) W8 i3 V<> printf("总产量：%lg\t总销量：%lg",sum_a,sum_b);
* g+ f% T& x6 w$ `9 M if(sum_a==sum_b) printf("\t产销平衡。");
else if(sum_a&gt;sum_b) {
9 V! O% m$ p* H' x  printf("\t供大于求，增加假想销地B%d。\n",++num_b);
1 g  r7 z  f: p$ \; d) o  b[num_b]=sum_a-sum_b;
/ f' o# I+ o% t6 S* e  r: \7 ^  for(i=1;i&lt;=num_a;i++) ab[num_b]=0;
# P  B5 J0 }' ~# J6 `( k- {. Z5 i }
else if(sum_a&lt;sum_b){
, p5 ?2 |) y( U1 P  printf("\t供不应求，增加假想产地A%d。\n",++num_a);
  a[num_a]=sum_b-sum_a;
  for(i=1;i&lt;=num_b;i++) ab[num_a]=0;
}
) D' G. u- J5 [3 V //求解前的准备
for(i=1;i&lt;=num_a;i++)
  for(j=1;j&lt;=num_b;j++)
" V0 T9 R) n/ k6 {   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;
' m! @- K1 }) B3 K for(i=1;i&lt;=num_a;i++)
' D$ {/ R7 F" m: E9 N& C, _' s for(j=1;j&lt;=num_b;j++) temp_ab[j]=ab[j];
//回显问题
+ |) M/ _* L4 P+ z4 k printf("\n\n原问题为：\n\n");
* V) x) D! ^# H2 J   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);
8 B* w6 @$ B5 a1 D8 B: m  X& s printf("\n运价为：\n");
1 l/ F$ X6 Y# I for(i=1;i&lt;=num_a;i++) {
" Y/ r: X$ R+ Z9 y; z  putchar(' ');
  for(j=1;j&lt;=num_b;j++)
   printf("A%d-&gt;B%d:%lg\t",i,j,ab[j]);
, S1 u, C" g/ c, @6 I7 c" [  putchar('\n');
+ s" k5 Z; `- a# q) i! h! ^& Z& t }
}</P>
<>double dabs(double d) {
if(d&gt;=0) return d;
else return -d;
  F% H: D8 M$ u0 o3 B5 ?}</P>
<>void findinit() {
int i,j,k;
: ]& B! |3 S' o0 r double r_penum[MAX],c_penum[MAX];
& {" f, a/ B# [; K0 Z  u struct largest {
  char rc;
" F. e+ L$ J/ y  int num;
  double value;
' @. C2 b5 L  f2 z' J9 }& D! |/ U };
struct largest lar1,lar2;
# U, d% Q5 S1 L. J! T; H  C int r=0,c=0;
double a1,a2,b1,b2,temp;</P>
<> for(i=1;i&lt;=num_a;i++) {
% y! H7 ]5 {2 q& G; U4 Q) o& F  temp=temp_ab[1];
  for(j=1;j&lt;=num_b;j++)
  @1 f) w2 b: U4 E/ i, M/ Y+ @   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
  a5 S* R/ u  `+ h2 [- O' `  a1=a2=temp;
  for(j=1;j&lt;=num_b;j++)
   if(temp_ab[j]&lt;=a1) {
: E! A3 Y8 D: I    a2=a1;
    a1=temp_ab[j];
   }
! r! Z( u2 i8 `% J   else if(temp_ab[j]&lt;=a2) a2=temp_ab[j];
$ _& S( j- }7 S8 @3 `0 t8 Z  r_penum=dabs(a1-a2);
4 n3 x3 ]' B6 D+ B }</P>
<> for(i=1;i&lt;=num_b;i++) {
7 z. ]& A+ }5 U  l! q4 B2 r8 y  temp=temp_ab[1];
4 T' n5 B- O1 j+ i0 H0 a  for(j=1;j&lt;=num_a;j++)
   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
  b1=b2=temp;
4 c/ }7 R: t; a" L  for(j=1;j&lt;=num_a;j++)  
5 y& K0 ]# Q  D' U. Z- M' v   if(temp_ab[j]&lt;=b1) {
    b2=b1;
! H- U+ f% ?5 T7 r4 }3 X/ x    b1=temp_ab[j];
   }
( Z) r) \3 y$ Y. [  P4 [! }   else if(temp_ab[j]&lt;=b2) b2=temp_ab[j];
" L0 E& o/ ~0 E9 K4 @% b  c_penum=dabs(b1-b2);
9 S, \  ^0 f, c- x }
0 N9 K; i* I/ M9 M: I /*
for(i=1;i&lt;=num_a;i++) printf("pa%d=%lg ",i,r_penum);
! f! t4 D- V8 j+ ?0 S7 U putchar('\n');
for(i=1;i&lt;=num_b;i++) printf("pb%d=%lg ",i,c_penum);
: h) M0 c  s9 r9 m# K/ {: g6 h */
temp=r_penum[1];
$ }/ Y6 N2 E* b 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>
<> //考虑了有两个罚数相等的情况，大于两个相等只取其中两个进行比较
: ]1 h1 T. \  M2 ]& n. G lar1.value=lar2.value=temp;
+ W' H- w5 m- [6 I( S lar1.num=lar2.num=1;
lar1.rc=lar2.rc='r';
for(i=1;i&lt;=num_a;i++)
  if(r_penum&gt;=lar1.value) {
" W6 D* }1 T9 w2 W& Q! e0 E   lar2=lar1;
( X, K  [  \8 |* V   lar1.rc='r';
   lar1.num=i;
! c$ x# o) c7 }* J2 j, c8 ~* y   lar1.value=r_penum;
  }
0 M& [7 i1 P+ u) S1 K* ~# n' K  else if(r_penum&gt;=lar2.value) {
6 M0 F4 F* [1 M, Q   lar2.rc='r';
1 g  t$ O% z8 S! j, c+ K! s   lar2.num=i;
   lar2.value=r_penum;
1 b- Q( N( ?3 @7 j% b% g  }</P>
<> for(i=1;i&lt;=num_b;i++)
  if(c_penum&gt;=lar1.value) {
( Z6 h" a% E. N8 `4 q   lar2=lar1;
   lar1.rc='c';
   lar1.num=i;
   lar1.value=c_penum;
) b" h0 A" f$ j" I  }
  else if(c_penum&gt;=lar2.value) {
. [# {; |; V' y% M0 a   lar2.rc='c';
3 K. n0 E5 B% }   lar2.num=i;
   lar2.value=c_penum;
3 o6 I0 Y8 a) k0 J( V  }</P>
5 _1 S$ z7 H4 |4 f7 c<> if(lar1.value==lar2.value&amp;&amp;(lar1.num!=lar2.num||lar1.rc!=lar2.rc)) {
, U9 W! D9 y+ o  if(lar1.rc=='r'&amp;&amp;lar2.rc=='r') {
! K9 l; X' |5 U0 C. p: \! {   temp=temp_ab[lar1.num][1];
0 _0 p6 t9 x) ]; }6 @& \   r=lar1.num;
/ H' r4 ~9 E& a# G$ V; F+ ~      c=1;
) I( I+ f! u+ L" K$ J   for(i=1;i&lt;=num_b;i++) {
1 b- q8 X5 J; v7 V( [! G% X    if(temp_ab[lar1.num]&lt;temp) {
     temp=temp_ab[lar1.num];
     r=lar1.num;
1 E, H9 W# e1 H2 _1 w# x0 ]+ S     c=i;
    }
+ ~# r, S0 A* f+ Z    if(temp_ab[lar2.num]&lt;temp) {
; k" Z4 z2 R* i) f9 [, |     temp=temp_ab[lar2.num];
     r=lar2.num;
     c=i;
/ i9 ~7 L! v2 M% D' G1 q  S$ y    }
% R$ B8 F: x2 A9 V! I   }
0 S/ h; s/ ~4 A: |; S$ |! ^  }
1 l1 }2 W% Q. s6 ]. B0 N- G' Y  if(lar1.rc=='c'&amp;&amp;lar2.rc=='c') {
7 p% M( M$ l  ?" T+ S( @! q   temp=temp_ab[1][lar1.num];
3 t- j8 t& x; d2 V) L5 g5 D   r=1;
      c=lar1.num;
   for(i=1;i&lt;=num_a-1;i++) {
    if(temp_ab[lar1.num]&lt;temp) {
! B3 i4 I7 d) ]  ~( _     temp=temp_ab[lar1.num];
     c=lar1.num;
* \; o" P: W; m! B2 S7 K% h8 `* p' [2 Q     r=i;
1 B( }: c0 U2 T$ ~    }
+ E  T& `1 ]* I: Z1 R* W' G1 z    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
     c=lar2.num;
4 S9 ^7 `: w) S7 z& Y& O1 Z8 N     r=i;
7 z4 r- s, y. H5 Q8 ^6 K: R    }
3 k- o7 s" x3 h   }
! P) l; \. d$ p& m  }
  if(lar1.rc=='r'&amp;&amp;lar2.rc=='c') {
4 j8 w0 r! Q, \" L: T- w   temp=temp_ab[lar1.num][1];
   r=lar1.num;
      c=1;
# f1 j+ f0 M( Q6 x; x9 S   for(i=1;i&lt;=num_b;i++)
3 R7 a3 d  _. Y  o. M6 {    if(temp_ab[lar1.num]&lt;temp) {
     temp=temp_ab[lar1.num];
3 ]) ^4 t- ?5 N1 r; o" b; \     r=lar1.num;
8 d5 R) _6 l$ y7 Q0 s     c=i;
/ b; H& ^# G3 ~. b/ I% [    }
  V& c# T0 i! Z8 w! U  z2 m+ ^0 W   for(i=1;i&lt;=num_a;i++)
    if(temp_ab[lar2.num]&lt;temp) {
1 A8 E; m; k" b! n7 g     temp=temp_ab[lar2.num];
5 R0 t! N( @; \! ^1 h     c=lar2.num;
$ d3 }6 B, }1 ?  U     r=i;
/ D6 P2 x' `6 j( Z0 q) F    }
" I, V* @# {( x6 U! k  }
  if(lar1.rc=='c'&amp;&amp;lar2.rc=='r') {
9 h6 B  E9 r9 ]. X1 T   temp=temp_ab[1][lar1.num];
   r=1;
% Z- C9 J1 q" v5 u" f      c=lar1.num;
   for(i=1;i&lt;=num_b;i++)
& H' h  E; T9 `    if(temp_ab[lar2.num]&lt;temp) {
! U! H2 a0 r" d- i% I     temp=temp_ab[lar2.num];
" C( x7 ~. M8 c3 ?* g     r=lar2.num;
' D, {, x& W4 X- p( D5 g     c=i;
4 J3 y. C) ?* Q; f8 Y0 {$ A    }
8 p6 r4 ?# x& q+ D   for(i=1;i&lt;=num_a;i++)
) t, s: f/ ^0 u! p- }1 Q    if(temp_ab[lar1.num]&lt;temp) {
& J' e1 c# }* Y% F6 j     temp=temp_ab[lar1.num];
     c=lar1.num;
     r=i;
    }
; I* Y2 c- L9 D* L$ G6 {  }
" o6 M; O$ J3 p9 q! l }
else {
  if(lar1.rc=='r') {
' A/ ^3 b7 @9 g' b$ {5 c* `   r=lar1.num;
3 T) d  U1 X  l. h   c=1;
   temp=temp_ab[lar1.num][1];
   for(i=1;i&lt;=num_b;i++)
    if(temp_ab[lar1.num]&lt;temp) {
     c=i;
     temp=temp_ab[lar1.num];
    }
  }
' r+ f8 y& L) {( Q! {3 n/ Y  else {
% R, c3 f4 v* E+ ?% W1 B* P9 U   r=1;
   c=lar1.num;
   temp=temp_ab[1][lar1.num];
6 ^5 I) d% V9 i9 D; G+ a3 [  ?& D: W/ P   for(i=1;i&lt;=num_a;i++)
    if(temp_ab[lar1.num]&lt;temp) {
     r=i;
     temp=temp_ab[lar1.num];
  ^7 Q0 A! R! r8 l; N4 Y9 r4 S2 P    }
& J7 b( V- f8 L7 D# A. M  }
- m9 M+ G- u4 y& Y }
pbase[r][c]=1;
6 ~+ E; Z, c' X) h0 ^. i" x if(temp_a[r]&gt;temp_b[c]) {
: ~1 f$ y( t0 \$ m) y; [, v  base[r][c]=temp_b[c];
  temp_a[r]=temp_a[r]-temp_b[c];
5 v9 F. K4 j, }3 i' ^$ O  temp_b[c]=0;
  V6 ^9 c1 c( ~( j& k+ e6 ~' u  for(i=1;i&lt;=num_a;i++) temp_ab[c]=M;
}
  P- O4 Y$ B+ R# u4 L8 z* E( S else if(temp_a[r]&lt;temp_b[c]) {
  base[r][c]=temp_a[r];
: V) G8 Q5 Y+ W6 Z( G  u  temp_b[c]=temp_b[c]-temp_a[r];
0 _; O/ ]' e+ O4 L  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];
  temp_a[r]=temp_b[c]=0;
7 V% B* V$ k0 [3 I- n  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;
* T. b8 s/ p2 P( T; Q1 Y, H& |  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) {
1 t) e' @/ L0 |) e. c   k=0;
+ H# O5 f" ?2 p# N5 p   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 R+ U6 F4 l2 W& H% r. }. Y; C6 t 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) return;
findinit();
) x2 P* T/ j6 V* [}</P>
<>void computeuv() {
- L0 Z: _. ?1 {  P/ ~& ]+ ] int i,j,k;
# |9 Y( W0 B; ^- ^' j- J- L for(i=1;i&lt;=num_a;i++)
  for(j=1;j&lt;=num_b;j++)
3 o8 g- o3 R' i0 z: a  Z3 h' ]) q   if(pbase[j]==1) {
2 q* G7 m! y  S  [* \    if(pu==1) {v[j]=ab[j]-u; pv[j]=1;}
    if(pv[j]==1) {u=ab[j]-v[j]; pu=1;}
   }
9 Q6 E+ M7 q& J8 Z" T k=0;
' U8 l2 \+ }( ]2 P9 H7 y 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;
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];
& @% N. Z' w+ q) Y/ j; _8 g7 O    if(base[j]&lt;0) k=1;
    else if(base[j]==0) l=1;
   }
, \; q' P* B0 Q/ v$ i) L3 q3 x/* for(i=1;i&lt;=num_a;i++){
& O8 \; ~5 `" a3 A# B' u4 u; o  for(j=1;j&lt;=num_b;j++) printf("base %lg\t",base[j]);
  putchar('\n');}
0 D3 T- E8 L( t8 n3 z4 H- n for(i=1;i&lt;=num_a;i++){
* p* h% A. L0 K  G. W: g) K& `  for(j=1;j&lt;=num_b;j++) printf("pbase %d\t",pbase[j]);
, `: i  D5 L. ^! O5 x: U8 b4 v+ D* |  putchar('\n');}
: H4 r3 b5 ?) F/ W/ s( y' u: h*/
if(k==0&amp;&amp;l==0) {status=1; return 1;}
. p+ e6 o: t, u$ s' B3 Q( s& l6 v else if(k==0&amp;&amp;l!=0) {status=-1; return 1;}
6 o# i5 ]' O3 c# M1 u3 i else return 0;
: x2 m( n5 i( x& u- M}</P>
1 W! O2 U9 U: H2 @) Z3 G0 H<>int circle(enum direction dir,struct element cir[],int *t) {
0 F: F" j4 M: T! Y2 ` int i,j,k;
% W  Q  B8 k4 Z1 i( \4 Q /*
4 {# w& `  q, F/ E5 t6 _& T) D* [ 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) {
+ O! B4 g* [1 K1 V% R  t--;
  return 1;
}
if(dir!=down) {
  k=0;
  for(i=cir[*t].r-1;i&gt;=1;i--)
+ y3 h4 \9 B% M1 w7 {   if(pbase[cir[*t].c]==1||(i==cir[1].r&amp;&amp;cir[*t].c==cir[1].c)) {k=1; break;}
* n) L( b6 A; Q1 {  for(j=2;j&lt;=*t;j++) if(i==cir[j].r&amp;&amp;cir[*t].c==cir[j].c) k=0;
0 T" y' ^6 A4 ?2 h% o% n' G  H  if(k==1) {
   if(dir==up) cir[*t].value=0;
, k, C" O' H! r! @( Y   else cir[*t].value=1;
( V( o' Z6 n( A0 b5 ~8 Q# }   (*t)++;
( I- |& J& G. C9 U4 l1 I   cir[*t].r=i;
   cir[*t].c=cir[(*t)-1].c;
( e7 k8 \7 i" d9 R   if(circle(up,cir,t)) return 1;
  }
0 C1 M4 H( g- C, i( m9 Q, ]* X }
9 r( ]  g5 ]1 X, {  W if(dir!=up) {
  k=0;
  for(i=cir[*t].r+1;i&lt;=num_a;i++)
8 @% B/ a0 M" y   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;
, a6 o# r  r+ y. v& {* H4 o  if(k==1) {
   if(dir==down) cir[*t].value=0;
   else cir[*t].value=1;
   (*t)++;
1 i2 X; o7 A+ f/ r, j% X   cir[*t].r=i;
- @2 U% u. G: ?& h, r- z5 r: n   cir[*t].c=cir[(*t)-1].c;
1 a, U! s; x5 D9 ^. W; i1 V! F   if(circle(down,cir,t)) return 1;
* n) [; g; q# j" n: F% A" S2 b  }
  n, D; T$ X5 F. Y- `- h }
if(dir!=right) {
% R7 F3 z8 E5 Z/ a  k=0;
8 o  E. C1 Y0 z* ?5 @  for(i=cir[*t].c-1;i&gt;=1;i--)
& v! Z3 K0 k( M, P" N, s" v" @   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;
. _% q; g/ A5 S' e% d( v  if(k==1) {
* S7 y9 E/ \0 K1 |/ @' {( N6 @7 R   if(dir==left) cir[*t].value=0;
$ ~2 \5 z7 ?$ h- I0 I1 V; J: p& T   else cir[*t].value=1;
3 }* g4 j/ l9 A7 l/ f2 w* V   (*t)++;
   cir[*t].r=cir[(*t)-1].r;
; c  U& ]5 H/ v+ V, L/ T! ^   cir[*t].c=i;
3 w; j) r3 S- ^. V7 [/ ]. M   if(circle(left,cir,t)) return 1;
% X5 n: J1 A/ _" _; f+ {8 N  }
}
& X) `/ Z" o) J* G if(dir!=left) {
  k=0;
4 x7 `* }# s  f  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;
3 g; e9 o3 }; Y8 V" |  if(k==1) {
: g( w  b! g% l$ Y/ @   if(dir==right) cir[*t].value=0;
( ]% \+ F& ]3 X8 W% J   else cir[*t].value=1;
4 e$ x1 l; I& [0 Z   (*t)++;
   cir[*t].r=cir[(*t)-1].r;
   cir[*t].c=i;
; a9 m1 E& A& f* A! O) ~   if(circle(right,cir,t)) return 1;
8 M! W$ N+ ^! e. N  }
- J* O; w( x! j, ]; j  |+ j7 q) ? }
6 K% V* f( O. h1 e (*t)--;
0 U$ N9 K4 G. Y return 0;
. i9 `. R5 L- E3 }}</P>
# L5 ]8 `2 S; J5 ]% M4 N- V- e<>void improve() {
int i,j,k,t;
8 {$ x4 b9 P1 \+ \/ p 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;
2 _6 ?& k9 g4 Y- b! l# u3 m computeuv();
if(check()) return;
( @0 ?# r* ~4 J for(i=1;i&lt;=num_a;i++)
+ [5 t1 d! J/ U  for(j=1;j&lt;=num_b;j++)
6 h/ X; ]6 e* [& X' |( a   if(pbase[j]==0) break;
# }8 i1 L2 U4 ~) K. r4 q base_in.r=i;
base_in.c=j;
' |2 Z2 g+ O; Z3 s5 e base_in.value=base[j];</P>
<> for(i=1;i&lt;=num_a;i++)
  for(j=1;j&lt;=num_b;j++)
2 \0 x& I  {$ X8 U5 p4 `2 ^1 d8 b   if(pbase[j]==0&amp;&amp;base[j]&lt;base_in.value) {
6 t* H# _1 g7 q$ t( k    base_in.r=i;
" N/ z/ ~- V, E8 u    base_in.c=j;
    base_in.value=base[j];
   }</P>
<> t=1;
+ b& T1 T7 g8 o5 I7 C% ^$ C7 f cir[t].r=base_in.r;
cir[t].c=base_in.c;
5 l2 P% Q0 A, |8 p+ K" q& `- B cir[t].value=1;
if(!circle(mid,cir,&amp;t)) {
; ?  |& J5 @& l5 A) x# \  printf("程序出错！按回车结束");
  getchar();
  exit(0);
}
, a$ u2 o5 c8 Z% l5 \3 ` 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>
<> for(i=2;i&lt;=t;i++) if(cir.value==1) break;
base_out=cir;
base_out.value=base[cir.r][cir.c];
" @: H, u- g! Z0 f k=1;
for(i=1;i&lt;=t;i++)
  v" ^  f$ v$ ^  G7 p7 d# P  if(k%2==0&amp;&amp;cir.value==1&amp;&amp;base[cir.r][cir.c]&lt;base_out.value) {
0 O  i0 [, D7 @: l" p& s   base_out=cir;
   base_out.value=base[cir.r][cir.c];
   k++;
" U+ N/ }" g6 g# E. O7 S  }
  else if(cir.value==1) k++;
$ X! S" M! E' Y) x" Y) C' ] base[cir[1].r][cir[1].c]=0;
1 J3 X; x  U+ ~) |8 s k=1;
for(i=1;i&lt;=t;i++) {
  if(k%2==1&amp;&amp;cir.value==1) {
* W# i, n4 c; b6 R- L, o/ ^8 s9 E   base[cir.r][cir.c]+=base_out.value;
   k++;
9 F, g! S, I, C( k  }
3 a. `6 j' @0 q3 V5 m2 X0 T& q  else if(k%2==0&amp;&amp;cir.value==1) {
4 G# }. T! e. a5 s1 H   base[cir.r][cir.c]-=base_out.value;
   k++;
  }
0 g$ a( x% w: _5 q% w* b  ~ }
* F; K, o' N, z! n; W  n8 @% h pbase[base_out.r][base_out.c]=0;
0 B; O- Q! t1 c; N1 }; q pbase[base_in.r][base_in.c]=1;</P>
<> improve();
}</P>
<>void output() {
2 h+ |) H% _+ d0 @0 |  E int i,j;
double sum=0;
printf("\n运量为：\n");
for(i=1;i&lt;=num_a;i++) {
  putchar(' ');
  for(j=1;j&lt;=num_b;j++)
4 P, l5 l: c- ~& s9 }   if(pbase[j]==1) {
    printf("A%d-&gt;B%d:%lg\t",i,j,base[j]);
    sum+=base[j]*ab[j];
   }
   else printf("A%d-&gt;B%d:0\t",i,j);
: f  l$ Z) U9 G: f  putchar('\n');
. N/ c, k3 m* R1 r3 x; V }
0 n# Z8 Q- ]( X printf("\n最低总运费为：%lg\n",sum);
. v( S( v& C/ b% {( z. ~7 c}
7 r$ I" ]! d6 f& ?8 x* ^. V- _# Z! }</P>

zhongguohelin

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

enrique08

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

hzlhm

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

liunengwu

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