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

plgatc

<>/*************************************************************************
% F$ g% T4 G! c0 m  w$ w                         表上作业法解运输问题        

编程环境：VC++6.0     
, `0 S9 |; R4 u( x$ h/ G+ ~2 j 程序说明：
- K0 a. _- ]. h6 R Vogel法求初始解，位势法检验是否最优，递归搜索闭回路改进解。
' J: g- @2 p# _6 V1 h6 W$ o *************************************************************************/
#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;</P>
3 n& q# T+ E; u<>#define MAX 100
#define M 999999</P>
, w5 r$ q. J4 p5 z7 B<>int status; //1唯一最优解，-1无穷多最优解</P>
6 Y9 u8 p/ ?* X. g% `<>int num_a,num_b;
2 e! d6 {1 a( ?8 N7 rdouble a[MAX],b[MAX],temp_a[MAX],temp_b[MAX];
  i  [! P9 Y. c/ Z8 g8 J+ I& i' adouble u[MAX],v[MAX],pu[MAX],pv[MAX];
, _- ^! W7 `3 fdouble ab[MAX][MAX],temp_ab[MAX][MAX];
double base[MAX][MAX];
int pbase[MAX][MAX];
3 C8 C+ \* w8 M2 e2 l/ s: i# z  ]; {struct element {
int r;
int c;
8 h$ C( j* J# {9 D; D: w% t% } double value;
};
. N; h* j/ d& Z# n+ s3 t7 Genum direction {mid,up,down,left,right};</P>
<>void create();
2 A' x& E8 I. `* h/ n. Vvoid banner();
double dabs(double d);
void findinit();
void computeuv();
3 }; D; H; t# j. ~+ Lint check();
int  circle(enum direction dir,struct element cir[],int *t);
void improve();
void output();</P>
; I  K0 ^, i7 v, m( M<>void main() {
" O+ T* D1 Q# j/ F banner();
create();
0 l! W2 u# s4 ~- k% G2 E0 B printf("\n按回车确认后开始求解");
  ]8 p3 K1 g* a2 l0 M6 J) R) @ getchar();
7 k- C" Z7 M, P6 @- k) g getchar();
7 s6 W- x/ a) m4 P findinit();
improve();
switch(status) {
/ j  V8 u+ P7 r; v case 1:
  output();
/ n0 W  H0 Y$ }7 d# Z! ^  puts("\n原问题有唯一最优解。\n");
  puts("\n按回车结束");
! H4 j- C* |1 g; r" A  getchar();
* c" j# M4 K. S  exit(0);
case -1:
  output();
  puts("\n原问题有无穷多最优解。\n");
