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

plgatc

<>/*************************************************************************
3 A/ S8 o' |! M0 ~                         表上作业法解运输问题        
3 T, D; `6 q& d
- e% H6 ?( Z% \5 u 编程环境：VC++6.0     
程序说明：
4 @6 e. B% ?; E7 p Vogel法求初始解，位势法检验是否最优，递归搜索闭回路改进解。
*************************************************************************/
9 ^5 o+ d3 H$ R9 k: l( H#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;</P>
<>#define MAX 100
#define M 999999</P>
<>int status; //1唯一最优解，-1无穷多最优解</P>
<>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];
double ab[MAX][MAX],temp_ab[MAX][MAX];
double base[MAX][MAX];
int pbase[MAX][MAX];
struct element {
8 h4 l7 f: l  |2 }- c6 s0 F' `; C int r;
0 V) U4 T$ E/ f4 C4 A int c;
0 H) Q* J2 O: A2 `$ B( b( m: n double value;
/ n/ x7 G# }. D: p2 w9 k  G( v};
" w* H7 g% _/ n' f9 D  P% d7 @enum direction {mid,up,down,left,right};</P>
<>void create();
2 C4 c4 q3 w5 [+ [. l' Tvoid banner();
$ y1 N7 K! y. y& `$ s' @double dabs(double d);
void findinit();
void computeuv();
3 p- }: b3 |2 Y$ B/ |; Sint check();
0 F4 r- ^* Z% cint  circle(enum direction dir,struct element cir[],int *t);
void improve();
" c; s. i  W, I# c& b; kvoid output();</P>
' s* v3 ?3 m! f$ a- f" L% G<>void main() {
, ?- p, |4 _8 f$ g" W% d banner();
3 _& Q; I4 K$ t" g+ A! y5 W create();
printf("\n按回车确认后开始求解");
getchar();
+ s& [' N" _! N0 H3 b getchar();
findinit();
$ r: ]+ K. ^) N/ z/ A improve();
. A+ a/ P, D6 m  P0 W! e switch(status) {
case 1:
& Q, |# _3 S8 H  output();
  puts("\n原问题有唯一最优解。\n");
  puts("\n按回车结束");
  getchar();
  exit(0);
$ H( f* b# x2 P) \ case -1:
7 H/ I9 h  @9 ^& @( h. _  output();
  puts("\n原问题有无穷多最优解。\n");
  puts("\n按回车结束");
  getchar();
  exit(0);
}
2 \( \: t7 G! H8 Z# t}</P>
, {4 d1 c) E9 E1 D5 }7 |/ \<>void banner() {
printf("\t\t****************************************\n");
" i$ G4 L" C9 N/ h printf("\t\t         表上作业法解运输问题\n");
8 u( }' O0 T7 U$ b" O printf("\t\t                              Thunder\n");
7 x; I0 T5 F' l. m, i4 O printf("\t\t****************************************\n");
0 P, A/ }- l6 s2 o printf("\n");
, l9 N. f, ?1 j: H0 P. [}</P>
<>void create() {
int i,j;
# S' \$ O2 R. Q double sum_a,sum_b;
/ e: T# H/ |4 v0 a char confirm;
while(1) {
  printf("请输入产地个数：");
) l3 W, B$ t# K1 }, ~5 `7 r  scanf("%d",&amp;num_a);
  for(i=1;i&lt;=num_a;i++) {
1 o3 c/ o1 C7 Y1 h" k/ H   printf("A%d产量：",i);
   scanf("%lf",&amp;a);
* v, d1 y# \0 P. R# K  }
/ ]" x! d5 n' e2 o  for(i=1;i&lt;=num_a;i++) printf("A%d产量：%lg\t",i,a);
! @9 n( U+ P0 \0 v, P  printf("\n正确吗？：(y/n)");
' k. c! s1 a& x$ q- o3 O  getchar();
  confirm=getchar();
  if (confirm=='y') break;
  else if(confirm=='n') continue;
}
9 f, K- z' P  a' J/ Z$ V. Q while(1) {
8 l$ k& J: @* u8 J5 E  printf("\n请输入销地个数：");
  scanf("%d",&amp;num_b);
  for(i=1;i&lt;=num_b;i++) {
   printf("B%d销量：",i);
. P- e0 C) N: d- C* _; L   scanf("%lf",&amp;b);
  }
  for(i=1;i&lt;=num_b;i++) printf("B%d销量：%lg\t",i,b);
  printf("\n正确吗？：(y/n)");
  getchar();
) O5 Z: W7 S6 w* ?, G  confirm=getchar();
  if (confirm=='y') break;
  else if(confirm=='n') continue;
}
& o0 i# C! G8 j putchar('\n');
for(i=1;i&lt;=num_a;i++) {
  for(j=1;j&lt;=num_b;j++) {
   printf("A%d到B%d运价：",i,j);
   scanf("%lf",&amp;ab[j]);
9 \' s7 X# ~2 C2 V% f- r/ G2 J5 `3 A  }
, G/ E& b% k7 ~* X  for(j=1;j&lt;=num_b;j++) printf("A%d到B%d：%lg\t",i,j,ab[j]);
  printf("\n正确吗？：(y/n)");
  getchar();
& M2 u  x! |' u2 ~  I/ o: K  confirm=getchar();
  if(confirm=='n') i--;
  putchar('\n');
}
//处理产销不平衡的情况
sum_a=sum_b=0;
) n; \, Y6 @- y: C( C 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);
if(sum_a==sum_b) printf("\t产销平衡。");
8 }4 e* K9 D/ B: N else if(sum_a&gt;sum_b) {
  printf("\t供大于求，增加假想销地B%d。\n",++num_b);
0 n! P/ t4 h) j: s/ i( L6 |, v  b[num_b]=sum_a-sum_b;
  for(i=1;i&lt;=num_a;i++) ab[num_b]=0;
/ s  V( N, t; R3 B0 Z. \) C }
1 `9 ~+ m6 K; |& A" E/ Z else if(sum_a&lt;sum_b){
  printf("\t供不应求，增加假想产地A%d。\n",++num_a);
' `1 n' ]# l4 _/ o  a[num_a]=sum_b-sum_a;
" `9 r9 `; y$ @4 v* A  for(i=1;i&lt;=num_b;i++) ab[num_a]=0;
}
5 R/ x* d. K/ u: u8 s. K //求解前的准备
+ T2 b- b$ Z4 D6 R& { for(i=1;i&lt;=num_a;i++)
, s5 j- P* b% X/ [8 A" V  for(j=1;j&lt;=num_b;j++)
" \6 U9 K+ d! u. `% p) S   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;
  g' x+ j# t6 K for(i=1;i&lt;=num_a;i++)
for(j=1;j&lt;=num_b;j++) temp_ab[j]=ab[j];
//回显问题
/ `0 L0 U6 T5 P8 r printf("\n\n原问题为：\n\n");
   printf("产量：\n ");
for(i=1;i&lt;=num_a;i++) printf("A%d:%lg\t",i,a);
printf("\n运量：\n ");
1 y7 V- Y8 r3 v  S/ Q- D' m for(i=1;i&lt;=num_b;i++) printf("B%d:%lg\t",i,b);
/ A5 u; J$ }! Q' G5 p. ^7 }, U$ o printf("\n运价为：\n");
for(i=1;i&lt;=num_a;i++) {
  putchar(' ');
  for(j=1;j&lt;=num_b;j++)
   printf("A%d-&gt;B%d:%lg\t",i,j,ab[j]);
, b" |% K; |! T/ g1 r; }  putchar('\n');
' ~! X4 ]3 W4 i0 n }
1 n2 J! P) `3 d}</P>
$ N9 ~! r5 X! s, P' O/ D" [& v) f<>double dabs(double d) {
if(d&gt;=0) return d;
else return -d;
}</P>
. @& N; A  Y6 {$ y) I# O<>void findinit() {
int i,j,k;
double r_penum[MAX],c_penum[MAX];
struct largest {
  char rc;
$ q% C4 O! [) W* ~3 s  int num;
) t0 L8 m6 F! e5 N6 {- m% o  double value;
};
' m6 O0 `( b9 i/ A: M0 @2 L struct largest lar1,lar2;
+ E; o; W4 Q" E5 w int r=0,c=0;
double a1,a2,b1,b2,temp;</P>
<> for(i=1;i&lt;=num_a;i++) {
: \* a9 y& q% _& M  temp=temp_ab[1];
& H6 _* k/ z' C1 _" x1 r) S  for(j=1;j&lt;=num_b;j++)
$ ?( Y! O: Y# }5 L9 v/ ~) O   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
  a1=a2=temp;
  for(j=1;j&lt;=num_b;j++)
   if(temp_ab[j]&lt;=a1) {
$ U, E; ~  R# o/ j    a2=a1;
; }* |' U8 D3 h1 I' N0 z+ @    a1=temp_ab[j];
: W9 X' q) b$ \7 u0 r! q- D   }
   else if(temp_ab[j]&lt;=a2) a2=temp_ab[j];
6 E! E; D9 R) T  r_penum=dabs(a1-a2);
7 J. ?7 R# K. I: Z }</P>
7 \4 J0 @! `# K& Y: s4 K+ r<> for(i=1;i&lt;=num_b;i++) {
1 t) E6 p5 f+ h' W# Z8 G  temp=temp_ab[1];
: {7 K8 P/ U* Y- o  A9 Q: K7 b4 s  for(j=1;j&lt;=num_a;j++)
   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
  b1=b2=temp;
4 S" G& I$ ]# m- ^* N8 o  for(j=1;j&lt;=num_a;j++)  
7 h3 _. U+ i! X# r   if(temp_ab[j]&lt;=b1) {
    b2=b1;
4 X* j& \3 j& r: C8 E    b1=temp_ab[j];
! e; g% m: R0 a   }
   else if(temp_ab[j]&lt;=b2) b2=temp_ab[j];
  c_penum=dabs(b1-b2);
}
, F* @7 H7 @1 |. y /*
for(i=1;i&lt;=num_a;i++) printf("pa%d=%lg ",i,r_penum);
& H  U" y8 Q( v, X: [ putchar('\n');
3 g* P# `4 R9 L: 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;
for(i=1;i&lt;=num_b;i++) if(c_penum&lt;temp) temp=c_penum;</P>
<> //考虑了有两个罚数相等的情况，大于两个相等只取其中两个进行比较
; U1 @# C  A* U) u lar1.value=lar2.value=temp;
lar1.num=lar2.num=1;
lar1.rc=lar2.rc='r';
for(i=1;i&lt;=num_a;i++)
2 f  N# h9 _' G6 @  u% k6 E7 s  if(r_penum&gt;=lar1.value) {
0 L  q6 n, C' ?4 u/ H1 `   lar2=lar1;
   lar1.rc='r';
   lar1.num=i;
$ E6 G8 B0 k* I( y& q   lar1.value=r_penum;
6 S, h  v" ~, Z  }
) D1 Y" e+ H) [" t  else if(r_penum&gt;=lar2.value) {
   lar2.rc='r';
$ ?) h6 p; B7 b# f; Q   lar2.num=i;
   lar2.value=r_penum;
  }</P>
