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

plgatc

<>/*************************************************************************
                         表上作业法解运输问题        
; }% }( _3 j1 ?9 A
编程环境：VC++6.0     
程序说明：
Vogel法求初始解，位势法检验是否最优，递归搜索闭回路改进解。
; j: [. |5 V1 W *************************************************************************/
#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;</P>
<>#define MAX 100
8 S% R6 A8 k" T5 @+ i) e#define M 999999</P>
<>int status; //1唯一最优解，-1无穷多最优解</P>
7 [6 e1 ^) p6 `" }) l: C4 G<>int num_a,num_b;
, L! ]: R7 i: X0 `4 ?; [$ n& o9 ldouble a[MAX],b[MAX],temp_a[MAX],temp_b[MAX];
double u[MAX],v[MAX],pu[MAX],pv[MAX];
; J+ b# ~% P" Z* E4 c) Z" C" `double ab[MAX][MAX],temp_ab[MAX][MAX];
double base[MAX][MAX];
int pbase[MAX][MAX];
struct element {
4 \- I5 P' O) _* Y int r;
int c;
double value;
* @8 {1 C8 y$ d6 C0 f4 x4 A% R};
enum direction {mid,up,down,left,right};</P>
: u  W+ A/ t$ f<>void create();
" O: |9 B/ Y5 g, s, e3 V2 @5 Lvoid banner();
double dabs(double d);
void findinit();
void computeuv();
int check();
int  circle(enum direction dir,struct element cir[],int *t);
void improve();
. @4 W4 }1 n* ~$ R( o6 xvoid output();</P>
: @) |2 M2 M# ^<>void main() {
banner();
' N* }! d4 Y: ~, i' F$ J create();
printf("\n按回车确认后开始求解");
getchar();
getchar();
findinit();
* j' Q- t/ g0 P& d: { improve();
switch(status) {
case 1:
  output();
; B/ X2 ~) X5 ~5 X  s  puts("\n原问题有唯一最优解。\n");
* t7 p7 G' t; Q# d- e6 n; \* g  puts("\n按回车结束");
2 |2 ]0 ?6 k5 b* n. H$ U  getchar();
  exit(0);
) |) u8 r5 Z1 W case -1:
  output();
  puts("\n原问题有无穷多最优解。\n");