! Q* F. H# v/ f. G. w  puts("\n按回车结束");
  getchar();
  exit(0);
}
}</P>
$ W; |& a% G, }; C% d<>void banner() {
! R/ i1 c) E, N4 O2 l. Q printf("\t\t****************************************\n");
printf("\t\t         表上作业法解运输问题\n");
printf("\t\t                              Thunder\n");
printf("\t\t****************************************\n");
8 P1 N" [2 M$ K1 J printf("\n");
0 J7 r% d1 P2 C; w8 C# y' {3 m}</P>
<>void create() {
2 O. T( X4 Y9 A$ Y! R; O+ N int i,j;
double sum_a,sum_b;
char confirm;
while(1) {
2 z2 a/ V6 ]8 ^+ B7 j% l0 V4 z  printf("请输入产地个数：");
# `+ z3 |1 U4 x4 }4 C: s  scanf("%d",&amp;num_a);
  for(i=1;i&lt;=num_a;i++) {
" P" R+ G2 u3 ~3 Z7 g: }   printf("A%d产量：",i);
   scanf("%lf",&amp;a);
5 K8 R5 `3 X( s, _7 b  `7 j  }
  for(i=1;i&lt;=num_a;i++) printf("A%d产量：%lg\t",i,a);
6 s  N% |' R( D) z; ?" [  printf("\n正确吗？：(y/n)");
; G& s1 B7 N, I, x& M) s1 t0 ?  getchar();
2 U3 {% t/ @% q4 C1 Y$ g, N  confirm=getchar();
$ I9 V# K. w( f) b! E/ U2 Q  if (confirm=='y') break;
+ L8 i, U, @# ^0 b8 L  else if(confirm=='n') continue;
+ s" f% y6 w+ W3 u }
while(1) {
  printf("\n请输入销地个数：");
  scanf("%d",&amp;num_b);
2 N; B! _' Z, X! d9 g- L8 A  for(i=1;i&lt;=num_b;i++) {
4 k+ n" s, b+ O   printf("B%d销量：",i);
   scanf("%lf",&amp;b);
! t- ?1 G2 i: \  }
9 r5 e% ?* `# l2 m8 [; |9 }, ?  for(i=1;i&lt;=num_b;i++) printf("B%d销量：%lg\t",i,b);
  printf("\n正确吗？：(y/n)");
  getchar();
  confirm=getchar();
& r/ S2 b1 O4 f& a  if (confirm=='y') break;
$ e& U$ }& q- l+ O; @  else if(confirm=='n') continue;
}
putchar('\n');
for(i=1;i&lt;=num_a;i++) {
+ R! @0 V% M" Z* d# [7 k# K  for(j=1;j&lt;=num_b;j++) {
   printf("A%d到B%d运价：",i,j);
   scanf("%lf",&amp;ab[j]);
  }
3 f6 C: r4 \  o0 P$ }  for(j=1;j&lt;=num_b;j++) printf("A%d到B%d：%lg\t",i,j,ab[j]);
, M1 W& p5 f8 T+ i4 g3 y- p. M' ?  printf("\n正确吗？：(y/n)");
/ g: p0 l! \: u# ~* z  getchar();
8 p: }9 t7 b/ ^# J  confirm=getchar();
& b7 F3 U+ J/ v. C  if(confirm=='n') i--;
5 N3 R2 C$ g# a- J- M1 _" ^) L3 o  putchar('\n');
}
! x% z7 l% f& ?+ }8 H4 C- X //处理产销不平衡的情况
sum_a=sum_b=0;
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);
2 j+ O' L5 Q5 {5 X; C2 R5 D if(sum_a==sum_b) printf("\t产销平衡。");
else if(sum_a&gt;sum_b) {
  printf("\t供大于求，增加假想销地B%d。\n",++num_b);
1 k% j& `; M, [, S9 [  b[num_b]=sum_a-sum_b;
  for(i=1;i&lt;=num_a;i++) ab[num_b]=0;
}
( z8 S: `, ^' L5 B! \5 p/ X else if(sum_a&lt;sum_b){
  printf("\t供不应求，增加假想产地A%d。\n",++num_a);
* B2 ]' b' n3 D" K  a[num_a]=sum_b-sum_a;
" z& n. `+ A; U% H8 c$ J% C  for(i=1;i&lt;=num_b;i++) ab[num_a]=0;
6 A- N. I1 u, H! C }
. ]/ U: l$ o* A/ V# U6 O3 Q0 l+ S& z //求解前的准备
2 ]3 @$ C0 `9 S) U5 D for(i=1;i&lt;=num_a;i++)
  for(j=1;j&lt;=num_b;j++)
$ q: U3 U; I6 k7 J   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;
for(i=1;i&lt;=num_a;i++)
for(j=1;j&lt;=num_b;j++) temp_ab[j]=ab[j];
7 y3 n$ I0 Q4 c. h5 Z5 ^  U, j //回显问题
- M4 v1 v: }) a3 {- `4 R8 z# G printf("\n\n原问题为：\n\n");
   printf("产量：\n ");
