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

plgatc

<>/*************************************************************************
8 K, T  d1 [. B4 K                         表上作业法解运输问题        

编程环境：VC++6.0     
程序说明：
Vogel法求初始解，位势法检验是否最优，递归搜索闭回路改进解。
*************************************************************************/
#include &lt;stdio.h&gt;
: L- B$ [" V, H#include &lt;stdlib.h&gt;</P>
; K* V' D$ E/ l; Z; ~3 v6 l<>#define MAX 100
1 h- B) j+ D2 }+ {: d  m% t#define M 999999</P>
<>int status; //1唯一最优解，-1无穷多最优解</P>
<>int num_a,num_b;
0 P1 m( X9 B  x8 b4 |# I  Ldouble a[MAX],b[MAX],temp_a[MAX],temp_b[MAX];
1 i* R& F3 A" Gdouble u[MAX],v[MAX],pu[MAX],pv[MAX];
) c4 U. L4 j* q, c) m6 Ydouble ab[MAX][MAX],temp_ab[MAX][MAX];
double base[MAX][MAX];
+ [  m8 \" p1 k# `  hint pbase[MAX][MAX];
- X7 K  B% Z& o1 U' N, f7 {8 Istruct element {
int r;
int c;
double value;
};
$ f2 ~6 |2 E' b8 C2 i, B* Q! senum direction {mid,up,down,left,right};</P>
<>void create();
void banner();
: u% O% ]( D# H0 N  Z( Hdouble dabs(double d);
( w3 C5 O; E. A# Q1 `void findinit();
void computeuv();
& B/ i7 M) U; I: ^& z8 d8 fint check();
int  circle(enum direction dir,struct element cir[],int *t);
void improve();
void output();</P>
+ }8 G5 h, \2 H6 @" ^5 f) Z* {<>void main() {
, }) B2 ^0 u3 t$ W. m1 S) N$ l/ E banner();
create();
$ V' R9 q  V' S% h4 U8 B; \ printf("\n按回车确认后开始求解");
getchar();
getchar();
findinit();
5 j! @# r9 v& V, U improve();
switch(status) {
case 1:
  output();
  puts("\n原问题有唯一最优解。\n");
( O+ Y- \9 O6 \: C$ d* L9 E& U  puts("\n按回车结束");
& a" L3 D0 N$ h1 O9 w  getchar();
" F8 i( w; n1 c2 o  exit(0);
) K4 c4 i1 N+ h! s4 M+ E0 g case -1:
% y1 l) }6 \: `  U  output();
3 R; z4 O/ [! j  puts("\n原问题有无穷多最优解。\n");
* i6 q, M: Z& K3 t. W  puts("\n按回车结束");
* W- x) c. |7 J! [  h  getchar();
  exit(0);
}
}</P>
7 t) M6 U& c1 q- G! h& D<>void banner() {
printf("\t\t****************************************\n");
' d, k! H4 B. E* S+ [+ x1 |5 `0 B- y printf("\t\t         表上作业法解运输问题\n");
& x1 n% g2 k7 X- k+ C, \) U. ~ printf("\t\t                              Thunder\n");
printf("\t\t****************************************\n");
; _! B; g, D/ ?- j printf("\n");
; s& i! h$ V4 R}</P>
3 b9 t# [  G# J6 V<>void create() {
& j0 A4 ]1 M- u4 W int i,j;
5 M- d4 P1 J* s+ t3 ?2 T double sum_a,sum_b;
char confirm;
while(1) {
9 v/ `' q  f- ]5 W/ V  printf("请输入产地个数：");
7 `6 N- W( }; j, D5 q% O  scanf("%d",&amp;num_a);
  for(i=1;i&lt;=num_a;i++) {
8 A' K: A- [. t1 c4 m1 `   printf("A%d产量：",i);
1 s! G, m* i, k1 e   scanf("%lf",&amp;a);
5 A8 j2 {  ?2 i4 C  }
, T1 `; ?8 M# c  for(i=1;i&lt;=num_a;i++) printf("A%d产量：%lg\t",i,a);
  printf("\n正确吗？：(y/n)");
9 z! u$ q0 C9 L& w% y  getchar();
/ K) F9 E2 A! @- Y: J. ^2 P/ \* V6 j  confirm=getchar();
  if (confirm=='y') break;
; Y0 D7 c" J0 o% K( U- ]  else if(confirm=='n') continue;
}
( S6 C/ L5 J8 W while(1) {
3 n- z$ J* m! j- @  printf("\n请输入销地个数：");
  scanf("%d",&amp;num_b);
1 A+ `! B, s- Y2 b3 c  for(i=1;i&lt;=num_b;i++) {
   printf("B%d销量：",i);
   scanf("%lf",&amp;b);
  }
! Y, }! N: y" ~  ~, R" \4 Z1 P  for(i=1;i&lt;=num_b;i++) printf("B%d销量：%lg\t",i,b);
  printf("\n正确吗？：(y/n)");
9 ?& }7 Z4 o9 M  getchar();
  confirm=getchar();
  if (confirm=='y') break;
  else if(confirm=='n') continue;
}
2 P) k5 L* S* \) F" u5 g, B  k putchar('\n');
; p9 X! M) B# ^ for(i=1;i&lt;=num_a;i++) {
7 V( i0 V" b# s. ?  for(j=1;j&lt;=num_b;j++) {
   printf("A%d到B%d运价：",i,j);
+ E. Z2 j6 G7 V4 w$ S" t   scanf("%lf",&amp;ab[j]);
  }