<> for(i=1;i&lt;=num_b;i++)
  if(c_penum&gt;=lar1.value) {
   lar2=lar1;
  O$ T& ?8 I. k   lar1.rc='c';
   lar1.num=i;
   lar1.value=c_penum;
  }
7 P- [, v- ]5 m: @1 w. q, v  else if(c_penum&gt;=lar2.value) {
   lar2.rc='c';
   lar2.num=i;
8 p$ o1 |+ ^4 D! z   lar2.value=c_penum;
7 p& ~" A5 j) p" M$ o  }</P>
3 h6 y; e$ c7 b; M<> if(lar1.value==lar2.value&amp;&amp;(lar1.num!=lar2.num||lar1.rc!=lar2.rc)) {
. ]' [0 s/ O" u, {, @) l: C/ V, v5 t  if(lar1.rc=='r'&amp;&amp;lar2.rc=='r') {
   temp=temp_ab[lar1.num][1];
   r=lar1.num;
+ @. L) E( M- [5 ?% Y      c=1;
   for(i=1;i&lt;=num_b;i++) {
5 e+ O2 A9 V! V5 l# i( @    if(temp_ab[lar1.num]&lt;temp) {
8 T5 E4 }; I  J, F     temp=temp_ab[lar1.num];
8 i; z6 D% l& q- S2 B  _& \0 ]     r=lar1.num;
     c=i;
    }
    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
     r=lar2.num;
     c=i;
    }
   }
  }
  if(lar1.rc=='c'&amp;&amp;lar2.rc=='c') {
   temp=temp_ab[1][lar1.num];
# F# p% R6 ]/ m( U   r=1;
      c=lar1.num;
) w  r) c* i4 j  M1 b# O7 H/ K   for(i=1;i&lt;=num_a-1;i++) {
6 t  V8 l- ^$ t. l4 R; G    if(temp_ab[lar1.num]&lt;temp) {
( p/ s. R7 ]! F' _  ]; [     temp=temp_ab[lar1.num];
. e3 g4 I' `" H' ^. }+ m# A6 l     c=lar1.num;
     r=i;
    }