for(i=1;i&lt;=num_a;i++) printf("A%d:%lg\t",i,a);
2 n6 S, V( {* R9 Q( F5 M printf("\n运量：\n ");
for(i=1;i&lt;=num_b;i++) printf("B%d:%lg\t",i,b);
printf("\n运价为：\n");
  B5 I) h) N: X for(i=1;i&lt;=num_a;i++) {
  putchar(' ');
7 k/ m. m' w5 l8 Y  for(j=1;j&lt;=num_b;j++)
   printf("A%d-&gt;B%d:%lg\t",i,j,ab[j]);
  putchar('\n');
}
}</P>
; e6 f8 f( S9 @1 d1 o, b- L<>double dabs(double d) {
if(d&gt;=0) return d;
else return -d;
}</P>
; U/ C3 g8 i1 s% J9 g  t$ R' F/ A  |) X<>void findinit() {
int i,j,k;
double r_penum[MAX],c_penum[MAX];
; A& w4 x  }* G, t0 ?; v struct largest {
  char rc;
: M; Q4 F& k. p  int num;
  double value;
/ B& U$ x- L8 f; T9 c };
struct largest lar1,lar2;
4 W5 k4 F! L! p+ ]+ R int r=0,c=0;
double a1,a2,b1,b2,temp;</P>
<> for(i=1;i&lt;=num_a;i++) {
; H# i  b  e0 N$ J) E  temp=temp_ab[1];
  for(j=1;j&lt;=num_b;j++)
   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
  a1=a2=temp;
% Y# @- l6 R/ L8 _  for(j=1;j&lt;=num_b;j++)
( S9 U! c8 d+ ?   if(temp_ab[j]&lt;=a1) {
    a2=a1;
* e# n7 h7 u. ]9 p8 s    a1=temp_ab[j];
7 l, D! H" s0 u$ r* Z( i, ~   }
3 A% G6 ^  d8 ~) ?   else if(temp_ab[j]&lt;=a2) a2=temp_ab[j];
  r_penum=dabs(a1-a2);
# t9 Q  R* G, ]( ~) U! Y }</P>
<> for(i=1;i&lt;=num_b;i++) {
  temp=temp_ab[1];
  for(j=1;j&lt;=num_a;j++)
5 Y; ~$ F6 W0 b- C* G   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
3 J( W' s3 A  D# Y! h& d  b1=b2=temp;
, u: l- v' r" T) p  for(j=1;j&lt;=num_a;j++)  
  k- p- ?! z$ r8 E! l& q   if(temp_ab[j]&lt;=b1) {
    b2=b1;
$ E9 k9 G* v3 H: e+ l    b1=temp_ab[j];
) S+ Z$ O" a: D   }
# @' V; P/ F) n) y4 @, E   else if(temp_ab[j]&lt;=b2) b2=temp_ab[j];
  c_penum=dabs(b1-b2);
# w7 j* ~' w3 _. y7 `0 r$ y }
/*
for(i=1;i&lt;=num_a;i++) printf("pa%d=%lg ",i,r_penum);
9 _, Y5 V; B- v5 ?. @3 }5 A3 R putchar('\n');
for(i=1;i&lt;=num_b;i++) printf("pb%d=%lg ",i,c_penum);
1 v. V; V3 S8 P! r  E */
temp=r_penum[1];
: s" \! [  V/ ~' T/ U6 s for(i=1;i&lt;=num_a;i++) if(r_penum&lt;temp) temp=r_penum;
* t3 c9 J9 x8 Y8 w& ]% j for(i=1;i&lt;=num_b;i++) if(c_penum&lt;temp) temp=c_penum;</P>
<> //考虑了有两个罚数相等的情况，大于两个相等只取其中两个进行比较
lar1.value=lar2.value=temp;
. \' b- d  H: w7 x4 s/ g6 }# m lar1.num=lar2.num=1;
lar1.rc=lar2.rc='r';
for(i=1;i&lt;=num_a;i++)
  if(r_penum&gt;=lar1.value) {
) D2 G& T2 u6 z  y) r   lar2=lar1;
8 C& ?" A7 p7 C& T& \, _   lar1.rc='r';
5 c: Q+ B5 i" M  E( T4 _   lar1.num=i;
   lar1.value=r_penum;
  }
8 U0 ^) Q* l" s) Q! T' |/ d6 r. R  else if(r_penum&gt;=lar2.value) {
/ a' I2 T; F- _2 _1 u   lar2.rc='r';
   lar2.num=i;
   lar2.value=r_penum;