1 [7 S; B& T; s* {; `. n. Y  for(j=1;j&lt;=num_b;j++) printf("A%d到B%d：%lg\t",i,j,ab[j]);
  printf("\n正确吗？：(y/n)");
  z0 V+ c- L( r  getchar();
  confirm=getchar();
  if(confirm=='n') i--;
" }, v! H6 P' \% f* A  putchar('\n');
}
//处理产销不平衡的情况
0 L9 s& O4 A4 {; B+ x sum_a=sum_b=0;
' ^2 Z+ k/ }; j7 T for(i=1;i&lt;=num_a;i++) sum_a+=a;
4 B4 \8 E- B; a& h: ] for(i=1;i&lt;=num_b;i++) sum_b+=b;</P>
<> 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);
  b[num_b]=sum_a-sum_b;
  for(i=1;i&lt;=num_a;i++) ab[num_b]=0;
! n& A, m. h) y }
else if(sum_a&lt;sum_b){
  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;
8 i% o, O4 y: S6 M; N& U }
//求解前的准备
for(i=1;i&lt;=num_a;i++)
) [) [8 F) L- R0 c+ V5 f  for(j=1;j&lt;=num_b;j++)
   base[j]=pbase[j]=0;
$ M: a2 c* b: _. F5 Z0 ?6 k for(i=1;i&lt;=num_a;i++) temp_a=a;
8 h1 X! L- D, W: C+ h for(i=1;i&lt;=num_b;i++) temp_b=b;
for(i=1;i&lt;=num_a;i++)
- J1 A" m5 J* g. u for(j=1;j&lt;=num_b;j++) temp_ab[j]=ab[j];
//回显问题
0 M0 M( i& x2 z printf("\n\n原问题为：\n\n");
! Z2 [& P% ~: `' D* v  P9 `( h0 _4 N   printf("产量：\n ");
for(i=1;i&lt;=num_a;i++) printf("A%d:%lg\t",i,a);
/ n- t& y, S& V" y$ B& J printf("\n运量：\n ");
' ?3 Y  T& B/ k% h for(i=1;i&lt;=num_b;i++) printf("B%d:%lg\t",i,b);
1 Z3 I" P4 U2 z9 p  e& X printf("\n运价为：\n");
for(i=1;i&lt;=num_a;i++) {
5 B) h8 h" `& |) q$ e  putchar(' ');
7 l" r4 V6 U" s. W0 l) x  for(j=1;j&lt;=num_b;j++)
   printf("A%d-&gt;B%d:%lg\t",i,j,ab[j]);
6 L, o+ v1 Y' M8 y7 w1 {: C0 B; h  putchar('\n');
}
}</P>
<>double dabs(double d) {
if(d&gt;=0) return d;
else return -d;
}</P>
<>void findinit() {
int i,j,k;
double r_penum[MAX],c_penum[MAX];
struct largest {
) M2 P1 g% K" d  char rc;
! Y$ G+ O5 k; P2 p( m/ O3 {  int num;
1 N! f5 K+ N) G" N3 {- c  double value;
};
7 @1 m0 z. b+ o  o6 @! K/ Y$ g9 G struct largest lar1,lar2;
* _3 ?/ j1 k; v0 k1 c/ ^& n5 r int r=0,c=0;
! s0 r/ b! x6 [! Z8 x double a1,a2,b1,b2,temp;</P>
<> for(i=1;i&lt;=num_a;i++) {
  temp=temp_ab[1];
  for(j=1;j&lt;=num_b;j++)
0 t5 D; C% N/ B3 P, m. C1 c   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
6 j6 a  b9 q3 Y: K4 a. a  a1=a2=temp;
  for(j=1;j&lt;=num_b;j++)
   if(temp_ab[j]&lt;=a1) {
    a2=a1;
    a1=temp_ab[j];
   }
   else if(temp_ab[j]&lt;=a2) a2=temp_ab[j];
) n. G( _- i) ~) R  r_penum=dabs(a1-a2);
+ \$ P% T/ D' _( k! W# S }</P>
# d# W% L) p4 d5 V8 \<> for(i=1;i&lt;=num_b;i++) {
  temp=temp_ab[1];
# `; s) ^/ X) f% v6 M* g  for(j=1;j&lt;=num_a;j++)
- y6 I( k% F/ m# D" p/ L9 L" M   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
* ^2 n  g9 r- Y2 a  b1=b2=temp;
- P9 x! E# ]) W3 J% M' h  for(j=1;j&lt;=num_a;j++)  
$ P( r: G) T# ?- O   if(temp_ab[j]&lt;=b1) {
    b2=b1;
' u& W/ y( {* [% A) `    b1=temp_ab[j];
9 i: o1 d/ }* j   }
   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);