: h2 |5 u+ ]& y+ o# y1 f' X4 V' Y    if(temp_ab[lar2.num]&lt;temp) {
9 y1 ]2 [$ K$ k9 E1 m     temp=temp_ab[lar2.num];
     c=lar2.num;
     r=i;
    }
   }
( ~0 ^7 \  q5 @+ @3 D! q  }
% T# Y) M# {  u% z0 r$ G  if(lar1.rc=='r'&amp;&amp;lar2.rc=='c') {
   temp=temp_ab[lar1.num][1];
! K- \* H0 k, @   r=lar1.num;
      c=1;
   for(i=1;i&lt;=num_b;i++)
# v0 o; Y; O/ r    if(temp_ab[lar1.num]&lt;temp) {
     temp=temp_ab[lar1.num];
* J' O% B2 |: I) D: t     r=lar1.num;
% {# I' M7 l1 u; B3 z- ?( ^     c=i;
9 Q4 j  y) P# a' s8 F7 r  t" Y    }
9 O% ?' K4 y3 M, m   for(i=1;i&lt;=num_a;i++)
    if(temp_ab[lar2.num]&lt;temp) {
, g" Y/ N3 l/ u8 C# n1 u/ l     temp=temp_ab[lar2.num];
     c=lar2.num;
     r=i;
1 d5 U- ~7 G. i8 H    }
. `% S. ^8 ?+ _; u  n9 V( m& k* K- F. ~  }
$ C0 u  V! C7 h! l. _" |; @  if(lar1.rc=='c'&amp;&amp;lar2.rc=='r') {
5 J) U5 U1 X! H, A5 Z4 Y   temp=temp_ab[1][lar1.num];
6 A+ @8 Z# K5 L) T3 k6 O   r=1;
      c=lar1.num;
1 K" y, L0 I# s6 _+ a   for(i=1;i&lt;=num_b;i++)
    if(temp_ab[lar2.num]&lt;temp) {
, w- j5 r. ~1 l; Y7 A$ z     temp=temp_ab[lar2.num];
" l/ _: @  ~. q3 z     r=lar2.num;
" _8 G% [5 J7 n! w7 w0 T' T     c=i;
    }
   for(i=1;i&lt;=num_a;i++)
. }$ e$ t( N( C) w    if(temp_ab[lar1.num]&lt;temp) {
0 i, s; D! U4 N8 `+ T. `     temp=temp_ab[lar1.num];
     c=lar1.num;
     r=i;
# N2 X# K. S9 D, Y) @3 R$ Z: s    }
6 m! p6 f$ u" o- {" s3 b  }
( C; t! u9 F. F }
5 q, p0 F$ i/ o: X else {
  E8 ~& A" T" C8 R# y  if(lar1.rc=='r') {
- x4 e: n- L: K' e* q7 L9 w6 y   r=lar1.num;
3 `) Q' n: I( |6 ?   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];
6 Q/ Z4 S0 T4 u  _    }
  }
  else {
   r=1;
6 H5 i# \3 F  a# ?" ~% S   c=lar1.num;
8 I4 d& L6 a: ^   temp=temp_ab[1][lar1.num];
8 O2 o9 \7 A# s( \0 [' d* H' s   for(i=1;i&lt;=num_a;i++)
& P$ W' p5 q. b    if(temp_ab[lar1.num]&lt;temp) {
& @; |/ H7 x& f+ V: |     r=i;
     temp=temp_ab[lar1.num];
9 S, }2 W9 y4 r  |6 P( ?5 a    }
  }