5 {- L9 I( e% n% w7 J$ M4 s  }</P>
<> for(i=1;i&lt;=num_b;i++)
  if(c_penum&gt;=lar1.value) {
   lar2=lar1;
8 u. ~. P" R0 v/ Z   lar1.rc='c';
. L1 `3 z6 e3 |- s0 K7 d- ]   lar1.num=i;
" E$ p/ G6 U( @   lar1.value=c_penum;
  }
  else if(c_penum&gt;=lar2.value) {
   lar2.rc='c';
2 v' L4 I: ]# \2 o2 n+ B9 T   lar2.num=i;
) O8 t* J4 U& j+ Q2 u& ~' r6 m1 l9 ]   lar2.value=c_penum;
) Z1 s, }5 \5 F% R  }</P>
<> if(lar1.value==lar2.value&amp;&amp;(lar1.num!=lar2.num||lar1.rc!=lar2.rc)) {
4 S/ \5 W3 g/ L3 H  if(lar1.rc=='r'&amp;&amp;lar2.rc=='r') {
   temp=temp_ab[lar1.num][1];
   r=lar1.num;
, m( f1 y, S3 U5 b: [* _' d, ~      c=1;
   for(i=1;i&lt;=num_b;i++) {
6 e9 S  D+ {7 u9 {    if(temp_ab[lar1.num]&lt;temp) {
     temp=temp_ab[lar1.num];
- `$ |' F+ H* c, \; j  O     r=lar1.num;
     c=i;
8 a& @  i! Y$ V1 O. E# U, Q    }
    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
9 _8 c! k$ |. ^  G0 H: f1 q  v: j4 ~     r=lar2.num;
, b/ v- I: S* R5 W: k     c=i;
    }
' W7 E1 C, ~! C" x- F' j1 \. F5 B2 p   }
: w+ u* ~7 Y0 a  }
  if(lar1.rc=='c'&amp;&amp;lar2.rc=='c') {
& U1 R# g( t2 ]9 g   temp=temp_ab[1][lar1.num];
7 U! l, ?" s1 h( ~1 E- a& h/ \   r=1;
, ^5 p* O4 y7 {4 j/ G+ P$ N0 ?      c=lar1.num;
   for(i=1;i&lt;=num_a-1;i++) {
! m/ [) |) q6 Q2 z    if(temp_ab[lar1.num]&lt;temp) {
     temp=temp_ab[lar1.num];
6 U$ j$ ]: J& h3 `; R& [# h& O8 s     c=lar1.num;
1 t5 E& t5 i+ t4 G% F* ]     r=i;
    }
    if(temp_ab[lar2.num]&lt;temp) {
5 I5 S+ m+ T. N* O) k     temp=temp_ab[lar2.num];
2 [4 t4 d7 n/ s$ d' K     c=lar2.num;
0 n2 _4 p6 Y9 W% m  {1 t# q8 k     r=i;
    }
1 C/ \' z+ G1 W, W   }
  }
  if(lar1.rc=='r'&amp;&amp;lar2.rc=='c') {
   temp=temp_ab[lar1.num][1];
   r=lar1.num;
      c=1;
   for(i=1;i&lt;=num_b;i++)
/ c& D% l) W$ i# i    if(temp_ab[lar1.num]&lt;temp) {
     temp=temp_ab[lar1.num];
     r=lar1.num;
: o$ s: a! W+ X- W9 I$ ~1 T# v     c=i;
    }
- B- T6 {8 h4 b   for(i=1;i&lt;=num_a;i++)
* B: k0 A2 s( q( x0 u/ ~% J3 Z    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
     c=lar2.num;
- l9 [5 t8 R8 Z+ ^4 v  Z/ q     r=i;
( y/ J/ E, o! l5 J1 f$ o    }
% Z' s, i* k  H, l1 R- Q! _  }
  if(lar1.rc=='c'&amp;&amp;lar2.rc=='r') {
   temp=temp_ab[1][lar1.num];
   r=1;
) L5 k8 A$ D* [      c=lar1.num;
   for(i=1;i&lt;=num_b;i++)
0 m( G( a! \; Y5 I    if(temp_ab[lar2.num]&lt;temp) {
7 `$ ~/ n" R! ?& k9 K1 \     temp=temp_ab[lar2.num];
' r2 _! z9 h! k, g! I! ]7 y+ a     r=lar2.num;
     c=i;
6 b# Y1 o3 h2 Y    }
. V" d( E% w8 I2 F9 u0 h/ v   for(i=1;i&lt;=num_a;i++)
: O) h$ K- ~" W6 m& j( f$ W( b    if(temp_ab[lar1.num]&lt;temp) {
' v* b. I+ b# P     temp=temp_ab[lar1.num];
2 ?- g+ {- f: Y. y; d/ e/ A; d+ b     c=lar1.num;
     r=i;
* F4 E  e3 V' g; O: _    }
/ W: u- Z7 G0 l' F  }
' D0 C* r2 L/ o  \0 q4 Q }
else {
: {1 }. ^5 @6 `, C1 N/ l+ E  if(lar1.rc=='r') {
   r=lar1.num;
6 d/ X: V" I, Q9 Y1 H   c=1;
   temp=temp_ab[lar1.num][1];
. G& A. p: v* x& [% `: C   for(i=1;i&lt;=num_b;i++)
  q- @' |+ O+ ?$ H& Q    if(temp_ab[lar1.num]&lt;temp) {
' j! a. V% T2 z0 i) @, F5 a/ f     c=i;
+ @* L+ ?- m- U+ y3 h+ z% q4 i' F     temp=temp_ab[lar1.num];
: B1 e4 |- ]7 e: @2 o    }
  }
  else {
   r=1;
   c=lar1.num;
   temp=temp_ab[1][lar1.num];
   for(i=1;i&lt;=num_a;i++)
    if(temp_ab[lar1.num]&lt;temp) {
* N% w, v9 O1 z. d- Z% \: `     r=i;
- D* o# D; T6 B) J' j     temp=temp_ab[lar1.num];
! g( R! v$ S% l3 q1 x    }
& [4 [# u  i+ D) X6 c" b  }
2 e. h8 u" C6 ~0 T2 X }
pbase[r][c]=1;
if(temp_a[r]&gt;temp_b[c]) {
  base[r][c]=temp_b[c];
: _& r; W+ @! b* j  temp_a[r]=temp_a[r]-temp_b[c];
8 K" j6 I6 ?, ?- I  temp_b[c]=0;
  for(i=1;i&lt;=num_a;i++) temp_ab[c]=M;
  \' U% E: }8 c- w: j }
' [. C$ I5 |% x9 _2 d& t* q6 X else if(temp_a[r]&lt;temp_b[c]) {
, Q- o( C, k$ k% A: C; R0 J; w" v  base[r][c]=temp_a[r];
  temp_b[c]=temp_b[c]-temp_a[r];
8 K' F, q- U9 `& B+ T0 N. J: i  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];
  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;
( J4 W0 Q! P7 U4 f9 I4 f  k=0;
$ g( {% g: F: ?  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;
4 m: g- j' F+ e  |9 S% Y* M  if(k!=0) {
& K2 c6 c! C  ~7 g+ |   k=0;
6 R! f2 E) A# m% w2 ~   for(i=1;i&lt;=num_a;i++) if(pbase[c]!=1) {k=1;break;}
" x+ G7 s; L0 X: k5 s8 a* L9 }) f   for(j=1;j&lt;=num_b;j++) if(pbase[r][j]!=1) {k=2;break;}
$ E8 J% G5 n! Z  ]+ T   if(k==1) pbase[c]=1;
" Y0 I, c: O2 ?& d% R' U* l# I/ L- B   else if(k==2) pbase[r][j]=1;
8 N1 a" g% U6 f8 A  }
! S- S9 ~4 \! Y' A; D% H/ H }
0 ~5 C  _( _: a k=0;
for(i=1;i&lt;=num_a;i++) if(temp_a!=0) k=1;
% X7 U( ~+ L" W* @; a0 T for(i=1;i&lt;=num_b;i++) if(temp_b!=0) k=1;
if(k==0) return;
+ \4 N, D3 s+ s7 j findinit();
- P. K, F9 E) U0 f  t% Q2 K}</P>
) P/ r  d. H8 m5 {) ]9 P$ E/ N<>void computeuv() {
( D4 L0 U5 w4 ^, L# \) `* h int i,j,k;
for(i=1;i&lt;=num_a;i++)
. ^' b/ y* l' m" @  w. X- a4 Q  for(j=1;j&lt;=num_b;j++)
. v# U& N6 }5 p/ U1 l8 l   if(pbase[j]==1) {
( H) e- Q7 f7 F) D$ q    if(pu==1) {v[j]=ab[j]-u; pv[j]=1;}
    if(pv[j]==1) {u=ab[j]-v[j]; pu=1;}
   }