+ r4 _. V# Z9 v" ^* D  puts("\n按回车结束");
& A  x, Z% F' p  getchar();
  exit(0);
}
}</P>
5 F* ~4 C. ?) c( f- x( N6 _2 T( T<>void banner() {
. S& U( |/ |" m) L, ^1 Y printf("\t\t****************************************\n");
! ~% i0 {7 b* u printf("\t\t         表上作业法解运输问题\n");
printf("\t\t                              Thunder\n");
" T" u0 S4 u' U; t, s printf("\t\t****************************************\n");
printf("\n");
7 V& Y' M1 s+ J9 D3 ~}</P>
<>void create() {
2 q" ^: N6 Z  Y) D! ^% u3 D0 _ int i,j;
double sum_a,sum_b;
* Z: \: q+ n4 |. D char confirm;
while(1) {
  W: k6 A& `  R, H4 u# U  printf("请输入产地个数：");
  scanf("%d",&amp;num_a);
  for(i=1;i&lt;=num_a;i++) {
   printf("A%d产量：",i);
   scanf("%lf",&amp;a);
  }
- O8 Q1 Q* n8 r* r# V* f9 @; U  for(i=1;i&lt;=num_a;i++) printf("A%d产量：%lg\t",i,a);
* Z+ K: e' |& j# T" y7 h  printf("\n正确吗？：(y/n)");
# m, D, }- L/ w, b! U  getchar();
  d: a+ a% ~" D7 N4 S( ]# d  confirm=getchar();
8 O; l, P+ [8 M9 B4 F  if (confirm=='y') break;
  else if(confirm=='n') continue;
$ T" ^" K6 }5 l+ C }
4 Z0 C( b* c7 a# |; `) w0 |" @ while(1) {
  printf("\n请输入销地个数：");
: Q- K' d+ l/ d6 K& ?  scanf("%d",&amp;num_b);
$ R8 X; y- d# V3 e  for(i=1;i&lt;=num_b;i++) {
; L# ~: Y3 s# l1 i  }+ l% C2 l   printf("B%d销量：",i);
   scanf("%lf",&amp;b);
) O$ A* u+ ]8 ~8 i; l/ U  }
$ C' v: m% y8 s/ z  for(i=1;i&lt;=num_b;i++) printf("B%d销量：%lg\t",i,b);
  printf("\n正确吗？：(y/n)");
  getchar();
  confirm=getchar();
  if (confirm=='y') break;
  else if(confirm=='n') continue;
  M: L/ [2 U; V }
0 H& s- Y& j" k' I9 g' D1 C7 A putchar('\n');
for(i=1;i&lt;=num_a;i++) {
  for(j=1;j&lt;=num_b;j++) {
+ M) c$ [; b. k   printf("A%d到B%d运价：",i,j);
! e9 h( V# z& Q0 j   scanf("%lf",&amp;ab[j]);
3 f7 q* u$ O* `) f7 W1 x8 T& M  }
  for(j=1;j&lt;=num_b;j++) printf("A%d到B%d：%lg\t",i,j,ab[j]);
" D0 k- Q9 v7 c0 g: [% l  printf("\n正确吗？：(y/n)");
  getchar();
5 w! Z6 r& ?; v8 X  confirm=getchar();
  if(confirm=='n') i--;
( `. ~2 ^7 R- B  putchar('\n');
7 S- J* D  P9 T% Z6 d% b }
//处理产销不平衡的情况
9 T' r: C8 I# u, x; e. S* w sum_a=sum_b=0;
8 W8 H, G6 R2 F  e! Z9 _6 K for(i=1;i&lt;=num_a;i++) sum_a+=a;
for(i=1;i&lt;=num_b;i++) sum_b+=b;</P>
1 ?2 n  i* e: T( t9 H5 ]<> 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);
6 G+ c/ @! F) H/ m% p. t3 F  b[num_b]=sum_a-sum_b;
  for(i=1;i&lt;=num_a;i++) ab[num_b]=0;
}
, U8 N+ J7 w0 G else if(sum_a&lt;sum_b){
  printf("\t供不应求，增加假想产地A%d。\n",++num_a);
* r  b0 t7 F2 y( l* Y) _" m1 X  a[num_a]=sum_b-sum_a;
7 G' r4 A* r% U. A6 F6 w  for(i=1;i&lt;=num_b;i++) ab[num_a]=0;
}
//求解前的准备
for(i=1;i&lt;=num_a;i++)
- @3 [% {2 t8 k* Y' F% w2 t- h6 s" D) |  for(j=1;j&lt;=num_b;j++)
   base[j]=pbase[j]=0;
" k6 |0 b& U/ E+ H for(i=1;i&lt;=num_a;i++) temp_a=a;
5 k, j9 Z+ a# e4 L! B for(i=1;i&lt;=num_b;i++) temp_b=b;
for(i=1;i&lt;=num_a;i++)
% k+ l6 V2 ~6 _* M. B) l- H8 Q7 A for(j=1;j&lt;=num_b;j++) temp_ab[j]=ab[j];
: u, ^4 \  ~, W! m; _0 A //回显问题
printf("\n\n原问题为：\n\n");
3 ^3 L* b9 x7 |% v' \0 t2 J- T   printf("产量：\n ");
, m' M% l, w4 {. e& K! F" K; d( b 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);
% l" K; @" o7 X" c" s printf("\n运价为：\n");
for(i=1;i&lt;=num_a;i++) {
1 ^" p8 Z# V$ q8 X) U; |0 `% y  putchar(' ');
; t5 L* A! N7 }0 H3 n/ ?7 `- i  for(j=1;j&lt;=num_b;j++)
   printf("A%d-&gt;B%d:%lg\t",i,j,ab[j]);
( s$ T% j1 W* |7 c4 i  putchar('\n');
/ J8 ^$ F( g$ v8 A  V5 b3 b }
& X0 A5 D; c  B$ j  P( D}</P>
<>double dabs(double d) {
0 I+ y- S% ?. s if(d&gt;=0) return d;
. A; `. ?- `+ x6 y( S9 v else return -d;
& y; d, r2 ], _! U' Z+ B, A( y}</P>
% ^9 H( ]) K1 P* v6 H. |6 x<>void findinit() {
int i,j,k;
double r_penum[MAX],c_penum[MAX];
struct largest {
1 E6 N; }  y5 j' ], N& |' j7 F0 Y  char rc;
# b6 V; {( R( ^6 e. d: `. A  int num;
  double value;
};
struct largest lar1,lar2;
+ b* u1 E4 g! v& ?/ x int r=0,c=0;
. o/ @( T4 l8 j9 V' [# A. T double a1,a2,b1,b2,temp;</P>
<> for(i=1;i&lt;=num_a;i++) {
  temp=temp_ab[1];
3 O1 F, b' c7 p0 s& ?8 r! E9 M  for(j=1;j&lt;=num_b;j++)
   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
& W+ g4 Q; l7 E" k1 \6 d  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];
  r_penum=dabs(a1-a2);
}</P>
( B6 i5 Q/ T* F<> for(i=1;i&lt;=num_b;i++) {
  temp=temp_ab[1];
  for(j=1;j&lt;=num_a;j++)
   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
: ]) ~1 q3 S4 |5 c7 M0 s  b1=b2=temp;
& T+ m( A+ ^. n3 b2 m% v3 X' q  for(j=1;j&lt;=num_a;j++)  
   if(temp_ab[j]&lt;=b1) {
    b2=b1;
( C. S5 u- G6 e/ e3 I! f    b1=temp_ab[j];
   }
, Y  H3 C& g8 C+ Z) P" M6 M" J   else if(temp_ab[j]&lt;=b2) b2=temp_ab[j];
2 B/ }7 O% m- T4 o% N& d% D' Y2 J  c_penum=dabs(b1-b2);
}
/*
for(i=1;i&lt;=num_a;i++) printf("pa%d=%lg ",i,r_penum);
putchar('\n');
6 e4 F+ ]+ V: @+ j# {8 h% L for(i=1;i&lt;=num_b;i++) printf("pb%d=%lg ",i,c_penum);
*/
  u9 E7 A0 T2 B& m temp=r_penum[1];
for(i=1;i&lt;=num_a;i++) if(r_penum&lt;temp) temp=r_penum;
6 j8 b9 R; S1 U  H- `- k for(i=1;i&lt;=num_b;i++) if(c_penum&lt;temp) temp=c_penum;</P>
<> //考虑了有两个罚数相等的情况，大于两个相等只取其中两个进行比较
lar1.value=lar2.value=temp;
) ?, f$ O/ X- e' ]1 P# N% F lar1.num=lar2.num=1;
lar1.rc=lar2.rc='r';
for(i=1;i&lt;=num_a;i++)
  if(r_penum&gt;=lar1.value) {
  W1 k9 F+ |3 E2 B   lar2=lar1;
: o; \) a5 J, \& M# J( }   lar1.rc='r';
   lar1.num=i;
   lar1.value=r_penum;
  }
  else if(r_penum&gt;=lar2.value) {
( q+ d6 z% F- N# t5 A; c8 c4 n   lar2.rc='r';
6 v7 N; @* C& q0 I   lar2.num=i;
6 L7 v  W7 s" F- F1 s3 B   lar2.value=r_penum;
  }</P>
" j! X# z2 T( H/ R<> for(i=1;i&lt;=num_b;i++)
  if(c_penum&gt;=lar1.value) {
   lar2=lar1;
3 c9 C2 D0 ^( T: [& p/ f" v& ~( U   lar1.rc='c';
8 S) N" o' G: g7 Y% a9 l4 g2 Z   lar1.num=i;
2 p: i  U) u* v! B/ V+ ]) b9 [3 m. {   lar1.value=c_penum;
  }
  else if(c_penum&gt;=lar2.value) {
   lar2.rc='c';
- Z3 ]' B6 g: f" B3 {8 X   lar2.num=i;
   lar2.value=c_penum;
  }</P>
2 L8 R$ l0 _3 a; M, {( w<> if(lar1.value==lar2.value&amp;&amp;(lar1.num!=lar2.num||lar1.rc!=lar2.rc)) {
: q8 M" d) c: V" E* k8 W/ J$ V  if(lar1.rc=='r'&amp;&amp;lar2.rc=='r') {
' F" q; u) K( p, F8 _" L   temp=temp_ab[lar1.num][1];
; n6 n* `: `' R4 H   r=lar1.num;
/ }* H' ~; B6 a: M7 E/ r7 E      c=1;
' s" n2 P/ |+ R- c5 H1 n   for(i=1;i&lt;=num_b;i++) {
8 S" d* ^- |# D9 R1 t: ^    if(temp_ab[lar1.num]&lt;temp) {
     temp=temp_ab[lar1.num];
3 K# L3 t' _, p! @/ m     r=lar1.num;
9 ^( O+ J5 U$ S     c=i;
    }
    if(temp_ab[lar2.num]&lt;temp) {
3 Y* s  e$ x0 t+ a5 R$ L     temp=temp_ab[lar2.num];
     r=lar2.num;
( T. z/ v9 I/ t0 E/ D' _     c=i;
    }
   }
. d" p1 \% Q7 _, L" b1 C  }
  if(lar1.rc=='c'&amp;&amp;lar2.rc=='c') {
   temp=temp_ab[1][lar1.num];
3 [! L! U" @: M9 C$ A   r=1;
      c=lar1.num;
   for(i=1;i&lt;=num_a-1;i++) {
    if(temp_ab[lar1.num]&lt;temp) {
     temp=temp_ab[lar1.num];
8 E8 r$ ]. D2 Z- z+ z, R     c=lar1.num;
     r=i;
+ ^# `, K4 ~- M0 o2 C    }
4 Q8 k) W" Q# L3 f1 `    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
5 p8 k# m% Q$ y" H     c=lar2.num;
1 Y% D0 l0 A8 e$ R0 G7 Z     r=i;
    }
   }
  }
  if(lar1.rc=='r'&amp;&amp;lar2.rc=='c') {
" c0 m- u5 t# c0 C" X5 Q( h8 z  z   temp=temp_ab[lar1.num][1];
   r=lar1.num;
1 c. I# w9 _5 C" A; `1 t/ a2 Q      c=1;
$ a5 K" L; U- M) ~, Z   for(i=1;i&lt;=num_b;i++)
    if(temp_ab[lar1.num]&lt;temp) {
     temp=temp_ab[lar1.num];
0 t8 {( {+ d3 @* |( ?1 X  I     r=lar1.num;
     c=i;
    }
   for(i=1;i&lt;=num_a;i++)
    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
) S2 L8 ?/ @1 x6 e' t* G# K" n     c=lar2.num;
' b& g& R" ]* E4 e     r=i;
- T- r% n& i' z& a1 S1 p7 e" a3 f    }
! @! `! v% e7 x7 P0 l, J  }
  if(lar1.rc=='c'&amp;&amp;lar2.rc=='r') {
   temp=temp_ab[1][lar1.num];
5 s$ @) Z' u$ u! T: L  ]1 Z. Z   r=1;
      c=lar1.num;
0 u2 C: O( p0 [* e# v   for(i=1;i&lt;=num_b;i++)
/ i; j1 x- {1 k    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
     r=lar2.num;
     c=i;
    }
   for(i=1;i&lt;=num_a;i++)
. e& w. Y. k4 t4 b& e' u- h! f$ Z# V    if(temp_ab[lar1.num]&lt;temp) {
9 ~/ |& O8 }& |+ O     temp=temp_ab[lar1.num];
' G$ k2 c3 p5 b9 C     c=lar1.num;
     r=i;
  ?" o8 y/ Y9 H  N0 d8 u    }
! ~- L$ a! E% I: e" ~, c7 B9 h# n  }
1 {9 O, v$ y. q( V }
else {
  if(lar1.rc=='r') {
6 M( \# I( v8 m2 i  q& ?   r=lar1.num;
! u# X* z  O' b. K+ r- t% r- }   c=1;
   temp=temp_ab[lar1.num][1];
   for(i=1;i&lt;=num_b;i++)
% D. j+ ?0 }4 j& X/ A& T* w& p    if(temp_ab[lar1.num]&lt;temp) {
     c=i;
     temp=temp_ab[lar1.num];
    }
7 I: R0 |  B/ R4 b( [  }
8 ~; a' ?/ v1 R) A( e4 K* J; O  else {
   r=1;
   c=lar1.num;
8 j, E. k; _# m! ^( i   temp=temp_ab[1][lar1.num];
   for(i=1;i&lt;=num_a;i++)
    if(temp_ab[lar1.num]&lt;temp) {
     r=i;
     temp=temp_ab[lar1.num];
    }
  }
# D1 g3 A- {6 Z; B+ i }
: t* ^5 p; |! [9 a- D0 { pbase[r][c]=1;
if(temp_a[r]&gt;temp_b[c]) {
7 V: S2 @7 j6 I6 j" u  base[r][c]=temp_b[c];
  temp_a[r]=temp_a[r]-temp_b[c];
& |, Z5 M6 D$ [  temp_b[c]=0;
7 ^- \7 B; y# p  ~3 b6 P  for(i=1;i&lt;=num_a;i++) temp_ab[c]=M;
& D  Z3 O3 l/ K8 `- _ }
  A; [/ g; e3 D# `- S else if(temp_a[r]&lt;temp_b[c]) {
  base[r][c]=temp_a[r];
  temp_b[c]=temp_b[c]-temp_a[r];
6 U# w# ~6 H3 t  temp_a[r]=0;
! {& z/ D8 b# x7 D, c% T7 {  for(i=1;i&lt;=num_b;i++) temp_ab[r]=M;
0 D/ g4 w7 ~' D) \/ U }
0 B) Y, ?, }. V else if(temp_a[r]==temp_b[c]) {
# s- A3 f) _3 ~4 |: y  base[r][c]=temp_a[r];
  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;
  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) {
   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;}
) W" ?. P9 l( U* M* q   if(k==1) pbase[c]=1;
   else if(k==2) pbase[r][j]=1;
+ A" n# V4 i, m# D6 `- L# L  }
, \+ g/ j6 ]2 q9 Y }
* S7 j, a3 |0 ~ 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;
$ L9 \/ \! b7 @" O1 [- m( b findinit();
$ @3 ^; K4 g4 m9 @, D0 G( ?. Z- ]+ s}</P>
<>void computeuv() {
int i,j,k;
0 j, p' Y% A# V6 m, j for(i=1;i&lt;=num_a;i++)
8 s% e5 L1 l. Y4 I  for(j=1;j&lt;=num_b;j++)
- T9 a5 P, _( C   if(pbase[j]==1) {
! U" v) B$ p. O+ H0 a# T    if(pu==1) {v[j]=ab[j]-u; pv[j]=1;}
    if(pv[j]==1) {u=ab[j]-v[j]; pu=1;}
0 z* Z# |9 M* Q' H5 X   }
k=0;
for(i=1;i&lt;=num_a;i++) if(pu==0) k=1;
0 ~& y" [, X2 v8 B. ` for(i=1;i&lt;=num_b;i++) if(pv==0) k=1;
& B4 x* S# _' ?' x$ {, _$ q8 _ if(k==1) computeuv();
8 \8 P; O) k4 m8 ~9 W}</P>
<>int check() {
, m' {$ M4 ~/ I! V4 x  J) @ int i,j,k,l;
5 s' _2 O6 p  u k=l=0;
for(i=1;i&lt;=num_a;i++)
: M' g" F; y0 |0 T( _! D  for(j=1;j&lt;=num_b;j++)
4 b( T+ c" D5 {, k8 J   if(pbase[j]==0) {
    base[j]=ab[j]-u-v[j];
% L) x1 I) u0 s. p+ _7 T" @    if(base[j]&lt;0) k=1;
* G7 g$ [! s( m8 _/ u. D    else if(base[j]==0) l=1;
   }
/* for(i=1;i&lt;=num_a;i++){
  for(j=1;j&lt;=num_b;j++) printf("base %lg\t",base[j]);
  putchar('\n');}
for(i=1;i&lt;=num_a;i++){
9 h5 }" p( A5 w9 X6 s  l  for(j=1;j&lt;=num_b;j++) printf("pbase %d\t",pbase[j]);
  putchar('\n');}
: K% t- Z6 T8 s: j5 E. {" i$ W# w: c*/
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>
; h& B( ]- l& t7 r  u<>int circle(enum direction dir,struct element cir[],int *t) {
int i,j,k;
/*
putchar('\n');
for(i=1;i&lt;=*t;i++) printf("%d: r%d c%d\t",i, cir.r,cir.c);
putchar('\n');
# Y' g& q4 P5 ^: [# ` */
if((*t)!=1&amp;&amp;cir[(*t)].r==cir[1].r&amp;&amp;cir[*t].c==cir[1].c) {
1 w! F( G$ H5 w: {" x% z  t--;
, T6 l2 r% V3 f4 E4 \, G$ z' i' o( @  return 1;
}
1 Z7 d0 u3 p+ i( R- ? if(dir!=down) {
  k=0;
8 K$ ~1 V1 ~: h  for(i=cir[*t].r-1;i&gt;=1;i--)
; B3 r$ E1 F! l7 a: h8 U   if(pbase[cir[*t].c]==1||(i==cir[1].r&amp;&amp;cir[*t].c==cir[1].c)) {k=1; break;}
* _) ~1 C- {. I$ I! L( s0 f" p3 e  for(j=2;j&lt;=*t;j++) if(i==cir[j].r&amp;&amp;cir[*t].c==cir[j].c) k=0;
8 m0 p  h+ A2 Z0 {- z' j( t* N* F8 k3 X  if(k==1) {
6 l: `) f5 P5 |6 N   if(dir==up) cir[*t].value=0;
# ]& A+ n4 d* @: V% A* T4 G   else cir[*t].value=1;
   (*t)++;
   cir[*t].r=i;
   cir[*t].c=cir[(*t)-1].c;
  Z% _/ y3 u; O# z0 H8 ?   if(circle(up,cir,t)) return 1;
0 X: a& N; I) w  o2 [' ^. p$ M  }
1 D5 z& A  D+ M2 K9 e2 m }
if(dir!=up) {
6 [: o8 U7 |  R& ?/ G  _# p  k=0;
  for(i=cir[*t].r+1;i&lt;=num_a;i++)
3 l- ~, o* G9 r/ |0 g* \   if(pbase[cir[*t].c]==1||(i==cir[1].r&amp;&amp;cir[*t].c==cir[1].c)) {k=1; break;}
$ b% {4 i; G3 U  for(j=2;j&lt;=*t;j++) if(i==cir[j].r&amp;&amp;cir[*t].c==cir[j].c) k=0;
& |# L( ]; ^7 x# a- \2 r: L  if(k==1) {
$ V, }% A9 M& k5 ?6 \' h0 ~   if(dir==down) cir[*t].value=0;
+ S+ O% z( }' h/ T   else cir[*t].value=1;
9 n* F$ a$ s5 y: I; ]' W   (*t)++;
   cir[*t].r=i;
6 _1 B! ~' d; o  a$ m   cir[*t].c=cir[(*t)-1].c;
6 O9 K$ j) q6 w7 J! b6 L4 E   if(circle(down,cir,t)) return 1;
' T4 D; `  R0 W, B" R6 y6 o9 L. @  }
7 V5 `! I1 n, h }
) v* _  u& N# N+ h' G if(dir!=right) {
  k=0;
  for(i=cir[*t].c-1;i&gt;=1;i--)
5 `; J8 a4 K" a  y8 ~   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;
3 Q) F) ^) W3 p" K( I, h4 T   else cir[*t].value=1;
+ ]0 |) \( L4 H/ g  P8 I   (*t)++;
   cir[*t].r=cir[(*t)-1].r;
$ s/ q9 _- {; n$ p. U* u   cir[*t].c=i;
   if(circle(left,cir,t)) return 1;
# p) i/ j& O! P, s  }
}
- r& }. H4 A3 @ if(dir!=left) {
  k=0;
$ i' i; t; O* k" w( K' m; ?8 ~- J  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;}
- d5 Q) v& s. [; X' g  for(j=2;j&lt;=*t;j++) if(cir[*t].r==cir[j].r&amp;&amp;i==cir[j].c) k=0;
$ g; \8 M: z5 e8 ?  if(k==1) {
   if(dir==right) cir[*t].value=0;
   else cir[*t].value=1;
' T" J1 T: @) z9 ~   (*t)++;
   cir[*t].r=cir[(*t)-1].r;
   cir[*t].c=i;
) e6 U3 P( G/ ~' A, W   if(circle(right,cir,t)) return 1;
& X( X) r/ U1 c) f5 _! ?6 P  }
}
6 ~) S. C9 _( D (*t)--;
0 @% X6 k, \+ ?2 e! d return 0;
# d- N" T, N; z/ n9 d3 m}</P>
( L2 q* \7 Q. _- Z! E* ^<>void improve() {
! w4 x3 P0 @6 P) d6 K int i,j,k,t;
' ^, Q: a% e7 P& b/ |  W5 P/ j$ ^ 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;
9 @1 e  M, e" c) ~' ~ computeuv();
. @) x. M1 h& y0 ~7 `% h; Y4 j if(check()) return;
for(i=1;i&lt;=num_a;i++)
: y; ~0 A$ w% b: y6 Q  for(j=1;j&lt;=num_b;j++)
, X7 a9 X4 `( x3 D2 J' ], [   if(pbase[j]==0) break;
2 N/ w* P, r6 Y! K base_in.r=i;
base_in.c=j;
, k# J1 Y! n9 ?4 W7 N7 G base_in.value=base[j];</P>
<> for(i=1;i&lt;=num_a;i++)
/ B- Q: c  G2 h" |: c5 u  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;
) S4 }9 L' ^9 o. ?% \# @    base_in.value=base[j];
   }</P>
<> t=1;
+ E1 Y3 |+ O7 r+ B: Y cir[t].r=base_in.r;
cir[t].c=base_in.c;
* n  R( E6 H; C cir[t].value=1;
if(!circle(mid,cir,&amp;t)) {
  printf("程序出错！按回车结束");
- ~) z# ~9 r+ c2 E8 }  getchar();
  exit(0);
}
6 P' H7 M0 N- u6 A2 N% A6 ?5 H# P 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;
( S3 G1 D: o$ n( Y! C base_out.value=base[cir.r][cir.c];
k=1;
- R! O4 j1 V; v+ l3 ^) I4 I, o4 g, D for(i=1;i&lt;=t;i++)
  v& a  ?7 Z8 q5 j8 w. ]  if(k%2==0&amp;&amp;cir.value==1&amp;&amp;base[cir.r][cir.c]&lt;base_out.value) {
/ n! M& p6 {2 f) i# s; b2 z   base_out=cir;
) a) d. T" s  `; h4 |% D) x: L   base_out.value=base[cir.r][cir.c];
   k++;
  }
  else if(cir.value==1) k++;
