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

plgatc

<>/*************************************************************************
                         表上作业法解运输问题        
6 X( \% a! m+ a  a: W# `6 _( O
$ |4 e: _) {% c0 `9 _' R1 u5 ]0 O! _ 编程环境：VC++6.0     
程序说明：
Vogel法求初始解，位势法检验是否最优，递归搜索闭回路改进解。
*************************************************************************/
#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;</P>
<>#define MAX 100
& t' @' _/ j( c5 P#define M 999999</P>
<>int status; //1唯一最优解，-1无穷多最优解</P>
$ [5 y+ J/ }/ B" @<>int num_a,num_b;
double a[MAX],b[MAX],temp_a[MAX],temp_b[MAX];
5 G# f; }# Y! U6 h0 z. Qdouble u[MAX],v[MAX],pu[MAX],pv[MAX];
double ab[MAX][MAX],temp_ab[MAX][MAX];
. W% w, @: T: ~( n4 tdouble base[MAX][MAX];
int pbase[MAX][MAX];
3 ^  q6 K9 s- a8 Estruct element {
" C2 r7 f" G$ W1 P int r;
int c;
double value;
' ]/ C- G. }* O" ^};
- u* a( q5 q" r8 Tenum direction {mid,up,down,left,right};</P>
3 i4 ~6 y* h" K5 Y' R9 k; G<>void create();
void banner();
" `- g; Z) V& d7 vdouble dabs(double d);
4 a5 |3 ^4 {2 @6 l" yvoid findinit();
( j  I4 {: I: u& d: }9 R1 Mvoid computeuv();
2 E8 P: A6 K  v' E  U- Fint check();
int  circle(enum direction dir,struct element cir[],int *t);
void improve();
; B5 q1 x2 J4 g0 w/ kvoid output();</P>
<>void main() {
banner();
create();
printf("\n按回车确认后开始求解");
7 U  p  {( _5 _6 L  Q/ z- ~ getchar();
3 w0 U( ]6 `: \, _$ C getchar();
findinit();
0 v5 M+ J1 u) ^8 F3 @% t improve();
6 J, q6 z1 o( ]  H8 l/ s4 x switch(status) {
% s$ I1 C% T7 h/ H3 q6 i) n case 1:
  output();
2 Y; X7 s, @" c9 i  puts("\n原问题有唯一最优解。\n");
; D* }' j3 i' H, l) S  puts("\n按回车结束");
, ~( V. [, n* y+ C5 J  Q/ A  getchar();
0 T5 l9 t% P  A+ x+ j  exit(0);
case -1:
  output();
  puts("\n原问题有无穷多最优解。\n");
  puts("\n按回车结束");
" |! G; _5 M& N+ w  K; w  getchar();
  exit(0);
}
}</P>
6 N" n! C- D3 Q+ O<>void banner() {
! F2 M- U" x* u, e' {- S; r8 o printf("\t\t****************************************\n");
; I9 x% z% S4 c; ?7 n printf("\t\t         表上作业法解运输问题\n");
printf("\t\t                              Thunder\n");
printf("\t\t****************************************\n");
9 f+ P9 F/ G( u5 O2 ] printf("\n");
- B8 S( ~: v& \+ u2 Z' o}</P>
<>void create() {
4 d% a$ d  m3 u3 C4 d* N5 C+ E9 c; b int i,j;
* X% x. r$ k& V. |7 j, M1 K2 X double sum_a,sum_b;
char confirm;
5 y4 R6 v6 \: T( j1 l while(1) {
5 ~3 D+ M2 [7 P  printf("请输入产地个数：");
  scanf("%d",&amp;num_a);
  for(i=1;i&lt;=num_a;i++) {
   printf("A%d产量：",i);
7 J6 A: R5 b2 Q: B   scanf("%lf",&amp;a);
  }
  for(i=1;i&lt;=num_a;i++) printf("A%d产量：%lg\t",i,a);
6 O) O1 @2 ?6 x" r: ?  printf("\n正确吗？：(y/n)");
) ^9 }% q$ i/ S8 F4 J  getchar();
  confirm=getchar();
  if (confirm=='y') break;
+ a+ ^! l: G1 B* @- L, ]/ s7 J. o  else if(confirm=='n') continue;
}
( ]! W3 K1 Q' T0 ]1 o& k8 d while(1) {
  n4 M- |3 [( E( p, S  printf("\n请输入销地个数：");
  scanf("%d",&amp;num_b);
0 F' s8 U  u0 u8 j( U+ D' c8 n3 E  for(i=1;i&lt;=num_b;i++) {
   printf("B%d销量：",i);
5 n7 j8 L0 q6 n& B0 x( d3 R   scanf("%lf",&amp;b);
) \9 ?# c( Z/ `- r( f9 E  }
; T/ f0 K+ ?7 V8 \2 y  for(i=1;i&lt;=num_b;i++) printf("B%d销量：%lg\t",i,b);
* C5 \# z2 A& {7 z/ n  printf("\n正确吗？：(y/n)");
  getchar();
! L, q, t$ l, x4 M) k  confirm=getchar();
4 V0 X3 z9 Y& b! @5 M  if (confirm=='y') break;
& q9 B, q+ I6 J0 V3 h, S; k1 x1 t  else if(confirm=='n') continue;
2 V, q7 a# u) F1 Y }
putchar('\n');
9 r/ _4 o7 ?( j7 l" N for(i=1;i&lt;=num_a;i++) {
; G7 ]- u- `2 Y0 z! c  for(j=1;j&lt;=num_b;j++) {
   printf("A%d到B%d运价：",i,j);
   scanf("%lf",&amp;ab[j]);
  }
) I1 L' ^6 p" c6 d8 G: A* E7 F  for(j=1;j&lt;=num_b;j++) printf("A%d到B%d：%lg\t",i,j,ab[j]);
  printf("\n正确吗？：(y/n)");
  getchar();
/ ?  f' L) ~& E0 W  confirm=getchar();
7 j" m8 K5 z- F4 f( I, W  b5 o  if(confirm=='n') i--;
% w1 w3 h5 X& U4 L) s' b% S  putchar('\n');
}
//处理产销不平衡的情况
+ }7 M- D* i8 j$ J7 x& e! E8 s sum_a=sum_b=0;
for(i=1;i&lt;=num_a;i++) sum_a+=a;
$ \* d# A, D' \9 H3 G9 @+ c; o% C( r for(i=1;i&lt;=num_b;i++) sum_b+=b;</P>
<> printf("总产量：%lg\t总销量：%lg",sum_a,sum_b);
6 I; X/ H1 W) n& V1 r: B9 M! n if(sum_a==sum_b) printf("\t产销平衡。");
else if(sum_a&gt;sum_b) {
# o4 p( [9 C5 F, T2 O, }  printf("\t供大于求，增加假想销地B%d。\n",++num_b);
; d; Y" v8 E/ D  b[num_b]=sum_a-sum_b;
% ?7 }; M$ m9 s: p" f  for(i=1;i&lt;=num_a;i++) ab[num_b]=0;
" o% v! B$ p$ C }
+ k' ^$ ^- L# m6 C  n& e else if(sum_a&lt;sum_b){
, F9 K/ N  |) d* R$ U  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;
}
//求解前的准备
for(i=1;i&lt;=num_a;i++)
- a0 N& W5 a8 }( g' q7 k9 G$ a  for(j=1;j&lt;=num_b;j++)
0 d" m/ n+ F  D, w   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;
8 a' ~$ v% {" p, H% i for(i=1;i&lt;=num_a;i++)
for(j=1;j&lt;=num_b;j++) temp_ab[j]=ab[j];
4 u9 |, O/ O. ^( B0 _, y //回显问题
printf("\n\n原问题为：\n\n");
. q& e/ Z* O) E- x" Y) h5 E   printf("产量：\n ");
- _& Z" A* z9 U' _ for(i=1;i&lt;=num_a;i++) printf("A%d:%lg\t",i,a);
5 L& o7 L, w+ N" }! n printf("\n运量：\n ");
- ~% F- r/ y: x: n7 ]" \ for(i=1;i&lt;=num_b;i++) printf("B%d:%lg\t",i,b);
printf("\n运价为：\n");
/ _7 g" |6 l* q* n+ k( _ for(i=1;i&lt;=num_a;i++) {
# v. j7 Z  R2 m8 g: P& k  putchar(' ');
  i4 `/ r' W8 A# v0 R/ R  l  for(j=1;j&lt;=num_b;j++)
   printf("A%d-&gt;B%d:%lg\t",i,j,ab[j]);
  putchar('\n');
4 W, i9 B5 e3 ?# t% p! `" `8 u }
( ~, {. z+ a7 \4 Y- s" O}</P>
<>double dabs(double d) {
if(d&gt;=0) return d;
else return -d;
, t, e% e% I. d' h}</P>
$ j0 B. m/ ?7 Z<>void findinit() {
1 h1 g% b% T/ Y5 r/ ?0 a' M5 ` int i,j,k;
2 O$ P9 X: Q# U$ e double r_penum[MAX],c_penum[MAX];
struct largest {
+ x: L  Y( L) C, B6 j( o  char rc;
  int num;
( g+ u) q* R7 D  double value;
6 F: O# n2 f0 c" x; `$ j' M };
struct largest lar1,lar2;
9 F! q' o% R$ I' V& q! _ int r=0,c=0;
! R$ n) F- Y, W2 q5 C double a1,a2,b1,b2,temp;</P>
<> for(i=1;i&lt;=num_a;i++) {
) {4 @: M0 q" ^2 ?  temp=temp_ab[1];
  for(j=1;j&lt;=num_b;j++)
   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
) d9 A; y& @4 I+ O+ ?  a1=a2=temp;
+ y3 H$ V3 ?9 m: q1 j6 j  for(j=1;j&lt;=num_b;j++)
   if(temp_ab[j]&lt;=a1) {
    a2=a1;
    a1=temp_ab[j];
* r4 H5 C& Z. ^$ N* L   }
3 j. v2 h% d0 O' K* F" W; A   else if(temp_ab[j]&lt;=a2) a2=temp_ab[j];
  r_penum=dabs(a1-a2);
}</P>
<> for(i=1;i&lt;=num_b;i++) {
  ~& G' {" e  ^- _8 A: x5 Q, C  temp=temp_ab[1];
4 m& K# H! m2 G& }( g; X! F4 i- u  for(j=1;j&lt;=num_a;j++)
   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
  b1=b2=temp;
7 v; q3 t" m% i) Q6 V4 F0 f  for(j=1;j&lt;=num_a;j++)  
) D$ [3 m. x1 J9 T/ l   if(temp_ab[j]&lt;=b1) {
    b2=b1;
    b1=temp_ab[j];
6 \( x3 ?' T# Y  }/ w   }
+ U' f+ k( t" r  w# ~; p( o! H   else if(temp_ab[j]&lt;=b2) b2=temp_ab[j];
8 Q! y2 J* T1 H( \% j  c_penum=dabs(b1-b2);
}
/*
- s- ?# D2 H+ l1 N; D for(i=1;i&lt;=num_a;i++) printf("pa%d=%lg ",i,r_penum);
4 m/ I4 G- ]/ A" O4 q2 U0 m putchar('\n');
8 r* R  i$ v$ \5 D+ ]7 N, d for(i=1;i&lt;=num_b;i++) printf("pb%d=%lg ",i,c_penum);
1 m3 Q4 L, X* r6 _' t3 o( L */
1 |7 J7 S; d3 S 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>
<> //考虑了有两个罚数相等的情况，大于两个相等只取其中两个进行比较
* e; t0 p& s2 [/ J3 r5 I6 U lar1.value=lar2.value=temp;
: ^2 N- v3 H% i lar1.num=lar2.num=1;
lar1.rc=lar2.rc='r';
& b3 j# d- y- Q- L( t for(i=1;i&lt;=num_a;i++)
, O; G4 o" W5 f" `  if(r_penum&gt;=lar1.value) {
   lar2=lar1;
   lar1.rc='r';
   lar1.num=i;
+ Q" I. i" r6 f3 {( }$ z5 f   lar1.value=r_penum;
  }
  else if(r_penum&gt;=lar2.value) {
5 [7 z6 m4 V8 ?, A   lar2.rc='r';
   lar2.num=i;
   lar2.value=r_penum;
  }</P>
9 i; H0 O6 i, \) D4 ]6 z<> for(i=1;i&lt;=num_b;i++)
  if(c_penum&gt;=lar1.value) {
2 v# L  F/ ^% W9 Y4 |4 ~6 u! h   lar2=lar1;
   lar1.rc='c';
   lar1.num=i;
* P4 ^' H! m' G3 G0 ^9 i   lar1.value=c_penum;
  }
7 f; G9 R8 t6 e  N- Q  else if(c_penum&gt;=lar2.value) {
, L1 S# i0 M* |   lar2.rc='c';
6 n8 g( ~0 u, Z) ^- U" M7 z/ ~7 c   lar2.num=i;
   lar2.value=c_penum;
% N/ Z6 D, ]3 b9 F& T  }</P>
<> if(lar1.value==lar2.value&amp;&amp;(lar1.num!=lar2.num||lar1.rc!=lar2.rc)) {
- r7 v. s  J) V8 c' A  if(lar1.rc=='r'&amp;&amp;lar2.rc=='r') {
. ?# |$ v+ w$ Z5 `8 m   temp=temp_ab[lar1.num][1];
) |7 Y+ t/ J) N+ ~   r=lar1.num;
      c=1;
8 k$ F& z0 x- ]- l2 m' E   for(i=1;i&lt;=num_b;i++) {
    if(temp_ab[lar1.num]&lt;temp) {
/ m& v; r. [  b( f* R" ^1 R     temp=temp_ab[lar1.num];
' E* M  g2 o# U" ]     r=lar1.num;
     c=i;
    }
3 G6 ?9 E0 H6 H( x1 u) [    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
4 U" U# }  K" C, m9 E. w6 i+ O     r=lar2.num;
     c=i;
2 I) n. B! B6 O% \2 ?; Q! m1 B    }
   }
  }
0 o& m: d. y* g4 K9 f$ K  if(lar1.rc=='c'&amp;&amp;lar2.rc=='c') {
   temp=temp_ab[1][lar1.num];
   r=1;
      c=lar1.num;
" f" `" L8 I2 {2 @   for(i=1;i&lt;=num_a-1;i++) {
' k9 {! A) A$ G0 a5 h) z5 z    if(temp_ab[lar1.num]&lt;temp) {
     temp=temp_ab[lar1.num];
     c=lar1.num;
& ?  B( {& f* H% b( H. M  `     r=i;
    }
9 t& ]1 S2 r+ h  X. F! Z    if(temp_ab[lar2.num]&lt;temp) {
2 E. P" ?* t6 S  ?$ B$ x     temp=temp_ab[lar2.num];
! Q4 b6 v3 y( T% _3 h     c=lar2.num;
* E7 d" \* s/ E2 n% x& g     r=i;
    }
   }
7 Z$ A' p# v0 v. n, v  }
, T9 r8 W/ m' j& F  if(lar1.rc=='r'&amp;&amp;lar2.rc=='c') {
   temp=temp_ab[lar1.num][1];
   r=lar1.num;
6 E0 N  y2 ?5 f      c=1;
   for(i=1;i&lt;=num_b;i++)
    if(temp_ab[lar1.num]&lt;temp) {
     temp=temp_ab[lar1.num];
     r=lar1.num;
2 X* Z4 k4 q) z* M     c=i;
& Z4 w" r3 d$ c9 H    }
: t: }/ L: @* L- u7 L. n: I   for(i=1;i&lt;=num_a;i++)
; m2 R9 J1 U7 O    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
" J& M9 p+ ^4 h     c=lar2.num;
. {) ]' Z/ V# W$ X2 R     r=i;
+ m1 E) {4 K- Q; A! P  n    }
/ p: I9 x$ S% T' \+ [0 }  }
  if(lar1.rc=='c'&amp;&amp;lar2.rc=='r') {
   temp=temp_ab[1][lar1.num];
% C! \  H5 l) \1 U( d. c& l   r=1;
+ C7 {5 J: G9 z* ^% R4 T+ [+ N! K      c=lar1.num;
: W2 W: N+ P% X6 l   for(i=1;i&lt;=num_b;i++)
7 V; M# _8 v- m# h! I, N9 A    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
     r=lar2.num;
8 Y0 Y: Y2 H: m- `7 b     c=i;
1 C$ G; P6 D  ~, a5 r    }
0 N  F( U. J. R- I  }. s   for(i=1;i&lt;=num_a;i++)
8 R# i' h- H& G) L8 {    if(temp_ab[lar1.num]&lt;temp) {
     temp=temp_ab[lar1.num];
     c=lar1.num;
. f2 b4 V) u; e! B2 E     r=i;
    }
  }
}
else {
0 b" q8 W3 G" B. A! |  if(lar1.rc=='r') {
/ H2 g' O2 c* L' J! M- @/ u# L   r=lar1.num;
$ f& T& \" Y4 X; E   c=1;
8 ~/ D  U* m% ^) o5 k   temp=temp_ab[lar1.num][1];
) f4 S* n8 C0 D   for(i=1;i&lt;=num_b;i++)
    if(temp_ab[lar1.num]&lt;temp) {
     c=i;
9 I% r; }" y! A) I. M     temp=temp_ab[lar1.num];
; `% G, B+ m4 |7 U4 ~% o6 E" N; p    }
  }
  else {
/ j3 d& C# G2 P! U9 l   r=1;
: G. r! n2 R+ B' c! V4 ]   c=lar1.num;
   temp=temp_ab[1][lar1.num];
4 k/ I8 b. n3 `   for(i=1;i&lt;=num_a;i++)
    if(temp_ab[lar1.num]&lt;temp) {
2 W' O6 E3 B% G- @# j6 _     r=i;
     temp=temp_ab[lar1.num];
  c( I; U7 M' w. \    }
0 r5 L1 d+ p0 S- ~  }
}
pbase[r][c]=1;
' p* d$ X) `4 K4 H& R% K& c if(temp_a[r]&gt;temp_b[c]) {
  base[r][c]=temp_b[c];
1 b( Z8 R4 i( d4 t  temp_a[r]=temp_a[r]-temp_b[c];
  temp_b[c]=0;
/ y" h1 k: `2 F* p# |  for(i=1;i&lt;=num_a;i++) temp_ab[c]=M;
& N2 v3 b8 S$ l# l4 b' I$ P }
7 |. ~3 W2 \7 @- b/ |3 t/ w3 [5 X else if(temp_a[r]&lt;temp_b[c]) {
) w2 Z- I; P& ]5 x  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]) {
  base[r][c]=temp_a[r];
- N7 ?. u; u- [; B1 @4 D  temp_a[r]=temp_b[c]=0;
7 I8 j6 O; W! r3 x/ Y0 f4 ^" z. b  for(i=1;i&lt;=num_a;i++) temp_ab[c]=M;
  for(i=1;i&lt;=num_b;i++) temp_ab[r]=M;
! t/ D7 V4 `2 Y8 t+ I" z2 ^  k=0;
  for(i=1;i&lt;=num_a;i++) if(temp_a!=0) k=1;
& J+ c4 _2 o+ _6 R  for(i=1;i&lt;=num_b;i++) if(temp_b!=0) k=1;
1 g& V; {0 B" E- N$ S) \7 g" m  if(k!=0) {
   k=0;
   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;
7 l! E. F6 q6 d2 }6 c2 @   else if(k==2) pbase[r][j]=1;
% v3 x& ?1 E: e: d, g  }
}
, I1 Q6 ?' R" C 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();
) s3 s- a- }& A}</P>
<>void computeuv() {
) ]6 Q. S4 Z. t% F) Y int i,j,k;
/ u: m# [: M& L' K' B9 S for(i=1;i&lt;=num_a;i++)
  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==1) {
    if(pu==1) {v[j]=ab[j]-u; pv[j]=1;}
: C) p% s& v' Y4 o* G2 q    if(pv[j]==1) {u=ab[j]-v[j]; pu=1;}
4 u& r" c- k- V6 o, D   }
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;
3 L; M+ q' {/ I* I* P if(k==1) computeuv();
}</P>
<>int check() {
int i,j,k,l;
7 ]  L* C8 P1 `& J3 z" s k=l=0;
for(i=1;i&lt;=num_a;i++)
  for(j=1;j&lt;=num_b;j++)
- @( @7 q: M0 Q& t1 y   if(pbase[j]==0) {
/ x; ?: |! G7 j5 q; O. g    base[j]=ab[j]-u-v[j];
4 i0 X7 i: H2 ^. i+ L8 E1 {    if(base[j]&lt;0) k=1;
    else if(base[j]==0) l=1;
   }
/* for(i=1;i&lt;=num_a;i++){
2 O5 }( |! b' {# Z  for(j=1;j&lt;=num_b;j++) printf("base %lg\t",base[j]);
8 [- H( ]2 y. p' w  putchar('\n');}
for(i=1;i&lt;=num_a;i++){
  Z' j" P, F  W1 d5 k, |  for(j=1;j&lt;=num_b;j++) printf("pbase %d\t",pbase[j]);
  putchar('\n');}
# X8 q6 W* a. ~7 v* H*/
0 r; @) s9 U8 Q4 x if(k==0&amp;&amp;l==0) {status=1; return 1;}
) ^5 j' `, K# M' Y else if(k==0&amp;&amp;l!=0) {status=-1; return 1;}
7 C0 l$ o/ G. G. j/ W3 F else return 0;
}</P>
6 G" y) r3 `; v3 U6 v, V! `/ {<>int circle(enum direction dir,struct element cir[],int *t) {
int i,j,k;
6 n% B. Q) }1 ]1 U, o+ X7 a /*
putchar('\n');
7 j% Z7 r6 L' ^% D for(i=1;i&lt;=*t;i++) printf("%d: r%d c%d\t",i, cir.r,cir.c);
putchar('\n');
*/
5 m8 K  L* M& s9 H7 y8 o if((*t)!=1&amp;&amp;cir[(*t)].r==cir[1].r&amp;&amp;cir[*t].c==cir[1].c) {
" r: n) d$ T# z/ f. _( t; _  t--;
  return 1;
, |0 n, W+ R3 @8 E4 b) H }
if(dir!=down) {
2 K4 ]: L, k9 x( [  k=0;
# v* L" S7 w* ~2 K8 s: j) h1 T' Q  for(i=cir[*t].r-1;i&gt;=1;i--)
  B; ^! `; w  j7 ?) B4 ]" T   if(pbase[cir[*t].c]==1||(i==cir[1].r&amp;&amp;cir[*t].c==cir[1].c)) {k=1; break;}
/ G9 T8 N: q3 y: O  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) {
   if(dir==up) cir[*t].value=0;
& i1 k9 ]2 S. M" Q# V, u   else cir[*t].value=1;
3 T" c0 s3 b( X5 t   (*t)++;
   cir[*t].r=i;
' g3 |) \& H# r! q# D3 V   cir[*t].c=cir[(*t)-1].c;
" j' l2 ~6 s( f2 A, M   if(circle(up,cir,t)) return 1;
4 A* ^/ E) w# m  }
}
if(dir!=up) {
8 i' ]4 `4 n* @  r, ]" C) S; d5 {  k=0;
' ?9 T8 }5 W8 s, b9 |/ H- g  for(i=cir[*t].r+1;i&lt;=num_a;i++)
1 N9 C1 m$ \+ M3 e$ R- x   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;
; ?: T: d: t: K2 B6 G  if(k==1) {
   if(dir==down) cir[*t].value=0;
" H7 S( A  k1 \/ p   else cir[*t].value=1;
   (*t)++;
   cir[*t].r=i;
   cir[*t].c=cir[(*t)-1].c;
   if(circle(down,cir,t)) return 1;
8 s1 I5 f/ r' b! a  }
}
if(dir!=right) {
. N1 t6 Q& G( X! n  k=0;
5 s3 k/ {7 v4 Z9 g0 Z% i  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;}
  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) {
: Q/ E8 _( i1 t/ o) _   if(dir==left) cir[*t].value=0;
   else cir[*t].value=1;
   (*t)++;
2 Y; c5 A- ]' q) T+ p- a   cir[*t].r=cir[(*t)-1].r;
   cir[*t].c=i;
; {& G% G2 `/ }" p   if(circle(left,cir,t)) return 1;
  }
" x) h' F+ `3 Y3 _) @ }
if(dir!=left) {
  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;
  if(k==1) {
3 ]9 k1 D" `* ^4 ?$ \  j0 A   if(dir==right) cir[*t].value=0;
   else cir[*t].value=1;
8 M% F' {- P4 `   (*t)++;
   cir[*t].r=cir[(*t)-1].r;
   cir[*t].c=i;
7 \+ [7 I1 Q( @! B0 w% n; m; j, d/ P   if(circle(right,cir,t)) return 1;
' z) I8 |$ G! ~- ?: ]% [( Y, Z  }
$ B* U" e$ Z# V4 ~ }
+ {  z$ T' x8 E. q6 k (*t)--;
+ _- i  `; b2 Y- A; P. ]* ` return 0;
: K; K! m5 X0 |; p) k3 \}</P>
" ^2 T* Q8 R6 h' v+ A- F( j, D<>void improve() {
int i,j,k,t;
$ ]* Z- C$ b5 p% x7 W: u 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;
computeuv();
% m, h* Q& l' o if(check()) return;
+ y8 i2 X6 l9 H/ {- T for(i=1;i&lt;=num_a;i++)
) O& G3 z7 t/ D9 H2 p7 h  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==0) break;
. S+ c6 v& L0 e- k+ F base_in.r=i;
base_in.c=j;
- @9 F( x- s6 d' r' ~- s. ?; ^( M base_in.value=base[j];</P>
! P8 F7 Z) S1 U, F- K5 w( {<> for(i=1;i&lt;=num_a;i++)
% p& [2 q# A" W( N7 Q3 F! A  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==0&amp;&amp;base[j]&lt;base_in.value) {
    base_in.r=i;
6 N6 g9 F3 M# J' s  @1 \! Q9 C. [    base_in.c=j;
    base_in.value=base[j];
   }</P>
<> t=1;
cir[t].r=base_in.r;
7 T) B5 o8 K- d* u9 |6 I8 v5 E cir[t].c=base_in.c;
& j4 x$ N; n% ?4 [, {7 {4 j cir[t].value=1;
if(!circle(mid,cir,&amp;t)) {
/ {0 B5 y, ?9 l( D$ U  printf("程序出错！按回车结束");
0 n- }) ]9 w( P/ r8 x* P  getchar();
  exit(0);
}
) J+ q1 @9 l2 G! L2 `+ l( p" h 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;
% x5 q4 r2 m, A! I* G) L4 [* J4 l8 \ base_out=cir;
base_out.value=base[cir.r][cir.c];
k=1;
. g; @6 U3 o' W for(i=1;i&lt;=t;i++)
$ k: H2 C4 f% o$ P# d  if(k%2==0&amp;&amp;cir.value==1&amp;&amp;base[cir.r][cir.c]&lt;base_out.value) {
% \& R6 B* D* \   base_out=cir;
6 p* v1 X1 H6 ?  X( U( N8 c   base_out.value=base[cir.r][cir.c];
" e; A# _0 ~3 H7 e   k++;
+ G: Z$ h+ q; y7 D* X# v  }
  else if(cir.value==1) k++;
base[cir[1].r][cir[1].c]=0;
k=1;
, g7 f( F. h$ M0 f for(i=1;i&lt;=t;i++) {
  if(k%2==1&amp;&amp;cir.value==1) {
   base[cir.r][cir.c]+=base_out.value;
   k++;
  }
  else if(k%2==0&amp;&amp;cir.value==1) {
   base[cir.r][cir.c]-=base_out.value;
   k++;
  }
}
pbase[base_out.r][base_out.c]=0;
pbase[base_in.r][base_in.c]=1;</P>
# d: U3 e& m5 C% P# \: K<> improve();
}</P>
! r3 l, X, R/ |8 I8 F$ o<>void output() {
int i,j;
" S+ V5 B% a8 `" e4 F/ {& O double sum=0;
3 Z, t6 Y/ `. r+ Y4 X printf("\n运量为：\n");
2 E( ~3 b  g1 ]' J- l+ ]1 z; K for(i=1;i&lt;=num_a;i++) {
, Y5 [  k) k, \) t# B. z$ P7 M: O1 F  putchar(' ');
  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==1) {
    printf("A%d-&gt;B%d:%lg\t",i,j,base[j]);
    sum+=base[j]*ab[j];
   }
9 g7 `6 `' P) Z7 B5 s5 X   else printf("A%d-&gt;B%d:0\t",i,j);
  putchar('\n');
}
1 o, R5 }1 R5 l9 B printf("\n最低总运费为：%lg\n",sum);
}
6 i5 ]0 K  L7 \! [8 k$ K</P>

zhongguohelin

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

enrique08

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

hzlhm

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

liunengwu

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