k=0;
! {- G( _: U# d5 v6 K4 ^0 i 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();
0 e. K0 j7 x. s5 D  L! a; H}</P>
<>int check() {
int i,j,k,l;
3 w, h9 k0 U& ~1 @2 \$ d9 b k=l=0;
' v1 h/ k0 D" u* g4 _0 z for(i=1;i&lt;=num_a;i++)
, N: A% f% U3 Q! Y4 }  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==0) {
    base[j]=ab[j]-u-v[j];
  P  Q1 V/ D: h" Z    if(base[j]&lt;0) k=1;
    else if(base[j]==0) l=1;
   }
* \! C/ Q2 v( X0 N7 y- i6 g/* for(i=1;i&lt;=num_a;i++){
2 q8 m/ p7 p2 U  @8 n/ [6 q  for(j=1;j&lt;=num_b;j++) printf("base %lg\t",base[j]);
  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');}
, T! U, w* m) N/ E! x) V4 x1 z; {*/
if(k==0&amp;&amp;l==0) {status=1; return 1;}
  M( a5 z9 X2 P0 ~+ y' l1 @; \ else if(k==0&amp;&amp;l!=0) {status=-1; return 1;}
" h6 d* x- @2 K! |/ w: l else return 0;
}</P>
5 @0 C. o6 D$ m. u, b0 U. |( U' W<>int circle(enum direction dir,struct element cir[],int *t) {
2 G1 D' H! O9 Q. r) D int i,j,k;
/*
$ ]  J: b; z. N0 w9 L+ |% z* P putchar('\n');
for(i=1;i&lt;=*t;i++) printf("%d: r%d c%d\t",i, cir.r,cir.c);
putchar('\n');
*/
5 ^8 D' I/ a! S+ {+ d% Z5 U! H if((*t)!=1&amp;&amp;cir[(*t)].r==cir[1].r&amp;&amp;cir[*t].c==cir[1].c) {
  t--;
9 s& |! p& G; v/ f" r  return 1;
}
+ o& ?8 C, u# z  z% o4 v! [ if(dir!=down) {
1 l. Z3 m# G8 U: y7 N/ R  e! ]( r) c; Q  k=0;
  for(i=cir[*t].r-1;i&gt;=1;i--)
2 J  z# Y" ]1 N# e/ r1 ^$ F5 z   if(pbase[cir[*t].c]==1||(i==cir[1].r&amp;&amp;cir[*t].c==cir[1].c)) {k=1; break;}
! u2 n' r- Y0 O  for(j=2;j&lt;=*t;j++) if(i==cir[j].r&amp;&amp;cir[*t].c==cir[j].c) k=0;
1 U' X2 n* ^  H, z- `. n  if(k==1) {
   if(dir==up) cir[*t].value=0;
: T' p4 h+ @7 j& f' [   else cir[*t].value=1;
. Y) u1 E& }7 b' G* a  s' G8 O, I- `   (*t)++;
   cir[*t].r=i;
6 @1 M- h+ j5 Z1 P   cir[*t].c=cir[(*t)-1].c;
   if(circle(up,cir,t)) return 1;
; \  D* _- Z3 o) I5 z+ X  }
) U. u! i- n2 }3 @ }
. {/ t+ x! P9 T5 X; ?' G! u if(dir!=up) {
  k=0;
  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;
9 Y! q2 Z6 d7 N* ^$ `0 |/ c) M  if(k==1) {
, D+ C* ~4 Z; X( m7 b   if(dir==down) cir[*t].value=0;
   else cir[*t].value=1;
   (*t)++;
   cir[*t].r=i;
& s. I8 l5 a5 I: e2 V& K. V& P   cir[*t].c=cir[(*t)-1].c;
   if(circle(down,cir,t)) return 1;
  }
}
7 J' @  q6 \. U  D) L& Q if(dir!=right) {
  k=0;
  for(i=cir[*t].c-1;i&gt;=1;i--)
