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

plgatc

<>/*************************************************************************
5 w5 K% c! f4 S; D2 A                         表上作业法解运输问题        

. B* P+ A$ Z4 E 编程环境：VC++6.0     
8 X+ f, c* ~! g9 y* Q 程序说明：
Vogel法求初始解，位势法检验是否最优，递归搜索闭回路改进解。
*************************************************************************/
#include &lt;stdio.h&gt;
3 P8 t: \( U0 h8 Q# F#include &lt;stdlib.h&gt;</P>
<>#define MAX 100
#define M 999999</P>
<>int status; //1唯一最优解，-1无穷多最优解</P>
, {: u7 P  T( D5 w2 w& l2 P<>int num_a,num_b;
double a[MAX],b[MAX],temp_a[MAX],temp_b[MAX];
- K# Z  l3 |$ `& ^, ndouble u[MAX],v[MAX],pu[MAX],pv[MAX];
; a3 b- Z8 Y. b( x; ldouble ab[MAX][MAX],temp_ab[MAX][MAX];
double base[MAX][MAX];
/ x, Q# ]$ R3 z5 v! mint pbase[MAX][MAX];
" H0 u3 M6 `$ Istruct element {
int r;
' i5 C' L! H5 T; O5 g$ P int c;
double value;
4 L& f0 _4 t. k$ d7 O, P};
) d8 s6 p/ |2 I4 D* jenum direction {mid,up,down,left,right};</P>
<>void create();
void banner();
% `7 C! j5 y& M4 }/ D3 W+ {double dabs(double d);
( n. }1 J  L* h) Nvoid findinit();
void computeuv();
int check();
int  circle(enum direction dir,struct element cir[],int *t);
9 B' p) v+ g  G8 Rvoid improve();
void output();</P>
<>void main() {
5 v4 M5 g' a$ R- N$ p* \ banner();
create();
printf("\n按回车确认后开始求解");
% c1 o  U/ Z- _, P" k getchar();
getchar();
$ I) b4 {3 t% u( e8 S8 H$ [ findinit();
improve();
8 Q- V( U7 q4 h' I# y switch(status) {
case 1:
& H! f8 P/ T+ x2 A$ o* ]: J0 a  output();
6 w" r# g! V7 D  N0 ?  puts("\n原问题有唯一最优解。\n");
  puts("\n按回车结束");
  getchar();
  exit(0);
case -1:
  output();
1 C* ^5 Y( z) C7 b, |( c( e5 u7 \& O  puts("\n原问题有无穷多最优解。\n");
6 @. R. U3 g5 }, X  puts("\n按回车结束");
  getchar();
7 }& i( W$ W* \* v  exit(0);
; H; w/ d* s9 e/ S1 ~ }
) u% N7 Z" W: r* r/ J# F8 g}</P>
, {0 N; S+ F! T* s3 j6 X<>void banner() {
printf("\t\t****************************************\n");
$ s, ]4 X$ Z, e3 {2 J printf("\t\t         表上作业法解运输问题\n");
4 U6 d! P* k7 D1 _) b8 G* V printf("\t\t                              Thunder\n");
printf("\t\t****************************************\n");
printf("\n");
}</P>
* A, ?; [* x7 B$ q/ J2 J. I$ B" c' i<>void create() {
* L# J/ M! D3 s2 S+ F  _ int i,j;
double sum_a,sum_b;
char confirm;
while(1) {
  printf("请输入产地个数：");
  scanf("%d",&amp;num_a);
  for(i=1;i&lt;=num_a;i++) {
! |  K: O; j' V( X/ C8 d   printf("A%d产量：",i);
2 g, l1 \5 E  ]/ J* Z' V   scanf("%lf",&amp;a);
' Y* a% m6 t; B2 \' ?$ G+ v) I  }
  for(i=1;i&lt;=num_a;i++) printf("A%d产量：%lg\t",i,a);
2 w( J9 G& q! ]; L; C' D  printf("\n正确吗？：(y/n)");
  getchar();
% u" _: {! y4 j* A& O  confirm=getchar();
  if (confirm=='y') break;
2 G( W, t, E# F1 S  else if(confirm=='n') continue;
: S/ h6 W# n8 k; z' {0 W- d# w }
" C1 ]) A* j/ ^3 V/ z# t( s while(1) {
  printf("\n请输入销地个数：");
  scanf("%d",&amp;num_b);
7 w& n  J+ P% d" g1 J  for(i=1;i&lt;=num_b;i++) {
- p- \1 l# W8 h5 e2 u/ J   printf("B%d销量：",i);
8 {3 e' F; q* x- o0 r   scanf("%lf",&amp;b);
  }
0 w' E/ Q. d5 l* k7 X( J# i4 G  for(i=1;i&lt;=num_b;i++) printf("B%d销量：%lg\t",i,b);
  printf("\n正确吗？：(y/n)");
  getchar();
0 W2 z# Q: J2 ]( V  confirm=getchar();
/ Z, u) G/ Z' M; e  if (confirm=='y') break;
  else if(confirm=='n') continue;
}
( I% S. w. f* ~. u. } putchar('\n');
9 P0 z2 k* ?( r( \: ? 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]);
6 }) m5 z3 E  n) g, h+ |, q  }
3 y0 M. S' c: {7 K" `  for(j=1;j&lt;=num_b;j++) printf("A%d到B%d：%lg\t",i,j,ab[j]);
  printf("\n正确吗？：(y/n)");
- K. v8 T* N: W. K. o  getchar();
5 @6 {# V- J; {  confirm=getchar();
  if(confirm=='n') i--;
7 ^& T2 u' O2 S. g  putchar('\n');
$ f- t8 s$ b: F2 m }
//处理产销不平衡的情况
. {$ M4 V9 d  [: a5 u$ I2 ?, [ sum_a=sum_b=0;
/ E' t0 G! n% {8 v$ z8 Q1 w for(i=1;i&lt;=num_a;i++) sum_a+=a;
4 o/ V5 }4 ~6 o3 s for(i=1;i&lt;=num_b;i++) sum_b+=b;</P>
<> printf("总产量：%lg\t总销量：%lg",sum_a,sum_b);
( l3 c9 o' `% I- l/ Q: C- v! L/ K- @& I' z if(sum_a==sum_b) printf("\t产销平衡。");
else if(sum_a&gt;sum_b) {
6 |5 D/ [, i; Q  printf("\t供大于求，增加假想销地B%d。\n",++num_b);
  b[num_b]=sum_a-sum_b;
" D  U* q, A: ]3 m0 ~' v  for(i=1;i&lt;=num_a;i++) ab[num_b]=0;
}
7 S% i" n( G$ Z: ~ else if(sum_a&lt;sum_b){
  printf("\t供不应求，增加假想产地A%d。\n",++num_a);
5 k2 G9 [' v" Q: w) |  a[num_a]=sum_b-sum_a;
: Y' a3 E% W" B) R9 V, C  `! {" P% q  for(i=1;i&lt;=num_b;i++) ab[num_a]=0;
}
- O3 |( x* ^2 j+ {2 S+ ?7 o5 w* q //求解前的准备
1 c3 F* U6 y! e6 c; }: P7 \% b4 Q for(i=1;i&lt;=num_a;i++)
+ I' ?: l- v( p3 c  for(j=1;j&lt;=num_b;j++)
( D9 ?, d' O+ P4 z$ X4 \. W+ Y   base[j]=pbase[j]=0;
9 N+ j7 ~" m$ f9 T for(i=1;i&lt;=num_a;i++) temp_a=a;
+ J% k. r1 f  e2 L. R 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];
* F7 g' Y0 F, y6 Z& g //回显问题
  r- E7 B2 b; J* Z) o# V printf("\n\n原问题为：\n\n");
   printf("产量：\n ");
% [- D/ G8 l: [/ i for(i=1;i&lt;=num_a;i++) printf("A%d:%lg\t",i,a);
printf("\n运量：\n ");
0 c1 P( V- o, W$ C  a for(i=1;i&lt;=num_b;i++) printf("B%d:%lg\t",i,b);
+ Y3 N3 N# k- z" v$ `% R. q printf("\n运价为：\n");
for(i=1;i&lt;=num_a;i++) {
$ x; W7 U2 F3 ]% l5 Q) x* p& e  putchar(' ');
8 \  p1 ^0 M$ t5 @' Y7 G# L' D  for(j=1;j&lt;=num_b;j++)
   printf("A%d-&gt;B%d:%lg\t",i,j,ab[j]);
  putchar('\n');
}
& t6 e) n1 j4 g1 s, \}</P>
, c8 A; I& ~! D( r* ?2 U) W<>double dabs(double d) {
8 _3 g1 v8 ~6 _6 E& b if(d&gt;=0) return d;
( v* _, C: T8 n) Y else return -d;
  `# @+ r3 W& u) Z) |1 s" D# {1 R}</P>
7 i  R# u8 P) O& J( m( S6 H/ m4 g3 _' u<>void findinit() {
: B$ D7 _0 A0 R% e" A, r int i,j,k;
double r_penum[MAX],c_penum[MAX];
, `6 ]* w- Z# k' h* ~) Q! t- G struct largest {
  char rc;
/ P" Z- E! @; h: m& {  int num;
  double value;
5 u) Y) q! w7 X8 X5 D7 }+ T4 H+ h. Y# Z6 s };
* B( g% C$ X( N5 o, I, R struct largest lar1,lar2;
int r=0,c=0;
5 w1 a) q# h# H9 k1 W: Z. h% c double a1,a2,b1,b2,temp;</P>
2 J  b* A  ?/ {% s<> for(i=1;i&lt;=num_a;i++) {
  temp=temp_ab[1];
3 _* R1 v# k/ v8 |  for(j=1;j&lt;=num_b;j++)
   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
' Q5 u' W1 N7 \  a1=a2=temp;
  for(j=1;j&lt;=num_b;j++)
   if(temp_ab[j]&lt;=a1) {
" g! Q& D( {) l* r    a2=a1;
    a1=temp_ab[j];
2 d# k$ g: S' R$ \8 }2 W   }
6 \1 h2 ?$ C' N: G4 v+ ~' K! L$ ]   else if(temp_ab[j]&lt;=a2) a2=temp_ab[j];
  r_penum=dabs(a1-a2);
1 j; S1 ~  K: r# l7 z }</P>
1 m5 C/ w- m# y# _- J$ b<> for(i=1;i&lt;=num_b;i++) {
  temp=temp_ab[1];
  for(j=1;j&lt;=num_a;j++)
: Z9 R0 @. O8 \* B9 ~   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
  b1=b2=temp;
9 {( p; P- d) m  for(j=1;j&lt;=num_a;j++)  
   if(temp_ab[j]&lt;=b1) {
! T* s0 f4 h# W& A3 T    b2=b1;
    b1=temp_ab[j];
6 _  `% G" o! v4 W   }
   else if(temp_ab[j]&lt;=b2) b2=temp_ab[j];
. y5 s2 n3 k2 w/ I  c_penum=dabs(b1-b2);
}
/*
for(i=1;i&lt;=num_a;i++) printf("pa%d=%lg ",i,r_penum);
putchar('\n');
for(i=1;i&lt;=num_b;i++) printf("pb%d=%lg ",i,c_penum);
*/
+ @) q; I5 S2 U temp=r_penum[1];
2 ?" K# a9 W! {1 Y 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>
<> //考虑了有两个罚数相等的情况，大于两个相等只取其中两个进行比较
lar1.value=lar2.value=temp;
5 [- A/ S$ x) Y, a lar1.num=lar2.num=1;
lar1.rc=lar2.rc='r';
for(i=1;i&lt;=num_a;i++)
( \2 P' x1 g0 D  if(r_penum&gt;=lar1.value) {
   lar2=lar1;
   lar1.rc='r';
9 G/ K1 h! J9 U3 }: S   lar1.num=i;
3 t$ r; t6 i& |. k# ]. N/ q   lar1.value=r_penum;
+ M. h& S5 o: @  M; R( s" `0 Z  }
  z) I. B# L+ E/ {/ {  else if(r_penum&gt;=lar2.value) {
   lar2.rc='r';
   lar2.num=i;
   lar2.value=r_penum;
  }</P>
<> for(i=1;i&lt;=num_b;i++)
7 F/ o/ W. D% ^  if(c_penum&gt;=lar1.value) {
   lar2=lar1;
# t( p0 N- }7 K2 L   lar1.rc='c';
   lar1.num=i;
   lar1.value=c_penum;
2 a6 q/ V: t% H7 k, N1 K  }
  w* U7 ]$ r7 ^( r. c; m  else if(c_penum&gt;=lar2.value) {
8 q' }' d* `- Z: d   lar2.rc='c';
   lar2.num=i;
! @2 m6 X/ a$ l1 O   lar2.value=c_penum;
  }</P>
<> if(lar1.value==lar2.value&amp;&amp;(lar1.num!=lar2.num||lar1.rc!=lar2.rc)) {
% w) T9 J% T$ w* E1 ?' s1 A: g" A  if(lar1.rc=='r'&amp;&amp;lar2.rc=='r') {
   temp=temp_ab[lar1.num][1];
+ e4 c0 ?: s# S3 ~, D   r=lar1.num;
      c=1;
   for(i=1;i&lt;=num_b;i++) {
  U: s. e4 V% g- d    if(temp_ab[lar1.num]&lt;temp) {
0 S- M- W9 K9 U6 A     temp=temp_ab[lar1.num];
3 B/ F+ K1 a2 v8 g. i: \1 `3 }     r=lar1.num;
     c=i;
8 G( `  l7 Z" v* [# ~4 @( L$ b    }
    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
     r=lar2.num;
6 Q0 i$ }) B0 M+ r4 x     c=i;
! v" M) O) x+ l% V- ~. X    }
   }
  }
- f$ `" P6 e4 C+ Y  if(lar1.rc=='c'&amp;&amp;lar2.rc=='c') {
3 m$ ?+ a% t) q0 m- Z! [7 ~9 u" n   temp=temp_ab[1][lar1.num];
   r=1;
      c=lar1.num;
. E# S5 P* y6 p) i4 j   for(i=1;i&lt;=num_a-1;i++) {
    if(temp_ab[lar1.num]&lt;temp) {
) C5 p& Z( Q; g! T7 e% _" D     temp=temp_ab[lar1.num];
     c=lar1.num;
     r=i;
    }
    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
1 p- a& L1 _* S( [' g7 I; z     c=lar2.num;
     r=i;
    }
   }
) J! ]% B1 ?7 W% l7 m4 d" g  }
2 X. ?: [8 r* [  if(lar1.rc=='r'&amp;&amp;lar2.rc=='c') {
- G( U3 }6 W7 W1 B2 q5 e3 T   temp=temp_ab[lar1.num][1];
. R. i8 O+ ?: P9 H   r=lar1.num;
      c=1;
* q" G* _& h  b: e9 O6 Q, g   for(i=1;i&lt;=num_b;i++)
    if(temp_ab[lar1.num]&lt;temp) {
% Q; t4 h; i* k* ~( R) O% F     temp=temp_ab[lar1.num];
2 j8 A: k+ [1 o     r=lar1.num;
2 y) I* V3 X4 Y& w  h+ {! V" c# W     c=i;
0 b2 d: n! o9 t  d# |, k4 |    }
2 V( E' B, `% k   for(i=1;i&lt;=num_a;i++)
% o; v' q- H; o4 r4 p    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
8 c) B) ^& L' c- h     c=lar2.num;
' x9 G! M$ z7 B; }# v# f     r=i;
    }
  }
8 M1 T% l* ^' S5 }+ _4 P  if(lar1.rc=='c'&amp;&amp;lar2.rc=='r') {
0 l% {( c; [6 G* @; v% r   temp=temp_ab[1][lar1.num];
   r=1;
% ~6 A8 ~* x' p) ~      c=lar1.num;
% a/ f/ n, A/ P& _8 B% ]3 h   for(i=1;i&lt;=num_b;i++)
* H& Z# H# a  F- g) `    if(temp_ab[lar2.num]&lt;temp) {
2 @; b4 C4 i9 D, [3 D" o     temp=temp_ab[lar2.num];
4 h4 j  Z/ n2 Z8 L! b6 Y' l% t$ C     r=lar2.num;
     c=i;
- z8 `. ^# D" ^8 ]) U: }    }
   for(i=1;i&lt;=num_a;i++)
    if(temp_ab[lar1.num]&lt;temp) {
* J4 S1 k8 s/ s     temp=temp_ab[lar1.num];
# G# i# {- r" g  R     c=lar1.num;
- q$ x  k* t0 [0 D: T     r=i;
) @; l' M4 O8 z6 v& _. A    }
0 S; J! j* A# U* E  }
}
  V! w' Q: s9 d7 F& u) E& G else {
  if(lar1.rc=='r') {
6 D- c- A( G, n, ~5 Z   r=lar1.num;
6 F( G( D* G! I' O3 W   c=1;
   temp=temp_ab[lar1.num][1];
   for(i=1;i&lt;=num_b;i++)
    if(temp_ab[lar1.num]&lt;temp) {
- h( t: p1 _5 A. w2 k! ?3 q( f     c=i;
# d5 ~3 D# V- S: x& @3 ^4 C     temp=temp_ab[lar1.num];
. E% w7 F; s1 d/ X# s    }
" C8 A. y: \  U; d  @8 I( `6 B9 ~' M  }
2 Q! K7 t+ M8 q  else {
   r=1;
% x; H8 f4 H0 p5 v3 J  ?, |   c=lar1.num;
   temp=temp_ab[1][lar1.num];
   for(i=1;i&lt;=num_a;i++)
; Z0 c' D+ y" W! T( l$ b5 p    if(temp_ab[lar1.num]&lt;temp) {
     r=i;
     temp=temp_ab[lar1.num];
2 `2 _, D8 T8 V4 i7 I3 \6 l    }
  }
# ^4 v7 ~7 W1 C- ]  b2 J9 B0 l }
pbase[r][c]=1;
8 ~0 W, n) U+ }" c if(temp_a[r]&gt;temp_b[c]) {
0 D$ |2 X% D' ~/ D4 _) v- l4 j  base[r][c]=temp_b[c];
3 W1 [5 i% T+ e4 L# \; y  temp_a[r]=temp_a[r]-temp_b[c];
  temp_b[c]=0;
  for(i=1;i&lt;=num_a;i++) temp_ab[c]=M;
0 r: w& t; c# K7 k }
else if(temp_a[r]&lt;temp_b[c]) {
  base[r][c]=temp_a[r];
  temp_b[c]=temp_b[c]-temp_a[r];
# d6 @% g7 T: j- h$ [9 S  temp_a[r]=0;
  for(i=1;i&lt;=num_b;i++) temp_ab[r]=M;
}
* ?7 f3 x, G. w0 {1 K" c, W else if(temp_a[r]==temp_b[c]) {
  base[r][c]=temp_a[r];
  temp_a[r]=temp_b[c]=0;
6 L; |& o7 C, [0 g$ _& t" S+ g  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;
8 T+ t5 V1 Z8 Q" c  if(k!=0) {
: t. j. g) K, X   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;}
# i" w& S( c. v# i) q) l4 e   if(k==1) pbase[c]=1;
2 g' y( u$ X2 @2 J. ^4 G3 d* G/ L   else if(k==2) pbase[r][j]=1;
  }
6 C7 A% R7 `; A+ z. i; [% v }
, f, B" X! B( S& b k=0;
: Q2 I0 Y" ]0 D% S) R4 t3 i for(i=1;i&lt;=num_a;i++) if(temp_a!=0) k=1;
- {8 R$ G0 \7 x( r3 l9 P for(i=1;i&lt;=num_b;i++) if(temp_b!=0) k=1;
if(k==0) return;
& n* Z2 m6 i+ t1 S5 m findinit();
" `! |, R5 z3 K. k2 |( Q- f  Y}</P>
<>void computeuv() {
+ e" H% s! u: i0 W9 c int i,j,k;
  U% t4 R! S1 {4 `( @ for(i=1;i&lt;=num_a;i++)
: d6 ^) `- ~& Z" f$ K  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==1) {
    if(pu==1) {v[j]=ab[j]-u; pv[j]=1;}
" @. j, p$ T+ r% r    if(pv[j]==1) {u=ab[j]-v[j]; pu=1;}
   }
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;
/ t3 E4 f' Y8 J( q$ U if(k==1) computeuv();
( x) Q5 h/ N3 V6 }, o1 Z}</P>
. Q9 y6 F8 f' b; P<>int check() {
int i,j,k,l;
$ q2 y$ z3 C7 x) k0 U, p* } k=l=0;
$ s$ ]0 j8 r3 ?) \; |$ w for(i=1;i&lt;=num_a;i++)
/ N, D# ^0 V( u3 B) f  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==0) {
    base[j]=ab[j]-u-v[j];
5 A, p8 t' @* T/ s' r9 W    if(base[j]&lt;0) k=1;
& v. B* \) O, `) F' a- }) b3 W    else if(base[j]==0) l=1;
4 W6 g( m$ d4 ]0 C7 Q; M   }
/* for(i=1;i&lt;=num_a;i++){
  for(j=1;j&lt;=num_b;j++) printf("base %lg\t",base[j]);
* s8 c$ a7 g, A  putchar('\n');}
: @1 q- I% Y7 u! L1 ` for(i=1;i&lt;=num_a;i++){
5 ?1 b& F: x0 m  for(j=1;j&lt;=num_b;j++) printf("pbase %d\t",pbase[j]);
  putchar('\n');}
6 j9 y. u" x4 o0 N: E+ g: M*/
& q0 N# v% {* S if(k==0&amp;&amp;l==0) {status=1; return 1;}
else if(k==0&amp;&amp;l!=0) {status=-1; return 1;}
else return 0;
}</P>
  v$ x4 P1 I* R0 f8 U- B  T- R<>int circle(enum direction dir,struct element cir[],int *t) {
int i,j,k;
" A+ |  p* a& C& B! ^ /*
putchar('\n');
for(i=1;i&lt;=*t;i++) printf("%d: r%d c%d\t",i, cir.r,cir.c);
putchar('\n');
*/
$ ~' m2 h) @: L$ H8 D8 v1 [ if((*t)!=1&amp;&amp;cir[(*t)].r==cir[1].r&amp;&amp;cir[*t].c==cir[1].c) {
/ g. f' S1 a5 e4 k) z1 z9 P2 {' _  t--;
  return 1;
, P6 H# f6 p: D3 e: u) O- n }
if(dir!=down) {
( j$ T" H1 p- M7 X+ c  k=0;
  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;}
, W! y% q5 A/ p( {$ S  for(j=2;j&lt;=*t;j++) if(i==cir[j].r&amp;&amp;cir[*t].c==cir[j].c) k=0;
) N' x! A# M# w5 d! s! _  if(k==1) {
   if(dir==up) cir[*t].value=0;
   else cir[*t].value=1;
2 L1 _, X; n; Z9 }) t   (*t)++;
   cir[*t].r=i;
* b  D7 S3 Y# V2 g( x1 S   cir[*t].c=cir[(*t)-1].c;
4 @1 L% X0 [5 \1 t, d7 I' p, Z+ j; `7 ?   if(circle(up,cir,t)) return 1;
; u3 h( ?  g7 T8 F  }
}
if(dir!=up) {
( ^$ A9 {9 U+ q- B/ Q4 d  k=0;
  for(i=cir[*t].r+1;i&lt;=num_a;i++)
7 q+ G+ T1 q2 Q5 Q0 [$ _: D   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;
3 u% x9 d9 z) t7 b( @) W$ h9 W  if(k==1) {
   if(dir==down) cir[*t].value=0;
/ p& n5 e! ?; K   else cir[*t].value=1;
; B  `( Z# y* W! g" E- U# _   (*t)++;
   cir[*t].r=i;
& @6 D0 S& k: {8 l   cir[*t].c=cir[(*t)-1].c;
/ c9 S/ o5 E" V" ?$ p1 s2 {6 B. W# u   if(circle(down,cir,t)) return 1;
  }
% W0 V6 O8 q8 D }
+ Z9 m( x) y/ H% ^; h if(dir!=right) {
# y  F( U' j# z  |, N) U5 r$ w3 e" w  k=0;
4 D* Q6 ~3 j$ n# T# y7 N+ O9 `! \  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;}
! e$ }0 A; `5 F, I  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) {
" S: Y+ r4 e8 ?1 d% f% P0 T   if(dir==left) cir[*t].value=0;
   else cir[*t].value=1;
   (*t)++;
   cir[*t].r=cir[(*t)-1].r;
7 [% i, t/ O2 V% }   cir[*t].c=i;
% y$ `0 n# i* F4 J! k4 u& q+ l   if(circle(left,cir,t)) return 1;
* D2 o3 V  G3 B( D  }
}
if(dir!=left) {
$ F" R  B# }  w+ c& f$ l0 ?* B: H  k=0;
5 S/ [; C& e$ z$ X2 g3 {  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;}
5 ?' P- [; Q0 s6 z" P7 @  j  for(j=2;j&lt;=*t;j++) if(cir[*t].r==cir[j].r&amp;&amp;i==cir[j].c) k=0;
4 B8 j" C2 H1 L, b4 T  if(k==1) {
   if(dir==right) cir[*t].value=0;
   else cir[*t].value=1;
, Q% J+ P+ h2 X9 M+ s5 i) K   (*t)++;
7 g% G9 L! r& Z   cir[*t].r=cir[(*t)-1].r;
) n/ A/ a3 ^# ?8 p  p   cir[*t].c=i;
   if(circle(right,cir,t)) return 1;
6 P* |  P2 @: g  x  }
}
(*t)--;
return 0;
}</P>
7 `" H, v. T2 d! J  H! C) K* `" x" h<>void improve() {
6 x4 n" T1 {+ S7 g' V  Z int i,j,k,t;
. G, B; U8 C, m( o- b+ W7 o struct element base_in,base_out,cir[2*MAX+1];</P>
! \  x# A+ e7 x" o- l) e( V. x* \9 C<> 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();
if(check()) return;
for(i=1;i&lt;=num_a;i++)
$ R9 k9 A* p. C0 c3 w3 p* }  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==0) break;
' _2 B6 h( A% g, W+ x* L- C* Q base_in.r=i;
7 m& p5 L2 b2 a2 ~! H2 Z9 y3 D base_in.c=j;
2 v1 `3 d. ?0 ]. Q base_in.value=base[j];</P>
<> for(i=1;i&lt;=num_a;i++)
6 E1 S! C6 P- G4 J  for(j=1;j&lt;=num_b;j++)
  G6 G) L) G0 E$ p   if(pbase[j]==0&amp;&amp;base[j]&lt;base_in.value) {
4 a8 h* @& ?0 [* D    base_in.r=i;
  Z! C. O  ^) d* U& v  l1 v    base_in.c=j;
) f2 O; P+ k- \" m* G' D8 y6 s- {5 k0 v    base_in.value=base[j];
   }</P>
7 ]$ z* M# k5 j7 @. B/ a! V" D<> t=1;
! N9 }" Z/ h% L7 A* s cir[t].r=base_in.r;
# [) a5 `* C. [2 W4 }! u cir[t].c=base_in.c;
cir[t].value=1;
if(!circle(mid,cir,&amp;t)) {
5 H( v& V' r3 o  printf("程序出错！按回车结束");
- Z" G2 v% x' R0 \( D' {3 P8 h  getchar();
6 u' z+ H3 C7 W& K  W  exit(0);
% {5 |& K) v& f7 }, `: ^$ Q; v }
t--;
// for(i=1;i&lt;=t;i++) printf("%d:r%d c%d v%lg\t",i,cir.r,cir.c,cir.value);
+ e; K" c, S3 y; ~! I" ]# u// putchar('\n');</P>
( ^; C! C- H8 d0 @( Q9 |<> for(i=2;i&lt;=t;i++) if(cir.value==1) break;
base_out=cir;
. v8 m, e) M) ?- @5 K base_out.value=base[cir.r][cir.c];
k=1;
for(i=1;i&lt;=t;i++)
. _# ?, [* J( v% K" S  if(k%2==0&amp;&amp;cir.value==1&amp;&amp;base[cir.r][cir.c]&lt;base_out.value) {
, j8 x# p! k* I1 ], H( K( y9 p   base_out=cir;
. B3 d) o4 z% Q+ `: ^   base_out.value=base[cir.r][cir.c];
   k++;
2 Y& `6 G& y  O5 j: |0 Q! U9 a  }
  else if(cir.value==1) k++;
base[cir[1].r][cir[1].c]=0;
4 q$ H6 i) c! S; [+ G9 \ k=1;
! w6 e2 q* I) P+ r. [ 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++;
; W& j( g! x8 i$ R  C$ v0 K1 u/ L' C8 d  }
  else if(k%2==0&amp;&amp;cir.value==1) {
   base[cir.r][cir.c]-=base_out.value;
   k++;
9 _! t4 ]. Q/ p4 A: x+ f. N  }
$ |+ e" K* b" l) R% h" Q }
pbase[base_out.r][base_out.c]=0;
pbase[base_in.r][base_in.c]=1;</P>
<> improve();
}</P>
<>void output() {
int i,j;
  O/ ?0 r7 |/ g double sum=0;
printf("\n运量为：\n");
+ U5 A8 q# |8 } for(i=1;i&lt;=num_a;i++) {
, S$ g* |. V" W! R9 h; e, s  putchar(' ');
  w/ o) P5 N, ?3 }4 P& m1 u3 l  for(j=1;j&lt;=num_b;j++)
( t! p% Y- d* D2 I# @   if(pbase[j]==1) {
    printf("A%d-&gt;B%d:%lg\t",i,j,base[j]);
    sum+=base[j]*ab[j];
   }
, ?  r+ R: a7 j. s. O4 z# i   else printf("A%d-&gt;B%d:0\t",i,j);
  putchar('\n');
1 V6 |0 N, W2 e) k- S/ j }
# H# x  `1 x4 S4 l' e$ D4 x" e* v printf("\n最低总运费为：%lg\n",sum);
}
% {- ]& i5 j$ s1 t# h1 F</P>

zhongguohelin

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

enrique08

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

hzlhm

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

liunengwu

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