1 {, y* e/ c5 j) N putchar('\n');
  x- s$ H4 p: |( B. X 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;
9 q" ?" J, D) |8 w3 O6 B7 Z. S# y 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;
2 n6 D% X( _/ Z. w lar1.rc=lar2.rc='r';
for(i=1;i&lt;=num_a;i++)
  i: k% b6 ~& V* I  if(r_penum&gt;=lar1.value) {
   lar2=lar1;
   lar1.rc='r';
/ M! C) n6 s( m   lar1.num=i;
   lar1.value=r_penum;
' v; b( A3 }  L+ p9 Q- N5 \% o+ [  }
  else if(r_penum&gt;=lar2.value) {
   lar2.rc='r';
   lar2.num=i;
$ F9 j" R! m$ _1 h* E- i( x5 e: X   lar2.value=r_penum;
6 {" \/ I8 {2 y7 y/ q5 Z2 O4 `2 w- A  }</P>
<> for(i=1;i&lt;=num_b;i++)
/ V( E# e4 u7 E+ i' r  if(c_penum&gt;=lar1.value) {
, h9 ~8 g) {9 d   lar2=lar1;
   lar1.rc='c';
   lar1.num=i;
2 b( O6 a$ U  _$ u* Q   lar1.value=c_penum;
  }
* o/ `2 O' F$ }4 x: l: @5 c% Q9 C  else if(c_penum&gt;=lar2.value) {
   lar2.rc='c';
, ^2 ~9 s: E8 i9 s) [( y   lar2.num=i;
   lar2.value=c_penum;
  }</P>
<> if(lar1.value==lar2.value&amp;&amp;(lar1.num!=lar2.num||lar1.rc!=lar2.rc)) {
. J, Y0 `6 f! a! ?' U4 h1 R  if(lar1.rc=='r'&amp;&amp;lar2.rc=='r') {
   temp=temp_ab[lar1.num][1];
   r=lar1.num;
8 G( X8 B: f, J7 M, Y. S/ o      c=1;
2 R3 a" q5 B  m" b   for(i=1;i&lt;=num_b;i++) {
    if(temp_ab[lar1.num]&lt;temp) {
     temp=temp_ab[lar1.num];
     r=lar1.num;
! L& t" i$ ~% o2 e( _0 P+ j     c=i;
    }
    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
     r=lar2.num;
     c=i;
" X1 r% z# o5 c5 ]8 I4 u4 h' ]. p: u    }
   }
  }
  if(lar1.rc=='c'&amp;&amp;lar2.rc=='c') {
   temp=temp_ab[1][lar1.num];
( X) T. N9 w, i, y6 a5 P% O6 I( B   r=1;
  @2 ~4 _( o* x% ^0 T      c=lar1.num;
' y4 [* u3 Z& v6 Z- e2 Q6 b% w% W) X   for(i=1;i&lt;=num_a-1;i++) {
    if(temp_ab[lar1.num]&lt;temp) {
     temp=temp_ab[lar1.num];
1 A1 B5 `4 N* X6 E6 p     c=lar1.num;
. V# |7 s: i) `5 b2 M     r=i;
; X6 X" @/ s; T9 G; O4 K2 b6 ?    }
7 u7 o. j, d* ]% ?: ^& i    if(temp_ab[lar2.num]&lt;temp) {
6 o) N4 `# A2 f, Y     temp=temp_ab[lar2.num];
     c=lar2.num;
     r=i;
/ G2 V# _) v: U& S" T2 M( G- n    }
   }
0 b; C) m( @+ ^$ Z. W  }
" Q1 D1 Z5 a7 w7 b0 H4 ^! ]8 {  if(lar1.rc=='r'&amp;&amp;lar2.rc=='c') {
% x$ }, r4 i9 h* E6 D) a: I% x   temp=temp_ab[lar1.num][1];
   r=lar1.num;
      c=1;
( M& e% n2 W+ p/ H   for(i=1;i&lt;=num_b;i++)
7 \' u2 }- n! f3 U' G    if(temp_ab[lar1.num]&lt;temp) {
     temp=temp_ab[lar1.num];
     r=lar1.num;
! Y/ }+ H) k: ^$ S1 X     c=i;
+ M! J1 m) P6 F8 _    }
! W5 D7 ~5 _5 N7 F( K/ x   for(i=1;i&lt;=num_a;i++)
    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
     c=lar2.num;
     r=i;
1 N* j- R- J3 {8 `    }
  }
/ X/ J, G& e# E- {2 O  if(lar1.rc=='c'&amp;&amp;lar2.rc=='r') {
& P' V4 p! |1 Z   temp=temp_ab[1][lar1.num];
. Q8 S' E3 i) t; N   r=1;
, P8 B& w: a$ {: {% p      c=lar1.num;
1 B4 M; u4 D; O/ |% ^   for(i=1;i&lt;=num_b;i++)
7 Z+ q- N4 Y' ?% x    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
     r=lar2.num;
5 W6 N- U6 \7 A     c=i;
: W, O: O* N4 g1 S$ f5 h( ~4 k    }
   for(i=1;i&lt;=num_a;i++)
+ Z1 F1 h& {7 J7 }    if(temp_ab[lar1.num]&lt;temp) {
     temp=temp_ab[lar1.num];
& ?4 p+ o3 {, ?2 a/ K4 a     c=lar1.num;
     r=i;
    }
  }
, Z8 f9 W3 o0 V) z2 C9 X* `' Y }
else {
  if(lar1.rc=='r') {
9 o) Y1 K& \% b# d! c4 T0 |5 B   r=lar1.num;
   c=1;
; t! j7 \$ L- v" _6 r: {. d   temp=temp_ab[lar1.num][1];
   for(i=1;i&lt;=num_b;i++)
) G2 R& x7 R  z  m: u- @$ ?3 C8 {    if(temp_ab[lar1.num]&lt;temp) {
. \: L6 q  V+ D5 o3 c1 `2 j" x, Q# {     c=i;
     temp=temp_ab[lar1.num];
    }
( p6 o- ~1 A, l% p0 }, ]  }
  else {
   r=1;
   c=lar1.num;
   temp=temp_ab[1][lar1.num];
9 i* ^; Z9 V8 n  z! |   for(i=1;i&lt;=num_a;i++)
    if(temp_ab[lar1.num]&lt;temp) {
# o! L) ?; e' m+ u3 g, \     r=i;
     temp=temp_ab[lar1.num];
! _3 L4 K- L2 x; I" q- F: h    }
  }
}
9 V  ?- J$ A! B- Y' }# K pbase[r][c]=1;
! Y% \6 h, q, ]8 A! x% x if(temp_a[r]&gt;temp_b[c]) {
* |6 {% P8 N$ N3 X* T  base[r][c]=temp_b[c];
  temp_a[r]=temp_a[r]-temp_b[c];
5 [2 ^) c3 H6 X  temp_b[c]=0;
( Q* E- A- c' g4 J  for(i=1;i&lt;=num_a;i++) temp_ab[c]=M;
}
& \0 ], j$ C" K% M else if(temp_a[r]&lt;temp_b[c]) {
3 {! ]! x1 ~. K% I  d  base[r][c]=temp_a[r];
  temp_b[c]=temp_b[c]-temp_a[r];
  temp_a[r]=0;
  for(i=1;i&lt;=num_b;i++) temp_ab[r]=M;
}
else if(temp_a[r]==temp_b[c]) {
$ ^6 A! J4 F# N1 e( C0 r/ o; q6 U0 p  base[r][c]=temp_a[r];
  temp_a[r]=temp_b[c]=0;
) ~4 t! T/ [( v  N7 h  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;
2 d& v# e6 A6 E' a9 v8 y5 n  if(k!=0) {
- }' ^6 j. e# w" v& B4 _" s   k=0;
+ l$ E2 i4 P6 p; V4 m   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;}
$ I$ j' r9 e1 t3 F  J7 X   if(k==1) pbase[c]=1;
9 [3 n$ s) _7 A   else if(k==2) pbase[r][j]=1;
0 L6 }# N/ |" t* {6 Q  }
}
k=0;
for(i=1;i&lt;=num_a;i++) if(temp_a!=0) k=1;
2 t, c7 ]. p; @' q% Z, h for(i=1;i&lt;=num_b;i++) if(temp_b!=0) k=1;
if(k==0) return;
. R/ X5 F( A5 J' u! i' g- A findinit();
}</P>
" N  B& q7 z* I! k  `$ a<>void computeuv() {
int i,j,k;
for(i=1;i&lt;=num_a;i++)
  for(j=1;j&lt;=num_b;j++)