' L' L! z& ~  o4 O+ a" G# ?; ?   if(pbase[cir[*t].r]==1||(cir[*t].r==cir[1].r&amp;&amp;i==cir[1].c)) {k=1; break;}
2 B) u  x, y2 d' a: @% h" o  for(j=2;j&lt;=*t;j++) if(cir[*t].r==cir[j].r&amp;&amp;i==cir[j].c) k=0;
" ?: Y: |3 F' X5 U7 g  if(k==1) {
$ c8 `2 o$ j- x2 ]* V) A: c& n   if(dir==left) cir[*t].value=0;
4 N7 g4 q+ v! o; D0 @2 D: v   else cir[*t].value=1;
% Z% X  m1 i! I, X: G( x  i# C   (*t)++;
9 i+ V* ?' P. |; y   cir[*t].r=cir[(*t)-1].r;
   cir[*t].c=i;
   if(circle(left,cir,t)) return 1;
; T, f) x  ~# w3 R0 @  }
}
if(dir!=left) {
2 E+ M6 y( z0 S6 b# z' ?; b% D  k=0;
5 w0 t% e8 `# r. c# }) f* v: U  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) {
   if(dir==right) cir[*t].value=0;
   else cir[*t].value=1;
6 ]* i5 M" X- g; V) h  Y   (*t)++;
   cir[*t].r=cir[(*t)-1].r;
