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

plgatc

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

编程环境：VC++6.0     
+ M/ o, T8 c. d; _4 ^: q* z. r 程序说明：
# M- W7 y& o) f( |. I/ a Vogel法求初始解，位势法检验是否最优，递归搜索闭回路改进解。
& C2 K2 g, a$ x *************************************************************************/
#include &lt;stdio.h&gt;
8 O$ S- e0 C* w1 F# r, O#include &lt;stdlib.h&gt;</P>
" e  E' P; z: E* a; b# l<>#define MAX 100
#define M 999999</P>
. B5 g7 j" L8 J  y<>int status; //1唯一最优解，-1无穷多最优解</P>
<>int num_a,num_b;
double a[MAX],b[MAX],temp_a[MAX],temp_b[MAX];
, o9 b9 c0 I/ h) s' }- _double u[MAX],v[MAX],pu[MAX],pv[MAX];
7 N3 N7 ~2 L8 W6 pdouble ab[MAX][MAX],temp_ab[MAX][MAX];
double base[MAX][MAX];
int pbase[MAX][MAX];
% _, F" L3 Y3 astruct element {
int r;
int c;
double value;
};
+ n; h% I" Z3 n2 qenum direction {mid,up,down,left,right};</P>
<>void create();
0 Z  d( s9 I$ f, M  gvoid banner();
double dabs(double d);
% T( `  o, o* _6 K# Evoid findinit();
% L; [: g! Z9 l4 ^# Y( @4 Evoid computeuv();
+ w6 Y! q, s6 n, d0 h6 |& i/ gint check();
8 f. u8 U! g: p/ H6 iint  circle(enum direction dir,struct element cir[],int *t);
void improve();
9 @; H% F& j5 Q7 E+ |9 bvoid output();</P>
! q" I- i. k& k4 }' u7 F<>void main() {
banner();
create();
1 n3 x$ l: j2 f printf("\n按回车确认后开始求解");
getchar();
getchar();
findinit();
  t8 r# q7 o, o" O: M; S( b: v improve();
switch(status) {
case 1:
  output();
. c2 c& [8 N7 |9 M: e: B! K  puts("\n原问题有唯一最优解。\n");
  puts("\n按回车结束");
  getchar();
  exit(0);
case -1:
  output();
6 @0 Q7 L! W% x4 ?# N  puts("\n原问题有无穷多最优解。\n");
  puts("\n按回车结束");
  getchar();
; y; E, {; x& w" O  exit(0);
}
" Q& {& ?' A. ?. L) P6 V) ]/ N}</P>
<>void banner() {
$ `$ ~6 n! @/ s printf("\t\t****************************************\n");
/ y3 I; i& c! ?/ }) R+ k* e printf("\t\t         表上作业法解运输问题\n");
; u5 n' i, n2 o; b( [. [! n printf("\t\t                              Thunder\n");
, W9 A* U7 i7 R9 |0 s! z printf("\t\t****************************************\n");
printf("\n");
, v) s9 I- D4 X+ g}</P>
9 u: b, T1 K8 ?/ F8 p<>void create() {
int i,j;
8 }1 c6 T+ t  ^1 q0 i double sum_a,sum_b;
4 r8 e+ s. {: w% \4 n" E- N char confirm;
& j- D1 e4 r  Z5 e while(1) {
  printf("请输入产地个数：");
) n6 w! Y' Q! z  scanf("%d",&amp;num_a);
6 _+ a: g. u2 l5 \$ _# @  for(i=1;i&lt;=num_a;i++) {
   printf("A%d产量：",i);
   scanf("%lf",&amp;a);
  }
  for(i=1;i&lt;=num_a;i++) printf("A%d产量：%lg\t",i,a);
  printf("\n正确吗？：(y/n)");
, n1 E8 s; }, C! k  getchar();
  confirm=getchar();
  if (confirm=='y') break;
  else if(confirm=='n') continue;