base[cir[1].r][cir[1].c]=0;
k=1;
for(i=1;i&lt;=t;i++) {
1 S( h+ F6 e6 i/ v/ n8 R  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) {
5 u& e8 y& |* B! p7 ]! t) o7 E( _   base[cir.r][cir.c]-=base_out.value;
0 w- {) X7 R( i1 v0 m  V   k++;
# c1 P, Y/ R- T$ {' D6 x9 E$ D  }
}
3 N7 l% E/ @% C7 U, \ pbase[base_out.r][base_out.c]=0;
pbase[base_in.r][base_in.c]=1;</P>
* }6 E' O  F4 \! b$ `<> improve();
}</P>
2 ?4 T' e, v! Q% q* x, ?  f1 B3 v<>void output() {
int i,j;
$ W( D" ^8 h6 c' O6 A! B- G6 _" C double sum=0;
printf("\n运量为：\n");
for(i=1;i&lt;=num_a;i++) {
, C! Z- [  k0 E+ V& A5 A* Z5 D8 Y  putchar(' ');
  for(j=1;j&lt;=num_b;j++)
1 s& W, M! U/ i) n   if(pbase[j]==1) {
0 O8 J# D% O4 M& Z5 d3 b    printf("A%d-&gt;B%d:%lg\t",i,j,base[j]);
1 O7 d. X" _6 e/ o, P7 K    sum+=base[j]*ab[j];
   }
   else printf("A%d-&gt;B%d:0\t",i,j);
) z% H: X  p0 Z/ a- z4 }7 S- j5 r3 P  putchar('\n');
/ g  e3 C" F" o }
printf("\n最低总运费为：%lg\n",sum);
/ ]3 L7 Y) N& T4 ~. V1 K( s}
5 k; h2 r2 d: L0 [' }</P>

zhongguohelin

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

enrique08

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

hzlhm

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

liunengwu

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