1 z% W' \0 V. `: ^* K6 d   if(pbase[j]==1) {
( z# Z; G: G9 j1 H/ F9 g4 p0 e    if(pu==1) {v[j]=ab[j]-u; pv[j]=1;}
    if(pv[j]==1) {u=ab[j]-v[j]; pu=1;}
' L0 n, ^& D& T" m* Q. ^, T   }
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;
if(k==1) computeuv();
}</P>
3 p- o, ]' {" @3 W% e<>int check() {
# [1 g" Q3 l0 |7 L' _ 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];
    if(base[j]&lt;0) k=1;
    else if(base[j]==0) l=1;
   }
/ g1 u! I- `; @: |6 \+ z9 p$ \/* for(i=1;i&lt;=num_a;i++){
  for(j=1;j&lt;=num_b;j++) printf("base %lg\t",base[j]);
$ ?, A* a  m% S5 ^& r- w1 @  putchar('\n');}
for(i=1;i&lt;=num_a;i++){
  for(j=1;j&lt;=num_b;j++) printf("pbase %d\t",pbase[j]);
  putchar('\n');}
*/
if(k==0&amp;&amp;l==0) {status=1; return 1;}
else if(k==0&amp;&amp;l!=0) {status=-1; return 1;}
& A' Q8 }2 L! i  s3 [$ D else return 0;
! m. ?! y6 p/ r2 q+ T& B( ?( ?! l}</P>
<>int circle(enum direction dir,struct element cir[],int *t) {
" Y( g  k7 |$ ?+ f int i,j,k;
/*
putchar('\n');
$ r' W- S0 c8 E& B1 a for(i=1;i&lt;=*t;i++) printf("%d: r%d c%d\t",i, cir.r,cir.c);
5 a1 ?+ I5 l8 e) I. ^ putchar('\n');
: {% ?( F" w7 F */
if((*t)!=1&amp;&amp;cir[(*t)].r==cir[1].r&amp;&amp;cir[*t].c==cir[1].c) {
  t--;
  return 1;
  Q9 y- D" [7 l% m3 ^ }
) O. s. e2 l  |& Q8 O if(dir!=down) {
1 |% B: J9 l0 H  ]  k=0;
- `$ n2 p( d6 W6 R% `- J  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;}
2 q' W) ]3 S# l( t7 {* V; g' x% w  for(j=2;j&lt;=*t;j++) if(i==cir[j].r&amp;&amp;cir[*t].c==cir[j].c) k=0;
( ~  k2 d& J- C+ \6 H" `* u0 v  if(k==1) {
   if(dir==up) cir[*t].value=0;
4 K8 E  X7 y1 W  Q5 S   else cir[*t].value=1;
3 n( v3 p' H0 d0 _! W   (*t)++;
   cir[*t].r=i;
   cir[*t].c=cir[(*t)-1].c;
1 y' N7 r0 r- b: ~$ L1 ?   if(circle(up,cir,t)) return 1;
/ U, @1 g" Y4 }  i; M1 B3 U  }
}
  V! k8 R# ^7 G3 E/ v if(dir!=up) {
( R, u5 M& v- E& q5 M  G9 ~  k=0;
' v0 a+ ^/ I( I$ }1 X  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;
  if(k==1) {
" p# q. z2 \/ }$ f2 ^) H' F   if(dir==down) cir[*t].value=0;
   else cir[*t].value=1;
   (*t)++;
   cir[*t].r=i;
   cir[*t].c=cir[(*t)-1].c;
% |! b: u9 \* ~* G   if(circle(down,cir,t)) return 1;
; f+ Y% V: @: f% l5 y% w9 k: A: [  }
- Z5 C0 U- I0 d7 D* Z }
if(dir!=right) {
% W5 y, ]1 ]/ _: ^  k=0;
  for(i=cir[*t].c-1;i&gt;=1;i--)
2 w$ t" K- C; @* l" D   if(pbase[cir[*t].r]==1||(cir[*t].r==cir[1].r&amp;&amp;i==cir[1].c)) {k=1; break;}
# _3 {; R9 A4 I  for(j=2;j&lt;=*t;j++) if(cir[*t].r==cir[j].r&amp;&amp;i==cir[j].c) k=0;
! J8 B3 H+ d) e8 R  if(k==1) {
   if(dir==left) cir[*t].value=0;
   else cir[*t].value=1;
; d& V$ X& N! ?. q* N  p# L   (*t)++;
   cir[*t].r=cir[(*t)-1].r;
, A& n7 J" E9 Q6 t9 `) L. _, W   cir[*t].c=i;
   if(circle(left,cir,t)) return 1;
  }
( L% Q3 d! y! b% c" `/ I }
if(dir!=left) {
  k=0;
/ Y* P! q/ N/ E( D  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;
" }* c2 M( {) ?$ t, l2 d, L  if(k==1) {
   if(dir==right) cir[*t].value=0;
   else cir[*t].value=1;
   (*t)++;
   cir[*t].r=cir[(*t)-1].r;
   cir[*t].c=i;
   if(circle(right,cir,t)) return 1;
2 P) |2 ~+ P- r* V# s  G/ S  }
5 ~- S9 P8 O9 y& G3 K }
1 D1 y( Q4 O: B0 q$ c (*t)--;
: \; C7 r6 `* n2 G1 s return 0;
}</P>
. o! h& V9 G# ?4 H0 W<>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;
* b( i* b1 c/ e8 | u[1]=0; pu[1]=1;
  j) d1 y+ ~* ~6 `# T7 V computeuv();
1 K% |4 ]6 s5 h/ y if(check()) return;
for(i=1;i&lt;=num_a;i++)
  for(j=1;j&lt;=num_b;j++)
9 n# [% p. x' e$ j2 u1 g& H   if(pbase[j]==0) break;
5 @& ~  i' Y/ ^  m base_in.r=i;
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;
, B6 i1 L) l  ?% Q: }    base_in.value=base[j];
7 G( B2 B' P0 H, l. r! I   }</P>
) A* [7 q9 w. \3 X1 p+ s4 k) g) c<> t=1;
cir[t].r=base_in.r;
cir[t].c=base_in.c;
0 g. s, x8 r5 `# E cir[t].value=1;
if(!circle(mid,cir,&amp;t)) {
: ?2 p5 W) X6 s  printf("程序出错！按回车结束");
5 t( H- r  H/ o  getchar();
  exit(0);
' G' u" p% b. F' J# J: \) I }
8 v6 `3 a# w7 p6 w 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>
5 _& L% Q0 b+ a/ b6 P5 J' P<> for(i=2;i&lt;=t;i++) if(cir.value==1) break;
; C- L" H1 w0 K' T$ J' M base_out=cir;
base_out.value=base[cir.r][cir.c];
k=1;
' z: g* H% t1 ?7 L) Z for(i=1;i&lt;=t;i++)
; Y% R6 V. m, X' P# J' ~/ t  if(k%2==0&amp;&amp;cir.value==1&amp;&amp;base[cir.r][cir.c]&lt;base_out.value) {
$ N5 Z: I2 M& H$ L  I7 G   base_out=cir;
   base_out.value=base[cir.r][cir.c];
7 M2 Q6 j4 Q, w4 Y; h7 U/ j# y7 ^, R   k++;
  }
  else if(cir.value==1) k++;