' b: S# q' A5 c2 s( t0 |% A- j5 _   cir[*t].c=i;
   if(circle(right,cir,t)) return 1;
  }
0 s0 G# N& f7 {) c7 `- i }
% x: i% D8 S5 y2 { (*t)--;
( u: {+ r  n0 A" q: X+ r return 0;
. M, O- \' m% W& C* I}</P>
" R0 i& P" h' Y7 I<>void improve() {
int i,j,k,t;
$ f2 \+ h8 M' G* \$ ~' P+ Y& x) 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;
computeuv();
if(check()) return;
for(i=1;i&lt;=num_a;i++)
  for(j=1;j&lt;=num_b;j++)
1 v2 ?7 K9 L& M   if(pbase[j]==0) break;
, e" g$ ?3 f% A base_in.r=i;
6 L0 T" ^9 w# r. J* }1 I. f base_in.c=j;
' T$ A6 s9 Y' l( t8 z$ | 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) {
' Y# C) R# k  f1 v    base_in.r=i;
  I) D4 r( m; G4 ]7 v    base_in.c=j;
    base_in.value=base[j];
   }</P>
<> t=1;
cir[t].r=base_in.r;
: d) s3 e5 B# H) a cir[t].c=base_in.c;
; X# b* \6 N" o9 x* a3 ~ cir[t].value=1;
if(!circle(mid,cir,&amp;t)) {
- J- p7 O3 Y& C* e  printf("程序出错！按回车结束");
  getchar();
  exit(0);
$ C* f; I; O( `- O- o) @ }
+ v5 Z+ z4 \) v2 M2 @" u% v t--;
. Y. n) Q+ v- C// 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>
& Z0 N: s9 X6 H! R<> for(i=2;i&lt;=t;i++) if(cir.value==1) break;
% z, B3 t9 {3 S( \ base_out=cir;
1 P( z, ?9 \; _6 { base_out.value=base[cir.r][cir.c];
k=1;
. C2 d/ O9 Y# S' i( Z7 J 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];
6 E8 y6 F) v/ V   k++;
& H8 c1 e; J3 _/ W3 F. w  }
, g8 L& P: Z' B" d* p" p, T  else if(cir.value==1) k++;
base[cir[1].r][cir[1].c]=0;
k=1;
for(i=1;i&lt;=t;i++) {
/ t8 X) |( U& S4 ~  N  if(k%2==1&amp;&amp;cir.value==1) {
2 n6 S* P" d& l3 W3 M7 ?1 k   base[cir.r][cir.c]+=base_out.value;
   k++;
  }
  else if(k%2==0&amp;&amp;cir.value==1) {
* s, z4 J3 c* f  m' V  E  W   base[cir.r][cir.c]-=base_out.value;
   k++;
  }
) T$ Z# ~0 r( g+ R7 P }
" `2 q* x$ x2 Q/ Q3 k1 U) {' T/ {9 d pbase[base_out.r][base_out.c]=0;
/ s- u6 o/ Z: Z! Y. O pbase[base_in.r][base_in.c]=1;</P>
<> improve();
3 d# a* v  `, E; a}</P>
<>void output() {
# v+ L3 a% {2 a. r6 N: s/ q/ R int i,j;
# i& n% j' m. t- I double sum=0;
% a* `" ]3 b9 F; w printf("\n运量为：\n");
for(i=1;i&lt;=num_a;i++) {
# m5 z1 {  Q9 q  putchar(' ');
; _2 J( a. g( |- t  for(j=1;j&lt;=num_b;j++)
0 E* X8 L8 p# M+ F) B   if(pbase[j]==1) {
    printf("A%d-&gt;B%d:%lg\t",i,j,base[j]);
    sum+=base[j]*ab[j];
   }
  d& E+ M) H* `  Q   else printf("A%d-&gt;B%d:0\t",i,j);
  putchar('\n');
}
6 e7 y' ]3 w4 p  r- b7 m printf("\n最低总运费为：%lg\n",sum);
}
$ V; C: X; v7 {3 Z, S8 w' X- d</P>

zhongguohelin

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

enrique08

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

hzlhm

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

liunengwu

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