! B- |; w" f" p' U }
while(1) {
  printf("\n请输入销地个数：");
( v* X8 i$ H' M7 T$ T  scanf("%d",&amp;num_b);
1 p* ?. I) `" Q" k6 V: }  for(i=1;i&lt;=num_b;i++) {
( L3 |5 V) B" A$ ?+ D2 H. L; n" i' k$ K   printf("B%d销量：",i);
  G9 X+ Z/ Y5 z/ \3 c   scanf("%lf",&amp;b);
0 g9 E& |; b/ _# U3 q$ c  }
4 W4 ]: ~+ A; v' p& @: D# U$ L8 Y* {  for(i=1;i&lt;=num_b;i++) printf("B%d销量：%lg\t",i,b);
# G& u2 p9 z0 ^) A# c  printf("\n正确吗？：(y/n)");
- Z) A' A6 Z2 L" |# i% g4 y  getchar();
  confirm=getchar();
  if (confirm=='y') break;
  else if(confirm=='n') continue;
) G9 V$ ^7 O; q  H }
' i' B: v& I6 L. n- [0 E& @, k putchar('\n');
; y( R3 B! T9 n0 g; a6 F: @ for(i=1;i&lt;=num_a;i++) {
/ K: F+ k4 J& `8 P0 m  for(j=1;j&lt;=num_b;j++) {
+ m# O0 ^3 M" y+ D   printf("A%d到B%d运价：",i,j);
  H# z0 q7 s3 h) ~' T   scanf("%lf",&amp;ab[j]);
5 v7 t0 R( B8 u3 [* m  }
  for(j=1;j&lt;=num_b;j++) printf("A%d到B%d：%lg\t",i,j,ab[j]);
* j+ S+ c1 A, C3 _  printf("\n正确吗？：(y/n)");
  getchar();
  confirm=getchar();
  if(confirm=='n') i--;
1 \, A5 z6 b. E. s! d  putchar('\n');
}
//处理产销不平衡的情况
sum_a=sum_b=0;
% e: O% H+ h4 ^% y$ n# u for(i=1;i&lt;=num_a;i++) sum_a+=a;
) w# C# i# S9 F for(i=1;i&lt;=num_b;i++) sum_b+=b;</P>
<> printf("总产量：%lg\t总销量：%lg",sum_a,sum_b);
4 m# z8 I! Z' r( X) \/ K) V/ j if(sum_a==sum_b) printf("\t产销平衡。");
else if(sum_a&gt;sum_b) {
  printf("\t供大于求，增加假想销地B%d。\n",++num_b);
' C" _$ R, h5 Q! Z- I  b[num_b]=sum_a-sum_b;
  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);
  a[num_a]=sum_b-sum_a;
( n6 \# E% h$ _3 K& `- k3 y  for(i=1;i&lt;=num_b;i++) ab[num_a]=0;
- o  q- \% H- m7 j3 k }
//求解前的准备
for(i=1;i&lt;=num_a;i++)
. ^( m4 I/ x5 {* U  for(j=1;j&lt;=num_b;j++)
: a8 S. \. P9 E0 |. v+ M   base[j]=pbase[j]=0;
9 E! E7 w# M% N! j  Z6 E for(i=1;i&lt;=num_a;i++) temp_a=a;
& N( U; y0 m, ~  ^4 H1 @  ` for(i=1;i&lt;=num_b;i++) temp_b=b;
for(i=1;i&lt;=num_a;i++)
+ a+ n5 b1 @9 d7 T& ] for(j=1;j&lt;=num_b;j++) temp_ab[j]=ab[j];
4 y0 b5 T5 j9 {, h //回显问题
- A; q  U: R* S" t! @ printf("\n\n原问题为：\n\n");
   printf("产量：\n ");
for(i=1;i&lt;=num_a;i++) printf("A%d:%lg\t",i,a);
. k/ K& X0 v7 y9 a" l printf("\n运量：\n ");
1 C  D0 E% ~" w. ]+ e for(i=1;i&lt;=num_b;i++) printf("B%d:%lg\t",i,b);
printf("\n运价为：\n");
8 q7 M+ S5 F0 [2 ~: t0 C0 S for(i=1;i&lt;=num_a;i++) {
  putchar(' ');
  for(j=1;j&lt;=num_b;j++)
5 M  r& M6 w% x+ W: w, ?   printf("A%d-&gt;B%d:%lg\t",i,j,ab[j]);
- M# r2 r0 I9 F6 k5 ?/ t$ u4 T# Q/ g  putchar('\n');
0 X( T- g) h7 q9 J/ n3 u) V }
}</P>
" O2 A( y1 @3 e( R- S<>double dabs(double d) {
if(d&gt;=0) return d;
else return -d;
}</P>
" c* [  s% L6 D<>void findinit() {
int i,j,k;
0 F  T# v# v5 f6 Q+ O double r_penum[MAX],c_penum[MAX];
struct largest {
4 k/ i) t  _7 E: ]  char rc;
  int num;
6 x* W3 }+ |- T& U" Z% Q) A, m8 z  double value;
6 x' w" I6 I. d1 | };
struct largest lar1,lar2;
- s& A9 H) t% N0 p7 o4 Y- b& X. {+ o int r=0,c=0;
double a1,a2,b1,b2,temp;</P>
<> for(i=1;i&lt;=num_a;i++) {
- x) J1 x& L/ k, p- s  temp=temp_ab[1];
' y9 m# _3 g. J. P# x7 D  for(j=1;j&lt;=num_b;j++)
7 x7 @8 `: }& w+ t   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
7 R; k  H# `" Y2 M6 a  a1=a2=temp;
, n+ c2 {2 W  @7 D, o1 @. a& {  for(j=1;j&lt;=num_b;j++)
   if(temp_ab[j]&lt;=a1) {
    a2=a1;
* q$ O! s7 |+ z    a1=temp_ab[j];
; @4 O3 i2 V, c9 p' L5 z- W9 V   }
   else if(temp_ab[j]&lt;=a2) a2=temp_ab[j];
  r_penum=dabs(a1-a2);
}</P>
6 Z% z/ j- U2 w* M' n0 }, |/ {<> for(i=1;i&lt;=num_b;i++) {
. Z5 A% ^( G" b  Z! k  temp=temp_ab[1];
, [& m8 f1 {# R( @4 L  for(j=1;j&lt;=num_a;j++)
   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
  b1=b2=temp;
  for(j=1;j&lt;=num_a;j++)  
   if(temp_ab[j]&lt;=b1) {
    b2=b1;
; y( ~2 ~' Z5 b1 @) s! O# g    b1=temp_ab[j];
   }
   else if(temp_ab[j]&lt;=b2) b2=temp_ab[j];
8 T  H: x6 P' c  t  c_penum=dabs(b1-b2);
4 @9 }: s" F, k }
/*
for(i=1;i&lt;=num_a;i++) printf("pa%d=%lg ",i,r_penum);
4 X/ P2 m  y/ [$ ?! M! w* r% j putchar('\n');
0 u) f+ J: @. f/ z for(i=1;i&lt;=num_b;i++) printf("pb%d=%lg ",i,c_penum);
2 ]: T" X) ]4 t, H$ [ */
6 G3 Q6 |* h4 Q; k, E% Q' B temp=r_penum[1];
# H8 }& P* T, G' k for(i=1;i&lt;=num_a;i++) if(r_penum&lt;temp) temp=r_penum;
0 K& Y( d; h2 z for(i=1;i&lt;=num_b;i++) if(c_penum&lt;temp) temp=c_penum;</P>
* w$ v( A4 A5 P$ Z' C<> //考虑了有两个罚数相等的情况，大于两个相等只取其中两个进行比较
/ }, v$ d# v. f3 M( C% i lar1.value=lar2.value=temp;
lar1.num=lar2.num=1;
lar1.rc=lar2.rc='r';
, m2 `7 J: m- {# O for(i=1;i&lt;=num_a;i++)
  if(r_penum&gt;=lar1.value) {
   lar2=lar1;
* D5 T0 y! ?( v  R8 P   lar1.rc='r';
   lar1.num=i;
) k7 D5 |+ C9 W+ c3 N* ^% m) H2 g   lar1.value=r_penum;
6 p+ T" t1 Q6 z1 J0 F  }
  else if(r_penum&gt;=lar2.value) {
/ @" A7 V7 s4 l9 D; r/ Y8 X   lar2.rc='r';
   lar2.num=i;
& `% E3 P; G& w! N' v! n* E   lar2.value=r_penum;
  }</P>
<> for(i=1;i&lt;=num_b;i++)
  if(c_penum&gt;=lar1.value) {
/ Y+ i, g# ~/ e2 w   lar2=lar1;
   lar1.rc='c';
0 a7 D- I- x3 F" l# D" C8 I, ^   lar1.num=i;
   lar1.value=c_penum;
  }
  else if(c_penum&gt;=lar2.value) {
   lar2.rc='c';
   lar2.num=i;
   lar2.value=c_penum;
  }</P>
<> if(lar1.value==lar2.value&amp;&amp;(lar1.num!=lar2.num||lar1.rc!=lar2.rc)) {
4 H  N! d  P! G1 B8 x4 J4 A. F  if(lar1.rc=='r'&amp;&amp;lar2.rc=='r') {
  p0 I" Q" _. x8 X( S1 c% \   temp=temp_ab[lar1.num][1];
   r=lar1.num;
; \* w2 ?6 Q5 t6 M5 a9 z      c=1;
   for(i=1;i&lt;=num_b;i++) {
( t# l6 v) w7 d4 k4 b' @    if(temp_ab[lar1.num]&lt;temp) {
- i* J8 S- p- h, |1 S: }# {: t     temp=temp_ab[lar1.num];
+ k( l; b: a0 P" l0 U     r=lar1.num;
* E- i: N, `0 B6 Z! C     c=i;
    }
    if(temp_ab[lar2.num]&lt;temp) {
# H0 I" r0 w, J& j: v     temp=temp_ab[lar2.num];
     r=lar2.num;
     c=i;
    }
9 _9 l1 F" w# [& X: b  H   }
4 x- d: R! p$ y3 P0 T( `  }
  if(lar1.rc=='c'&amp;&amp;lar2.rc=='c') {
   temp=temp_ab[1][lar1.num];
/ \7 m4 \0 O. M, D" R5 v   r=1;
      c=lar1.num;
   for(i=1;i&lt;=num_a-1;i++) {
# v  _" \& N5 x& d* x    if(temp_ab[lar1.num]&lt;temp) {
     temp=temp_ab[lar1.num];
     c=lar1.num;
     r=i;
9 C" y/ _! F. w% N. D  u    }
) p+ h& q3 l0 `3 b( [8 w" U& O    if(temp_ab[lar2.num]&lt;temp) {
0 n8 E5 Z4 J+ [" Q0 J6 y     temp=temp_ab[lar2.num];
     c=lar2.num;
7 u. a& _* m3 C0 C# {9 z' ]     r=i;
    }
   }
  }
  if(lar1.rc=='r'&amp;&amp;lar2.rc=='c') {
   temp=temp_ab[lar1.num][1];
( W% Y% ?/ o: Q   r=lar1.num;
      c=1;
   for(i=1;i&lt;=num_b;i++)
' O7 C9 t6 H- U, c    if(temp_ab[lar1.num]&lt;temp) {
; \* b2 a# G% t! v1 S     temp=temp_ab[lar1.num];
7 J# b( u% \: W7 ]! l7 h# e     r=lar1.num;
     c=i;
    }
+ N4 L+ ]+ A! |. [7 e# ?; x, C   for(i=1;i&lt;=num_a;i++)
- m( B3 W3 g: B% W# i1 `% P    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
     c=lar2.num;
     r=i;
    }
  }
  if(lar1.rc=='c'&amp;&amp;lar2.rc=='r') {
   temp=temp_ab[1][lar1.num];
   r=1;
# ^0 A0 J) t7 m4 v/ E6 t& p* L9 D5 X      c=lar1.num;
   for(i=1;i&lt;=num_b;i++)
# k. ^9 y# g) j) d. k3 e! _" K    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
     r=lar2.num;
     c=i;
1 J& w2 o+ y7 v* D    }
   for(i=1;i&lt;=num_a;i++)
9 ^% x$ s: W$ p% E/ U0 ^  {    if(temp_ab[lar1.num]&lt;temp) {
     temp=temp_ab[lar1.num];
  ?' H5 t! W% q7 s0 O+ T" d3 d. \     c=lar1.num;
     r=i;
9 Z" d9 r- n- _. N2 a    }
* W+ w2 x$ }2 n! w% o  }
' i: h: H5 T) W2 A9 m! p+ A8 p }
else {
/ C: \' x1 v$ H, v. @: _/ T/ \) u7 u& [/ h  if(lar1.rc=='r') {
+ a7 d2 H$ w$ c) U" E5 K% h* @& i   r=lar1.num;
/ _( t  Z; c+ `, R6 |  q1 z   c=1;
: m% K) n6 P0 S. {5 _& x   temp=temp_ab[lar1.num][1];
   for(i=1;i&lt;=num_b;i++)
8 H( C) R* B) D( _2 E, y0 u    if(temp_ab[lar1.num]&lt;temp) {
     c=i;
     temp=temp_ab[lar1.num];
) o/ h4 |1 j6 t    }
+ C  P* h, S6 `* X8 f  }
0 K& m# X) L4 E4 H& X, S  [# V  else {
   r=1;
   c=lar1.num;
   temp=temp_ab[1][lar1.num];
8 @# ~( O" O! A. t: x) @5 x' `   for(i=1;i&lt;=num_a;i++)
6 E  |4 N( v. d$ r/ u: {7 ~7 N" }    if(temp_ab[lar1.num]&lt;temp) {
     r=i;
# q! C7 [' J( W/ k+ w     temp=temp_ab[lar1.num];
    }
  }
' j  q5 K& V" V7 @! q6 ` }
8 T7 {- s7 J! V" d; ^( n pbase[r][c]=1;
if(temp_a[r]&gt;temp_b[c]) {
) f6 _0 Y  B6 `( D6 K! [  base[r][c]=temp_b[c];
0 @0 ]+ Z4 G- Z' q" i* H  B  temp_a[r]=temp_a[r]-temp_b[c];
% Y/ N7 k; _5 Z; u4 P) {( f% ]  temp_b[c]=0;
* k1 t! o% ?8 O  for(i=1;i&lt;=num_a;i++) temp_ab[c]=M;
: d. S) I4 o8 E, N8 }3 q* k, I }
7 q; V& \" t0 P2 C2 q else if(temp_a[r]&lt;temp_b[c]) {
2 |+ {% @" f  R2 O% V$ }) D  base[r][c]=temp_a[r];
2 t! V- i2 n2 Q8 H! l  temp_b[c]=temp_b[c]-temp_a[r];
( L0 n' [) c3 U: p6 j) {' P7 u  temp_a[r]=0;
  for(i=1;i&lt;=num_b;i++) temp_ab[r]=M;
1 i3 e1 @$ [7 ~/ x( K }
else if(temp_a[r]==temp_b[c]) {
  base[r][c]=temp_a[r];
* F$ ?) J6 H+ R" B" 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;
0 J) C5 y6 l8 y; t% Z& ~6 ]  k=0;
  for(i=1;i&lt;=num_a;i++) if(temp_a!=0) k=1;
* L& ~' q; M2 [9 _6 z3 A  for(i=1;i&lt;=num_b;i++) if(temp_b!=0) k=1;
  if(k!=0) {
) c, |& `) C% \5 F6 E   k=0;
8 a3 B" T6 Y7 _- ?' S% V$ }   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;}
" a2 t8 `- i, h& P. }; A   if(k==1) pbase[c]=1;
8 h1 S. m8 H7 ?/ [' Y5 {, \   else if(k==2) pbase[r][j]=1;
* y. v, Z4 F# C+ L6 F  }
* J  T6 a' R& Y5 _ }
& {0 D& x( X$ h' | 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;
" s3 H' W8 k' Y$ \% M if(k==0) return;
2 D2 D# t2 n: H8 N( v findinit();
2 A/ |; G0 q5 p+ u$ ^/ R}</P>
<>void computeuv() {
int i,j,k;
7 N$ G% x4 f) g1 _. z for(i=1;i&lt;=num_a;i++)
$ Z; Q6 g8 F, r( b8 A2 l5 f  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==1) {
    if(pu==1) {v[j]=ab[j]-u; pv[j]=1;}
    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;
if(k==1) computeuv();
; K& B  H8 }5 \8 \4 g, v" k}</P>
<>int check() {
int i,j,k,l;
k=l=0;
for(i=1;i&lt;=num_a;i++)
  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==0) {
% w7 \# E/ y* n4 {4 |  g    base[j]=ab[j]-u-v[j];
    if(base[j]&lt;0) k=1;
    else if(base[j]==0) l=1;
$ f; z& O' a6 e4 y   }
/* 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++){
  for(j=1;j&lt;=num_b;j++) printf("pbase %d\t",pbase[j]);
  putchar('\n');}
*/
5 q+ n& ^% l: z3 s3 b# Z 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>
<>int circle(enum direction dir,struct element cir[],int *t) {
+ v/ [, A, D& z6 U 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');
*/
/ R/ U9 u: h& y, l if((*t)!=1&amp;&amp;cir[(*t)].r==cir[1].r&amp;&amp;cir[*t].c==cir[1].c) {
  t--;
: _* `4 @: k7 J& p) }4 F; N1 w" D  return 1;
+ M3 x( h0 W+ X1 k  K1 K; B }
if(dir!=down) {
  k=0;
  ?6 Q3 E) k8 `% G1 v: c  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;}
" Q+ x( a1 @' _  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;
   else cir[*t].value=1;
1 e+ s' D1 q  m) D- `   (*t)++;
4 l! J+ y# O, W3 s! e- s2 L   cir[*t].r=i;
8 `  c9 d  M, x+ x% K! e   cir[*t].c=cir[(*t)-1].c;
0 Y' D. n. B8 z6 E" m* e% p+ P2 @7 w   if(circle(up,cir,t)) return 1;
  }
}
; o/ f! ]. {1 h% W, w if(dir!=up) {
" }  B! l  p3 Q0 m  k=0;
  for(i=cir[*t].r+1;i&lt;=num_a;i++)
+ _- O- t) d7 ?+ z' z   if(pbase[cir[*t].c]==1||(i==cir[1].r&amp;&amp;cir[*t].c==cir[1].c)) {k=1; break;}
' u" ~' n  V- }* f  for(j=2;j&lt;=*t;j++) if(i==cir[j].r&amp;&amp;cir[*t].c==cir[j].c) k=0;
5 z3 C9 E1 r6 c7 [# R  if(k==1) {
   if(dir==down) cir[*t].value=0;
! z$ w4 G# A- p( x   else cir[*t].value=1;
   (*t)++;
2 ^+ G5 t7 Q- H   cir[*t].r=i;
& [/ X9 @% f+ F2 h   cir[*t].c=cir[(*t)-1].c;
) m' o1 {* ~( e2 n   if(circle(down,cir,t)) return 1;
  }
7 T8 G" {5 Y% c$ X }
$ J8 E( v0 V: Q9 {7 B. K& p7 ~ if(dir!=right) {
0 r, \* r; o# B( S6 v  k=0;
) s" @% k& w6 Y" l. [+ |  for(i=cir[*t].c-1;i&gt;=1;i--)
( o) {- U- {6 d   if(pbase[cir[*t].r]==1||(cir[*t].r==cir[1].r&amp;&amp;i==cir[1].c)) {k=1; break;}
6 ~' r  Y$ x" ~7 R7 A0 M5 \) V  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) {
6 d( Y1 M* s# ]* j9 O6 r* m   if(dir==left) cir[*t].value=0;
   else cir[*t].value=1;
9 ?3 f8 J9 b+ K   (*t)++;
   cir[*t].r=cir[(*t)-1].r;
   cir[*t].c=i;
2 Y1 C* H2 \8 k" C  Q) N+ u# U   if(circle(left,cir,t)) return 1;
' z. B( t% Q# e+ H  }
}
if(dir!=left) {
9 G' s+ v  N: x) o$ m' ?5 F) ^  k=0;
  for(i=cir[*t].c+1;i&lt;=num_b;i++)
' K" {& c  R# d6 S5 Y8 x0 b( y2 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) {
   if(dir==right) cir[*t].value=0;
2 U+ z/ a* U9 \' `! D  O; f8 U   else cir[*t].value=1;
   (*t)++;
   cir[*t].r=cir[(*t)-1].r;
   cir[*t].c=i;
) g% }" m& C  M! U$ d2 F$ ^: m   if(circle(right,cir,t)) return 1;
9 s/ o) R4 T( `; P7 Q  }
$ R8 k1 w+ N9 ]6 U) W7 A }
/ N9 ?' ]% T. r* x& M (*t)--;
7 Y/ q2 g; o2 I# a, Q return 0;
1 T3 m- n$ Z6 c}</P>
7 t$ h  H1 B1 x0 l. s& U: G3 B% d0 O<>void improve() {
int i,j,k,t;
2 v! e( h4 r. E0 H, L& K! m% p. T4 N/ m struct element base_in,base_out,cir[2*MAX+1];</P>
7 K" m/ b3 [! N  k) J<> for(i=1;i&lt;=num_a;i++) pu=0;
for(i=1;i&lt;=num_b;i++) pv=0;
- {- Q% q& N1 W/ _% B# V u[1]=0; pu[1]=1;
) W) B0 G9 z$ D: G5 |; l+ A computeuv();
- `6 H8 c+ i8 G if(check()) return;
for(i=1;i&lt;=num_a;i++)
1 @2 v8 S8 d; D: b  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==0) break;
! q' x; e. ^; o) o! g base_in.r=i;
' c, X+ ~% u9 s6 h; U8 h/ ] base_in.c=j;
base_in.value=base[j];</P>
<> for(i=1;i&lt;=num_a;i++)
, e( O. e) c2 |; {& u  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;
8 h& z8 u0 d& l* M2 Q    base_in.c=j;
    base_in.value=base[j];
6 Q$ Z3 F6 D- F) B  b   }</P>
" j" i. P2 Q3 ^) o<> t=1;
cir[t].r=base_in.r;
, l; }1 V: a. J cir[t].c=base_in.c;
cir[t].value=1;
+ I; Q: o% _* c$ u. `1 u if(!circle(mid,cir,&amp;t)) {
9 i& q% \: j$ U- z3 d- U! u  printf("程序出错！按回车结束");
  getchar();
% }) A  y# {5 t( h% u  exit(0);
}
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>
- T+ t' K* h1 {9 l: u* M<> for(i=2;i&lt;=t;i++) if(cir.value==1) break;
base_out=cir;
1 O+ S; ]& A# i3 J* O base_out.value=base[cir.r][cir.c];
% T- S5 e0 M4 I% D. C' F& G7 e k=1;
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];
/ @, H* ~$ p5 E& ^  C$ R( _   k++;
/ [( j/ d- |4 K1 Y: P6 Y* d# `. e& E  }
  else if(cir.value==1) k++;
base[cir[1].r][cir[1].c]=0;
k=1;
7 {% Y- d7 o% z8 a7 d 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++;
) @, b# ^) n6 w  }
2 |: I) r5 g9 k5 G/ ]: d  else if(k%2==0&amp;&amp;cir.value==1) {
   base[cir.r][cir.c]-=base_out.value;
   k++;
  }
6 t4 V6 e" \. R7 X }
pbase[base_out.r][base_out.c]=0;
pbase[base_in.r][base_in.c]=1;</P>
7 U$ ^; Z; e5 v8 n, K<> improve();
}</P>
' t$ F  _; {6 X3 i4 n<>void output() {
int i,j;
double sum=0;
printf("\n运量为：\n");
' l6 h* ]% }2 E; a" X7 s; V# T for(i=1;i&lt;=num_a;i++) {
* T) C& x9 c# A6 ~& G  putchar(' ');
- ?  x5 @1 _3 _+ z% k# |( }' g: [  for(j=1;j&lt;=num_b;j++)
0 l6 _; G+ x5 }$ }2 N: W   if(pbase[j]==1) {
0 D; y% i2 z8 Z" f    printf("A%d-&gt;B%d:%lg\t",i,j,base[j]);
    sum+=base[j]*ab[j];
   }
   else printf("A%d-&gt;B%d:0\t",i,j);
  putchar('\n');
1 K# d5 o5 y: g3 j: @) _ }
printf("\n最低总运费为：%lg\n",sum);
}
7 I6 B1 a, N4 ?</P>

zhongguohelin

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

enrique08

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

hzlhm

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

liunengwu

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