% k$ s, d+ b  u! O }
0 j3 b# y  \# p6 D9 J/ \' u pbase[r][c]=1;
if(temp_a[r]&gt;temp_b[c]) {
  base[r][c]=temp_b[c];
5 j3 B/ a$ c( |: E4 l0 p  temp_a[r]=temp_a[r]-temp_b[c];
  temp_b[c]=0;
7 i* u: V" ~1 Z* r" K8 A! M" b4 j7 D  for(i=1;i&lt;=num_a;i++) temp_ab[c]=M;
}
( q2 L9 f' b  v2 O8 @2 c else if(temp_a[r]&lt;temp_b[c]) {
( h8 e7 f% u# k8 A! U1 |  base[r][c]=temp_a[r];
) ^& `3 Z5 P9 y* @' N3 e( S  temp_b[c]=temp_b[c]-temp_a[r];
7 S1 H  s  b/ D& @  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];
3 a  p7 s8 X# o. g  temp_a[r]=temp_b[c]=0;
  for(i=1;i&lt;=num_a;i++) temp_ab[c]=M;
  for(i=1;i&lt;=num_b;i++) temp_ab[r]=M;
  M% c* C8 P3 p+ g" C  k=0;
  for(i=1;i&lt;=num_a;i++) if(temp_a!=0) k=1;
$ }! [4 B% E! [  for(i=1;i&lt;=num_b;i++) if(temp_b!=0) k=1;
% T$ Q6 }8 r) R1 z, [( n0 H. b/ H6 P2 H  if(k!=0) {
3 g7 U; k/ @4 F, M' O+ W  f   k=0;
4 V0 s& X5 `9 Z. |6 I   for(i=1;i&lt;=num_a;i++) if(pbase[c]!=1) {k=1;break;}
9 q' g  ]! I" G* u4 A4 V% \+ l   for(j=1;j&lt;=num_b;j++) if(pbase[r][j]!=1) {k=2;break;}
  Y& J' N' @3 o0 n3 e8 K. L2 p   if(k==1) pbase[c]=1;
$ s, F% d$ Z4 j/ B# G   else if(k==2) pbase[r][j]=1;
9 k+ G1 ?; E) i: s# {  }
}
k=0;
for(i=1;i&lt;=num_a;i++) if(temp_a!=0) k=1;
# K5 w# R7 s/ B. v  ?; A+ w for(i=1;i&lt;=num_b;i++) if(temp_b!=0) k=1;
3 D/ K3 s3 O9 T  N if(k==0) return;
4 `" U: [; d- n( ~ findinit();
* u1 W' N( N5 g, A( e- S, D7 G1 b}</P>
! y* ]9 g/ I/ g- ?; u& |$ m7 [# Q/ E<>void computeuv() {
* k* I5 {$ w; ]8 j! e int i,j,k;
. y9 q7 G( s. k- z9 [$ y! s6 K for(i=1;i&lt;=num_a;i++)
  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==1) {
" l4 d% u* K& M) k- F9 E& P    if(pu==1) {v[j]=ab[j]-u; pv[j]=1;}
    if(pv[j]==1) {u=ab[j]-v[j]; pu=1;}
# [+ c4 m3 u4 m4 C8 x   }
k=0;
for(i=1;i&lt;=num_a;i++) if(pu==0) k=1;
3 j  x8 n3 o9 `- [" M4 o& `' R for(i=1;i&lt;=num_b;i++) if(pv==0) k=1;
, ?6 i! _* h; O. u if(k==1) computeuv();
9 u. O6 B. t! r  |( Z& I6 P}</P>
<>int check() {
int i,j,k,l;
9 }' h4 N. \; w5 P) P k=l=0;
for(i=1;i&lt;=num_a;i++)
  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==0) {
* b5 s0 p0 Q2 ^% [    base[j]=ab[j]-u-v[j];
    if(base[j]&lt;0) k=1;
    else if(base[j]==0) l=1;
, Y& B' n0 @/ ~   }
# y: S6 S3 C- {& O/* for(i=1;i&lt;=num_a;i++){
. V8 \- q$ j( ]7 |% r  for(j=1;j&lt;=num_b;j++) printf("base %lg\t",base[j]);
& O! [7 s3 U/ g2 Z, \8 u; A  putchar('\n');}
9 Z" v% z- o, r' q( @- a3 Q" G8 M; g4 C for(i=1;i&lt;=num_a;i++){
4 m  v# p* _7 K! R  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;}
1 z4 M' E9 n5 t! |, Z2 ^3 E7 ^( k' B else if(k==0&amp;&amp;l!=0) {status=-1; return 1;}
0 N  t# P: u% v# c else return 0;
+ f( l; @) ?2 M' E2 H}</P>
<>int circle(enum direction dir,struct element cir[],int *t) {
int i,j,k;
/*
" c# f' B- m3 y7 S6 Y4 ?  B putchar('\n');
for(i=1;i&lt;=*t;i++) printf("%d: r%d c%d\t",i, cir.r,cir.c);
putchar('\n');
& ~+ }- f- q, y# M */
if((*t)!=1&amp;&amp;cir[(*t)].r==cir[1].r&amp;&amp;cir[*t].c==cir[1].c) {
% ]* b$ N& {8 y1 V  t--;
  k4 t% R% C3 H! y& \9 {8 |. N( O  return 1;
# _. o* R: u; t8 H! r }
if(dir!=down) {
, A$ m# q. g" Q, w  k=0;
  for(i=cir[*t].r-1;i&gt;=1;i--)
8 ?- s3 _9 v0 a/ ^9 ~# F) M   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;
6 K$ k5 g$ F; ?- e! F, C: W  if(k==1) {
   if(dir==up) cir[*t].value=0;
   else cir[*t].value=1;
   (*t)++;
  p) _$ ?; H  d* N0 y5 l; c   cir[*t].r=i;
   cir[*t].c=cir[(*t)-1].c;
   if(circle(up,cir,t)) return 1;
* O$ A* f& P* ^( i% H* V  G  }
}
7 q6 ~8 o+ |7 H if(dir!=up) {
+ w, s2 V6 M4 k/ S3 B  k=0;
8 j& a0 ~6 g3 C3 P& ~  for(i=cir[*t].r+1;i&lt;=num_a;i++)
- ~0 z1 t! K  u/ B* |- o2 K   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;
5 M7 i5 l4 ]8 d; \; x1 W  if(k==1) {
   if(dir==down) cir[*t].value=0;
! U; G: X# _$ ^# q   else cir[*t].value=1;
   (*t)++;
  U, j% U" _( m2 ~! ~   cir[*t].r=i;
, g9 t4 D# h! x7 i8 M# i9 c   cir[*t].c=cir[(*t)-1].c;
   if(circle(down,cir,t)) return 1;
  }
}
if(dir!=right) {
+ V; ?0 @' }9 m( i' b: z! ~1 p  k=0;
# C& X: j$ |! S1 y7 Z  for(i=cir[*t].c-1;i&gt;=1;i--)
- J8 {0 \# h5 {   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) {
   if(dir==left) cir[*t].value=0;
   else cir[*t].value=1;
   (*t)++;
, l  v! |# U3 v, u* P* n, G+ U3 G   cir[*t].r=cir[(*t)-1].r;
) L: t* O7 D6 R( J! k% ^   cir[*t].c=i;
' N8 D6 H, F  V* E& _   if(circle(left,cir,t)) return 1;
  }
& w6 k8 O$ k, O: y: R$ t1 ~ }
if(dir!=left) {
  k=0;
  for(i=cir[*t].c+1;i&lt;=num_b;i++)
8 k* {7 w% k# \$ ]: I3 A# J   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;
  m4 R& d% n7 W( U) Z$ z  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;
  }
% ?; B1 X" ^, ]) M) u$ H6 W# L }
8 D' V1 u# l3 h4 H# B4 B (*t)--;
- |$ v. `+ Y# f3 z2 t/ ] return 0;
}</P>
! Z5 J& Z& X/ N# @% V, t2 e<>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;
, r" G! O( d# e. p0 a/ ~' t for(i=1;i&lt;=num_b;i++) pv=0;
u[1]=0; pu[1]=1;
computeuv();
1 i# A) m; v: ^$ p3 y if(check()) return;
for(i=1;i&lt;=num_a;i++)
  for(j=1;j&lt;=num_b;j++)
7 `9 |; ~% t/ q2 U   if(pbase[j]==0) break;
; W* @0 c2 f' g4 @' j, A% b2 Y base_in.r=i;
* r  H$ H7 O; N0 E( A/ e base_in.c=j;
base_in.value=base[j];</P>
# g- U$ @. U! y/ D. |<> for(i=1;i&lt;=num_a;i++)
% b1 C0 ]9 q# I3 J) @! F  for(j=1;j&lt;=num_b;j++)
$ w. }  c! e" w3 y   if(pbase[j]==0&amp;&amp;base[j]&lt;base_in.value) {
7 v  j  `0 K1 d, e+ n% c9 K    base_in.r=i;
    base_in.c=j;
    base_in.value=base[j];
1 J. h$ B* Y! z, x4 P$ W   }</P>
<> t=1;
cir[t].r=base_in.r;
3 |1 ?" z" @6 a" O0 }- m cir[t].c=base_in.c;
) s/ Z( C) }& a* v" P- h% E$ p cir[t].value=1;
5 X; Y7 r' ?  V" k! ~+ r if(!circle(mid,cir,&amp;t)) {
  printf("程序出错！按回车结束");
  getchar();
  exit(0);
2 x& `' l: C6 ? }
t--;
// for(i=1;i&lt;=t;i++) printf("%d:r%d c%d v%lg\t",i,cir.r,cir.c,cir.value);
, O4 F8 m6 M$ _// putchar('\n');</P>
  z  @) b$ o, \1 u) _<> for(i=2;i&lt;=t;i++) if(cir.value==1) break;
  ]4 q% a# T1 x- L: i base_out=cir;
base_out.value=base[cir.r][cir.c];
' y. \0 o& B3 P4 A; v# f k=1;
! v6 R" g& Y6 U) y2 i) F3 ]1 y 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) {
   base_out=cir;
   base_out.value=base[cir.r][cir.c];
9 [, D4 U7 v$ a% I   k++;
  }
# v- H- B* y0 h9 P% w  else if(cir.value==1) k++;
base[cir[1].r][cir[1].c]=0;
& ^0 j  A9 A% ]; E+ J k=1;
4 J& h$ G1 R8 P% o/ c- L" H for(i=1;i&lt;=t;i++) {
; H; M4 c! C  y0 y! r  G- d  if(k%2==1&amp;&amp;cir.value==1) {
   base[cir.r][cir.c]+=base_out.value;
! o1 x& o1 F* |$ C% I) n   k++;
  }
  else if(k%2==0&amp;&amp;cir.value==1) {
0 g$ j0 D, y7 A8 I/ u   base[cir.r][cir.c]-=base_out.value;
5 S5 T( W+ n, t- h5 k   k++;
  }
}
: `  P7 w1 d; r2 z* l1 @. `1 i3 b pbase[base_out.r][base_out.c]=0;
pbase[base_in.r][base_in.c]=1;</P>
<> improve();
9 {6 y! r9 M' A}</P>
<>void output() {
int i,j;
double sum=0;
printf("\n运量为：\n");
7 |- e3 J" H! Y0 Z: T9 j) ~( b for(i=1;i&lt;=num_a;i++) {
! A: {8 z9 G' ~# f: g- d  putchar(' ');
5 a/ w% B0 X% |  for(j=1;j&lt;=num_b;j++)
# o! h; ?+ _, i+ m) E& O* N! V) `4 c   if(pbase[j]==1) {
    printf("A%d-&gt;B%d:%lg\t",i,j,base[j]);
/ n# f; z4 a  L4 K  S+ t    sum+=base[j]*ab[j];
   }
   else printf("A%d-&gt;B%d:0\t",i,j);
  putchar('\n');
}
; ]& n, z" k* H2 @7 ?) T6 { printf("\n最低总运费为：%lg\n",sum);
}
</P>

zhongguohelin

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

enrique08

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

hzlhm

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

liunengwu

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