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

plgatc

<>/*************************************************************************
                         表上作业法解运输问题        

编程环境：VC++6.0     
程序说明：
Vogel法求初始解，位势法检验是否最优，递归搜索闭回路改进解。
0 M% h0 v/ f7 m/ A. a& y *************************************************************************/
#include &lt;stdio.h&gt;
+ o! y* f2 N" Y$ U#include &lt;stdlib.h&gt;</P>
! {6 O+ ~/ `9 ], e<>#define MAX 100
#define M 999999</P>
7 N, m" T7 `. j; g9 Y1 G<>int status; //1唯一最优解，-1无穷多最优解</P>
<>int num_a,num_b;
double a[MAX],b[MAX],temp_a[MAX],temp_b[MAX];
& C: L+ O7 {* a1 H6 adouble u[MAX],v[MAX],pu[MAX],pv[MAX];
# H% A- [" `4 a# P* B8 N/ J. z3 Sdouble ab[MAX][MAX],temp_ab[MAX][MAX];
, e! }  w  N6 L. A9 e6 Ddouble base[MAX][MAX];
int pbase[MAX][MAX];
struct element {
int r;
, O2 z: G1 [) M) e int c;
double value;
; x6 q( P( X% e8 F$ Y0 r$ `};
' d4 i) _+ R! R) Z4 g) ~5 {enum direction {mid,up,down,left,right};</P>
; Q2 X  j* P/ Z5 @( j) F<>void create();
/ P0 F' g- v% A9 h  p0 s4 svoid banner();
$ g8 B, K  i6 a" ~) E# N* cdouble dabs(double d);
void findinit();
% m7 t% p5 m1 E! X1 X/ h: k/ _void computeuv();
int check();
: b7 P- U3 S1 i& Wint  circle(enum direction dir,struct element cir[],int *t);
void improve();
void output();</P>
2 j- M' o; J( w/ K  I<>void main() {
) a5 {: b2 `$ Z' s  F banner();
5 d' p' T! j# s: V; ` create();
printf("\n按回车确认后开始求解");
getchar();
1 @" l/ V7 _& m8 h1 H+ P$ H' H0 ] getchar();
findinit();
improve();
; t+ \( H. ~+ d* K* m; V switch(status) {
4 J: k8 r7 @, |/ _1 i! \4 C case 1:
  output();
  puts("\n原问题有唯一最优解。\n");
1 d3 ?" s0 T& A7 d8 N  u  puts("\n按回车结束");
+ @# @+ K& p- h  getchar();
5 r! F8 Q1 V  H9 K3 z; [  exit(0);
( x" d4 {; A  B  @' o case -1:
1 A  @6 e" v1 z6 G1 T9 E8 m  output();
  puts("\n原问题有无穷多最优解。\n");
: Q9 {: S& ~- ], V  puts("\n按回车结束");
& q6 B  H1 i  q" {! f5 y  I  getchar();
  exit(0);
; O& o, ?& y2 D, i) V }
}</P>
<>void banner() {
printf("\t\t****************************************\n");
4 G6 O; O; u4 B( y  X% f& z8 \$ [ printf("\t\t         表上作业法解运输问题\n");
; V# }! P8 {5 @# ? printf("\t\t                              Thunder\n");
printf("\t\t****************************************\n");
printf("\n");
}</P>
: @7 W9 `/ ?8 S9 a# p3 Y% C<>void create() {
int i,j;
8 q& @2 d7 J7 |* J3 l6 n! T: s8 d double sum_a,sum_b;
char confirm;
! h' p. \( ^2 s' }3 Y while(1) {
  printf("请输入产地个数：");
  scanf("%d",&amp;num_a);
8 h0 e0 Z- m2 _/ b  for(i=1;i&lt;=num_a;i++) {
4 z6 ]5 k- }3 F; ]3 B1 R! I   printf("A%d产量：",i);
   scanf("%lf",&amp;a);
) Y# h4 }8 {% p9 m9 d  }
  y. B6 h& o' _; `9 E* }  for(i=1;i&lt;=num_a;i++) printf("A%d产量：%lg\t",i,a);
7 y- Q+ s9 z& W" d& `  printf("\n正确吗？：(y/n)");
9 [6 [1 j5 r  Y$ ^$ F7 z9 I& [  getchar();
  confirm=getchar();
  if (confirm=='y') break;
$ ]* o! m6 c6 X. F& Q0 r9 ?. c2 f  else if(confirm=='n') continue;
1 y( n9 f% S( Z! ] }
while(1) {
  printf("\n请输入销地个数：");
  scanf("%d",&amp;num_b);
  for(i=1;i&lt;=num_b;i++) {
   printf("B%d销量：",i);
- v9 h+ x8 {3 Y- ^# S  ~   scanf("%lf",&amp;b);
+ @6 Z9 D0 t% N1 i8 W5 Y7 D  }
  for(i=1;i&lt;=num_b;i++) printf("B%d销量：%lg\t",i,b);
  printf("\n正确吗？：(y/n)");
  getchar();
. X, N8 O; K2 G; O) N  confirm=getchar();
- z" N2 w& m/ Z5 j# Z' y  if (confirm=='y') break;
  else if(confirm=='n') continue;
/ H3 S: Y8 v/ U, h, ^ }
putchar('\n');
. k- G2 Y2 D. T9 p4 k) g: p for(i=1;i&lt;=num_a;i++) {
  for(j=1;j&lt;=num_b;j++) {
0 @2 e3 ~3 A1 w5 y8 k7 i. T+ o3 `   printf("A%d到B%d运价：",i,j);
5 U5 M8 E- T# o   scanf("%lf",&amp;ab[j]);
7 r9 R/ ?& ~+ Z6 k; }  y2 e5 G  }
  for(j=1;j&lt;=num_b;j++) printf("A%d到B%d：%lg\t",i,j,ab[j]);
. C9 x" @, W7 s7 Z  printf("\n正确吗？：(y/n)");
  getchar();
  confirm=getchar();
9 E: t* @. ~3 G8 Q8 v" o- [  if(confirm=='n') i--;
6 R3 R$ `+ T. {! V* v. f  putchar('\n');
}
//处理产销不平衡的情况
' ^, }! s* N" A% ?1 V  i sum_a=sum_b=0;
1 _2 y9 F+ S& u# n( m5 t8 z for(i=1;i&lt;=num_a;i++) sum_a+=a;
+ \; }) x& ~7 ? for(i=1;i&lt;=num_b;i++) sum_b+=b;</P>
+ \8 W) _! u2 D<> 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);
  b[num_b]=sum_a-sum_b;
, D% ^- {" V; \) H* i  for(i=1;i&lt;=num_a;i++) ab[num_b]=0;
}
else if(sum_a&lt;sum_b){
  printf("\t供不应求，增加假想产地A%d。\n",++num_a);
. M& A9 J7 Q* r* Y  a[num_a]=sum_b-sum_a;
; k  z, [& X# _, u0 a2 s0 T7 S  for(i=1;i&lt;=num_b;i++) ab[num_a]=0;
5 j3 C6 u2 x- b' |. k% u$ ~ }
1 [+ Y0 e9 z0 C( z- P4 X //求解前的准备
for(i=1;i&lt;=num_a;i++)
  for(j=1;j&lt;=num_b;j++)
   base[j]=pbase[j]=0;
, M2 h+ o8 \" `9 Q. ^% C7 d( w# e& b0 G for(i=1;i&lt;=num_a;i++) temp_a=a;
; d; U+ {$ b1 z* ~4 j+ ? for(i=1;i&lt;=num_b;i++) temp_b=b;
& p" C% s- n  W. n; a. t for(i=1;i&lt;=num_a;i++)
: [. I4 j. i7 V/ S! \8 C" d for(j=1;j&lt;=num_b;j++) temp_ab[j]=ab[j];
3 y( i, b& D7 i" C3 {2 G //回显问题
printf("\n\n原问题为：\n\n");
8 m- ~6 k! \8 ?+ X4 M   printf("产量：\n ");
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);
printf("\n运价为：\n");
) [  h0 `5 e; K4 D! I for(i=1;i&lt;=num_a;i++) {
  putchar(' ');
4 }* ?. a; j: ]/ o, D" w  for(j=1;j&lt;=num_b;j++)
   printf("A%d-&gt;B%d:%lg\t",i,j,ab[j]);
  putchar('\n');
" H* Z" d2 k! z" H3 [ }
}</P>
) p" @0 Q% b/ ^, h# w<>double dabs(double d) {
* n1 X+ B: J7 n3 W" s( _8 s if(d&gt;=0) return d;
else return -d;
}</P>
, f4 p- f" C# \; ~2 ^; X<>void findinit() {
int i,j,k;
4 E5 v' a2 e9 I double r_penum[MAX],c_penum[MAX];
struct largest {
  char rc;
6 s: M% w+ ]) |- d  int num;
  double value;
, D; g, |2 R. c8 H* O0 Y };
struct largest lar1,lar2;
int r=0,c=0;
4 ?  q7 J+ {+ h- D double a1,a2,b1,b2,temp;</P>
<> for(i=1;i&lt;=num_a;i++) {
  temp=temp_ab[1];
7 d( i: ^( U. @+ k# f4 M  for(j=1;j&lt;=num_b;j++)
: R8 v/ m4 z4 P% ?1 {. _! Q% |/ T- |   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
5 Z8 T6 o, b/ B  U+ d, Y  a1=a2=temp;
" k3 F- Z' W5 p, u' ?6 ^  for(j=1;j&lt;=num_b;j++)
   if(temp_ab[j]&lt;=a1) {
    a2=a1;
    a1=temp_ab[j];
   }
/ }* M0 E- U1 a8 z   else if(temp_ab[j]&lt;=a2) a2=temp_ab[j];
! E/ X, g2 B2 u4 C  r_penum=dabs(a1-a2);
) P1 b8 ?' j3 G) N }</P>
<> for(i=1;i&lt;=num_b;i++) {
  temp=temp_ab[1];
4 P0 J+ ~& G0 |, s% p/ d8 U  for(j=1;j&lt;=num_a;j++)
   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
% P) i* A5 Y: w5 \  b1=b2=temp;
" p9 c- ]5 k* y  ?# U& V  for(j=1;j&lt;=num_a;j++)  
# o7 r7 b" H0 d- R1 `. n' w   if(temp_ab[j]&lt;=b1) {
    b2=b1;
    b1=temp_ab[j];
/ l4 q* z- ^8 k   }
3 t3 x, C! d  Y& w: Z$ n# N   else if(temp_ab[j]&lt;=b2) b2=temp_ab[j];
4 `" s* X, p6 {5 H* Y  c_penum=dabs(b1-b2);
: V; ^0 c8 y! }  ] }
$ r8 f9 c  y7 b% \6 V3 f0 S /*
for(i=1;i&lt;=num_a;i++) printf("pa%d=%lg ",i,r_penum);
4 [" I) g4 Q( |* ~; B" _ putchar('\n');
for(i=1;i&lt;=num_b;i++) printf("pb%d=%lg ",i,c_penum);
4 u$ d1 F3 s: g5 Q */
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>
<> //考虑了有两个罚数相等的情况，大于两个相等只取其中两个进行比较
  w2 I0 y9 f$ e. ]% W1 B lar1.value=lar2.value=temp;
. I3 d: B% D. i, J; d$ H" x3 | lar1.num=lar2.num=1;
lar1.rc=lar2.rc='r';
! Z8 J* W8 {+ k6 j for(i=1;i&lt;=num_a;i++)
  l! W# J4 S2 p5 k4 s! O1 \  if(r_penum&gt;=lar1.value) {
   lar2=lar1;
# z4 Q% r) `1 n. x% \6 I3 W   lar1.rc='r';
* k. o8 x& X* g: O   lar1.num=i;
   lar1.value=r_penum;
3 e! f7 r+ P5 |, H  }
  else if(r_penum&gt;=lar2.value) {
   lar2.rc='r';
   lar2.num=i;
3 u5 c/ y  J3 i' M2 O3 K/ w* V& r   lar2.value=r_penum;
  }</P>
<> for(i=1;i&lt;=num_b;i++)
  if(c_penum&gt;=lar1.value) {
   lar2=lar1;
  K& n. s+ s" z" D   lar1.rc='c';
   lar1.num=i;
   lar1.value=c_penum;
  }
  r8 B, U/ Q* h5 M  else if(c_penum&gt;=lar2.value) {
9 K5 H0 }7 r! z6 c. p. |   lar2.rc='c';
   lar2.num=i;
   lar2.value=c_penum;
+ Z4 _4 p  U- Q! l% f# q  }</P>
<> if(lar1.value==lar2.value&amp;&amp;(lar1.num!=lar2.num||lar1.rc!=lar2.rc)) {
6 k3 |; c1 C8 p  if(lar1.rc=='r'&amp;&amp;lar2.rc=='r') {
' T! ?- F! ^6 [0 D   temp=temp_ab[lar1.num][1];
# F8 M6 ~; I4 b' {8 Y" I  t( g( {   r=lar1.num;
      c=1;
   for(i=1;i&lt;=num_b;i++) {
3 _: ?) S; x. {% _$ D2 M2 T# @    if(temp_ab[lar1.num]&lt;temp) {
     temp=temp_ab[lar1.num];
) l# [3 G/ R2 z  i3 H! x     r=lar1.num;
; v6 I" u! g4 K, a     c=i;
$ s; [" z* @) O8 D. r5 @0 ^    }
/ ^8 u. {1 @) H) W    if(temp_ab[lar2.num]&lt;temp) {
" \& _7 b; k# y     temp=temp_ab[lar2.num];
0 v/ `+ Z2 [" w( j- E1 Y5 X/ Z* y     r=lar2.num;
     c=i;
: g! s' E. T( |    }
   }
2 a& q+ M, @  }  }
  if(lar1.rc=='c'&amp;&amp;lar2.rc=='c') {
  Z7 Z5 ~: i% W1 Q# x8 N   temp=temp_ab[1][lar1.num];
   r=1;
3 D/ e9 |! \5 b4 T. _+ w% c/ ?      c=lar1.num;
0 ~( p4 \6 j9 w% k   for(i=1;i&lt;=num_a-1;i++) {
    if(temp_ab[lar1.num]&lt;temp) {
5 u7 `1 t9 Q& i7 w, e3 c) h     temp=temp_ab[lar1.num];
     c=lar1.num;
: I% W) Q8 P% e; I2 |7 B     r=i;
/ r' F% s) G" O; x0 `2 }    }
, f" Y' [. Z. g) N1 D9 L1 K    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
7 O: u# T% I; W3 A5 i     c=lar2.num;
' [- U; u$ x; h  H     r=i;
3 E  D0 L' v/ K3 G    }
3 ]: C2 q# R9 A2 Q, `   }
  }
# E% N9 a; }, D% ]9 X  if(lar1.rc=='r'&amp;&amp;lar2.rc=='c') {
   temp=temp_ab[lar1.num][1];
   r=lar1.num;
( p! N* \9 X( u1 |3 c$ A      c=1;
. R! p: z! A* `   for(i=1;i&lt;=num_b;i++)
    if(temp_ab[lar1.num]&lt;temp) {
5 B+ V& H' V' D3 R8 Y5 X5 Q: w& X     temp=temp_ab[lar1.num];
' i  K: @* d, ]$ E$ J) K     r=lar1.num;
7 m0 ~. O: I) _4 r* G* M     c=i;
8 V0 T. H! t/ s    }
   for(i=1;i&lt;=num_a;i++)
. M! ~# ^7 |. F2 c! f1 z    if(temp_ab[lar2.num]&lt;temp) {
$ a& U1 t+ A+ D* @! q! v5 g     temp=temp_ab[lar2.num];
     c=lar2.num;
     r=i;
% ^( q( C  A* f9 U% V- q    }
6 O! H6 I# ]8 i& t  }
' ~1 @6 F! \  N/ C! |9 Q5 s8 @  if(lar1.rc=='c'&amp;&amp;lar2.rc=='r') {
9 O% {9 g1 a; S# g2 k   temp=temp_ab[1][lar1.num];
8 j7 I* `* o2 U* F. C   r=1;
$ X3 F- p& v# {9 A/ k5 z% x      c=lar1.num;
   for(i=1;i&lt;=num_b;i++)
9 v5 ?; }% J" ?6 P6 u( x) X    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
8 q( e5 q8 v- n, w; ^     r=lar2.num;
     c=i;
    }
   for(i=1;i&lt;=num_a;i++)
    if(temp_ab[lar1.num]&lt;temp) {
     temp=temp_ab[lar1.num];
     c=lar1.num;
     r=i;
    }
, _: Z/ M3 O+ \) ~7 h2 m: n  }
. u# R# W6 V7 g9 ]# @+ q3 |' I }
) ?" D. T- b& M; q3 H else {
  if(lar1.rc=='r') {
   r=lar1.num;
) J9 m( Z6 I8 V9 _   c=1;
/ g+ a8 {) o  A/ P7 g   temp=temp_ab[lar1.num][1];
  v6 Y4 [' o4 N   for(i=1;i&lt;=num_b;i++)
3 k( T8 F2 V1 o. o. n3 h    if(temp_ab[lar1.num]&lt;temp) {
     c=i;
     temp=temp_ab[lar1.num];
0 @; F. A2 {% }  u/ j0 m    }
. K* h; H. t" V  }
  else {
' w, D" w5 X1 ~+ G9 C   r=1;
! s( U. b. Q7 P3 k: G   c=lar1.num;
   temp=temp_ab[1][lar1.num];
   for(i=1;i&lt;=num_a;i++)
    if(temp_ab[lar1.num]&lt;temp) {
* p+ B5 y) Y/ P7 G" ?5 X     r=i;
1 l0 L( |3 u, ^7 K) j& g4 q     temp=temp_ab[lar1.num];
. h' z- N; i/ ]; Y- ]. A( P$ F    }
  }
3 a6 d5 X* B) x4 j$ K }
* B& _  R2 {' s3 V/ L pbase[r][c]=1;
6 g+ D# `0 `1 \. M" U if(temp_a[r]&gt;temp_b[c]) {
& ?" \1 b# Y7 B9 z  base[r][c]=temp_b[c];
  temp_a[r]=temp_a[r]-temp_b[c];
( T+ R" h4 p0 p1 ]4 `& S# x& H; x  temp_b[c]=0;
  for(i=1;i&lt;=num_a;i++) temp_ab[c]=M;
; N: u. u9 f8 b1 J }
else if(temp_a[r]&lt;temp_b[c]) {
  base[r][c]=temp_a[r];
+ F! |* ]* S+ e& ?, Z  temp_b[c]=temp_b[c]-temp_a[r];
. U* p4 E5 D1 J  temp_a[r]=0;
  for(i=1;i&lt;=num_b;i++) temp_ab[r]=M;
- C$ y: T8 n5 ~* b/ c& V }
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;
7 c. E& o+ U( p( P" d. S! l  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;
; b* ?/ l6 ^2 }' z. U5 ?/ k' Z  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;}
! o* c% ?, V  J1 k+ Q) ~   if(k==1) pbase[c]=1;
   else if(k==2) pbase[r][j]=1;
+ i% ^. h! `$ f, ^  }
6 A! k" O! o( u# k% j! h }
k=0;
4 w1 o* q7 ~2 {6 \9 d1 P* @ 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;
0 ~) q" N7 {( o" t2 @4 w if(k==0) return;
8 |: W8 a$ c1 @# z$ S9 Z findinit();
' ?- r% v, `% ]5 `$ M  Z}</P>
<>void computeuv() {
0 M6 o+ D- O0 m+ @' x int i,j,k;
# h; y  p: U" `, A% J for(i=1;i&lt;=num_a;i++)
  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==1) {
; l% o4 L/ o9 `4 P    if(pu==1) {v[j]=ab[j]-u; pv[j]=1;}
    if(pv[j]==1) {u=ab[j]-v[j]; pu=1;}
   }
k=0;
6 `& D" h1 J) ` for(i=1;i&lt;=num_a;i++) if(pu==0) k=1;
8 f: [/ B$ O7 ?$ m( b" ? for(i=1;i&lt;=num_b;i++) if(pv==0) k=1;
if(k==1) computeuv();
}</P>
! m4 R: D1 @: u$ k6 X4 G8 _  w% O<>int check() {
int i,j,k,l;
6 l6 z# K; l) S6 m+ J k=l=0;
for(i=1;i&lt;=num_a;i++)
  for(j=1;j&lt;=num_b;j++)
6 a, h! q$ r# `7 i3 ~$ q! x; n   if(pbase[j]==0) {
, |' S9 \5 J: G+ ]) K    base[j]=ab[j]-u-v[j];
" U  v% c) t6 W* O- H    if(base[j]&lt;0) k=1;
    else if(base[j]==0) l=1;
$ c$ k6 j& T) e( B, ?& Z' T% D   }
& E# r1 o# T  N) v, G1 W' U4 Y/* for(i=1;i&lt;=num_a;i++){
; f: l, s% W& f* _* Y8 K  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]);
' {' ^4 D. E# X' m  putchar('\n');}
*/
8 g7 x4 q7 E6 P4 a% z% o6 B if(k==0&amp;&amp;l==0) {status=1; return 1;}
else if(k==0&amp;&amp;l!=0) {status=-1; return 1;}
3 U. Q3 ]: O+ z else return 0;
}</P>
<>int circle(enum direction dir,struct element cir[],int *t) {
, e1 x& }# A5 {+ ? int i,j,k;
/*
putchar('\n');
! \* ~5 t% L; ^6 M, L5 N for(i=1;i&lt;=*t;i++) printf("%d: r%d c%d\t",i, cir.r,cir.c);
% c+ O& _  C/ _% d putchar('\n');
*/
. R+ C% j+ }7 b if((*t)!=1&amp;&amp;cir[(*t)].r==cir[1].r&amp;&amp;cir[*t].c==cir[1].c) {
! i9 D% H7 f4 [1 W, E( S  t--;
7 C( R& J. L; f- G% s* `  return 1;
9 w3 c$ H, \, u! s9 C }
0 D. F6 _6 q( Q" p) K0 J/ } if(dir!=down) {
  k=0;
( ^" g5 A0 {  D  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;}
' J3 X3 O( p7 E8 a  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;
7 J: z: l7 [3 s1 F   else cir[*t].value=1;
   (*t)++;
2 d7 t! M8 a  }% ^6 l7 }   cir[*t].r=i;
   cir[*t].c=cir[(*t)-1].c;
7 S; _4 z8 B# y# ?   if(circle(up,cir,t)) return 1;
! b  o# `; _8 h$ L: ^7 N  }
2 l8 r  p% y% `& G+ D }
% p4 c% H& S# o9 I0 s" f 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;
# n& T+ g# a: ?) }* n1 O  if(k==1) {
, N4 X; r% |5 ?   if(dir==down) cir[*t].value=0;
   else cir[*t].value=1;
  J; Z2 t4 K/ Y   (*t)++;
   cir[*t].r=i;
   cir[*t].c=cir[(*t)-1].c;
$ q: D- E! P; ?' F   if(circle(down,cir,t)) return 1;
1 K1 I$ I) _9 S$ m: a  }
}
; Q2 K5 r8 I) v: x if(dir!=right) {
  k=0;
  for(i=cir[*t].c-1;i&gt;=1;i--)
- ?: y7 ?9 k( u0 P/ t5 e   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) {
2 J8 D# t+ F/ X0 C   if(dir==left) cir[*t].value=0;
  e, P4 n4 J  ]4 }. t6 N   else cir[*t].value=1;
   (*t)++;
4 X& f; C& K( J: G6 ?3 f9 W   cir[*t].r=cir[(*t)-1].r;
   cir[*t].c=i;
   if(circle(left,cir,t)) return 1;
+ w3 [, f# i3 G  }
}
if(dir!=left) {
  k=0;
  for(i=cir[*t].c+1;i&lt;=num_b;i++)
2 ?& Z5 i5 ~! I9 q! |% x: g7 F   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) {
( ?1 ?% b. W; u3 g   if(dir==right) cir[*t].value=0;
- ?( S/ L& o4 w& X* |   else cir[*t].value=1;
+ a/ F* Y0 O, p9 Y   (*t)++;
) R6 Q" k9 X0 e3 I& j0 }  w3 g   cir[*t].r=cir[(*t)-1].r;
9 b. G* i- ?* `, D   cir[*t].c=i;
   if(circle(right,cir,t)) return 1;
# S: W8 M7 I. n$ e) R) x  }
}
(*t)--;
return 0;
6 \* e$ D$ A& a/ [4 |" @}</P>
- a: y1 p1 w+ s  V2 a<>void improve() {
5 Q0 K& ?/ Z; L; D int i,j,k,t;
. h8 H" ?' T# E2 P+ A. ]% p struct element base_in,base_out,cir[2*MAX+1];</P>
<> for(i=1;i&lt;=num_a;i++) pu=0;
4 F3 T" C% q8 |0 X+ P for(i=1;i&lt;=num_b;i++) pv=0;
u[1]=0; pu[1]=1;
computeuv();
' u; z! m7 O' G2 E. W if(check()) return;
% e- j. T7 W9 M for(i=1;i&lt;=num_a;i++)
/ D" a( T; Z7 Z9 _) w- x1 Y( J& b  for(j=1;j&lt;=num_b;j++)
1 K. }3 ?, i5 D" D   if(pbase[j]==0) break;
base_in.r=i;
! R1 r( x% _. f: L! y8 u% w' r base_in.c=j;
base_in.value=base[j];</P>
<> for(i=1;i&lt;=num_a;i++)
' m% n1 ~  t. O# J, B  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;
; c' k# @8 x; Z: d0 D/ B    base_in.value=base[j];
. A) n) ^+ A0 E- Y# l) H   }</P>
<> t=1;
cir[t].r=base_in.r;
8 l  ~$ F& P1 K+ |$ q cir[t].c=base_in.c;
cir[t].value=1;
5 I9 l, g" l% \ if(!circle(mid,cir,&amp;t)) {
4 M8 }+ x* a* r# }. n  printf("程序出错！按回车结束");
  getchar();
# n7 C0 @* x1 Q; M  exit(0);
) K: I6 s: Z, _* e" U }
. h# E+ f: L9 `) o0 G2 j6 S t--;
// for(i=1;i&lt;=t;i++) printf("%d:r%d c%d v%lg\t",i,cir.r,cir.c,cir.value);
& x$ a- l" I% S// putchar('\n');</P>
<> for(i=2;i&lt;=t;i++) if(cir.value==1) break;
base_out=cir;
base_out.value=base[cir.r][cir.c];
k=1;
0 }2 c% E" n+ ^5 P! B) U3 D, @ for(i=1;i&lt;=t;i++)
2 ?7 R: Q: V! m5 F) X" x/ t/ u, y  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];
8 D( a' z% ]+ ~3 _; Z   k++;
  }