base[cir[1].r][cir[1].c]=0;
k=1;
% T! u( X. F* d" ? for(i=1;i&lt;=t;i++) {
% m5 R; N- J, o/ M0 i% }8 ]4 {( E  if(k%2==1&amp;&amp;cir.value==1) {
! _  ~' R! z( S0 J, d) W0 f   base[cir.r][cir.c]+=base_out.value;
4 M1 n6 u& M$ `8 j6 J   k++;
  }
( Z9 X* H7 U' f5 b9 N  else if(k%2==0&amp;&amp;cir.value==1) {
) ^) H# T/ u! i* B$ F% u   base[cir.r][cir.c]-=base_out.value;
/ I8 B' Y2 ?# g4 j! X3 z4 s   k++;
  }
}
/ e' o) L: l1 [4 {8 l pbase[base_out.r][base_out.c]=0;
pbase[base_in.r][base_in.c]=1;</P>
8 I6 \# s  n: G6 F$ s, q: _<> improve();
9 |! U/ t' x  {0 m$ U# v}</P>
<>void output() {
* d6 d. z: }; x0 S" @! z int i,j;
double sum=0;
+ G$ f' H8 W9 ]" K  r printf("\n运量为：\n");
for(i=1;i&lt;=num_a;i++) {
/ I, O2 j: R& N# w6 B9 L1 F  putchar(' ');
5 p/ q- U# |" L9 l$ ?% {  for(j=1;j&lt;=num_b;j++)
. a8 A1 U& D; v2 k   if(pbase[j]==1) {
    printf("A%d-&gt;B%d:%lg\t",i,j,base[j]);
' ]# i1 \; Z' t( P3 h    sum+=base[j]*ab[j];
   }
   else printf("A%d-&gt;B%d:0\t",i,j);
  putchar('\n');
- @- K/ {6 |2 `3 y* l( d }
printf("\n最低总运费为：%lg\n",sum);
7 m% F! w' s8 S$ J}
</P>

liunengwu

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

hzlhm

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

enrique08

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

zhongguohelin

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