, Y+ V/ f3 S  |  t( U  else if(cir.value==1) k++;
base[cir[1].r][cir[1].c]=0;
k=1;
, n; X' G# O/ j* u& ] for(i=1;i&lt;=t;i++) {
  if(k%2==1&amp;&amp;cir.value==1) {
- u! f" N6 b/ @' P" i   base[cir.r][cir.c]+=base_out.value;
$ D% m1 J  `, n$ i   k++;
% S9 K* k! A* i& l  }
, W: `4 G( s; {( _8 v  else if(k%2==0&amp;&amp;cir.value==1) {
" Q6 W8 `; V8 D! H$ L- X4 C% q   base[cir.r][cir.c]-=base_out.value;
+ t5 ?( G1 R9 Z   k++;
  }
, v2 q$ h2 y  G$ q: u7 o }
9 e+ L- _/ L+ Z: o, V" F7 B pbase[base_out.r][base_out.c]=0;
pbase[base_in.r][base_in.c]=1;</P>
<> improve();
0 o3 [& @6 [+ o& }2 `& A/ m& g2 H}</P>
<>void output() {
$ [' c( N, R* d int i,j;
- @5 w- s8 O% {0 H/ ^ double sum=0;
+ o* f$ X" t3 F* Y printf("\n运量为：\n");
+ M9 ^# @7 ]) T2 t: H5 }3 @ for(i=1;i&lt;=num_a;i++) {
  putchar(' ');
5 V# v: s4 r. c: D( R  for(j=1;j&lt;=num_b;j++)
* Y( Z) K6 @/ V. r   if(pbase[j]==1) {
    printf("A%d-&gt;B%d:%lg\t",i,j,base[j]);
  d( ~( ^, Y8 K+ {5 n    sum+=base[j]*ab[j];
) ?+ p' q) f( ~   }
3 Y: A: C& o1 E* u) T% D1 H& f  E   else printf("A%d-&gt;B%d:0\t",i,j);
# _1 a: _" I+ i: f- E4 c# |  putchar('\n');
}
printf("\n最低总运费为：%lg\n",sum);
6 ?: {3 }8 b1 t) h}
3 |" B  H% H9 |. e2 n/ e</P>

zhongguohelin

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

enrique08

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

hzlhm

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

liunengwu

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