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

plgatc

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

* x% y+ u2 d, |: ^$ m# P$ `7 H$ u 编程环境：VC++6.0     
( a. \; Z! \! H( d0 o: t 程序说明：
Vogel法求初始解，位势法检验是否最优，递归搜索闭回路改进解。
*************************************************************************/
% E- f+ z  a! _  ]8 H8 }9 U- G4 C#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;</P>
<>#define MAX 100
#define M 999999</P>
<>int status; //1唯一最优解，-1无穷多最优解</P>
<>int num_a,num_b;
double a[MAX],b[MAX],temp_a[MAX],temp_b[MAX];
double u[MAX],v[MAX],pu[MAX],pv[MAX];
double ab[MAX][MAX],temp_ab[MAX][MAX];
8 F0 X0 _& r/ X+ Tdouble base[MAX][MAX];
# L  h, T, ~- wint pbase[MAX][MAX];
struct element {
' }7 y5 |; W2 Z* E4 g( K" y3 p' J int r;
+ Q; h0 c0 ]) M% F# l int c;
double value;
4 t2 ~$ m" ]' w# Y: P- [};
. g+ e; W- z$ S4 B$ D! henum direction {mid,up,down,left,right};</P>
<>void create();
void banner();
double dabs(double d);
- x% F( z$ F1 x0 r- g8 Evoid findinit();
void computeuv();
8 B* X; Y% y3 |* hint check();
1 x2 W* G$ E" p/ ~, j, K. Zint  circle(enum direction dir,struct element cir[],int *t);
void improve();
/ e2 D+ y+ n4 S. D1 q& g, K' jvoid output();</P>
, l0 s& P$ B8 b+ O5 i<>void main() {
banner();
7 n: e/ w; T9 O6 j+ {2 Y+ C* n2 k/ v create();
/ {# l& [- h" u: W printf("\n按回车确认后开始求解");
5 H% V* ^% z* M! A2 |; ` getchar();
0 }! `- S4 s$ M1 m4 e; L getchar();
findinit();
improve();
9 K4 M) m- [/ t$ w switch(status) {
' z( o$ @1 L+ ~7 Y& B! ^' p case 1:
6 F# M9 F9 J8 G9 M* \7 l* C; U  output();
8 i, E9 T2 A' N/ P3 L+ z  puts("\n原问题有唯一最优解。\n");
  puts("\n按回车结束");
  getchar();
; Q. V7 I' N$ A# m* L7 Y  exit(0);
. x+ U: l. t% K! K3 q case -1:
/ }/ o; N$ t1 I0 o( d% e$ Z7 y  output();
1 |5 r8 n0 Q+ A) Z' Y, W. F  puts("\n原问题有无穷多最优解。\n");
0 n. }; I6 i; r# D6 i  puts("\n按回车结束");
4 a, c( [* F7 ^" Z  getchar();
  exit(0);
& Z- x% @8 |9 p }
}</P>
5 n& i- F' ]" g8 l, p* d<>void banner() {
printf("\t\t****************************************\n");
0 m6 _7 s0 ~8 `' c( a9 u printf("\t\t         表上作业法解运输问题\n");
printf("\t\t                              Thunder\n");
printf("\t\t****************************************\n");
5 w/ z2 |* \0 Q" E7 m: ^9 ^ printf("\n");
}</P>
<>void create() {
int i,j;
' I" o( A! U( h  O double sum_a,sum_b;
char confirm;
while(1) {
  printf("请输入产地个数：");
  scanf("%d",&amp;num_a);
  for(i=1;i&lt;=num_a;i++) {
# C; x1 i3 N3 c4 c5 F   printf("A%d产量：",i);
2 v) A. e2 x4 y1 w' K* T& Z8 Y   scanf("%lf",&amp;a);
  }
& X& s5 L5 r4 ?; ]; @  for(i=1;i&lt;=num_a;i++) printf("A%d产量：%lg\t",i,a);
  printf("\n正确吗？：(y/n)");
$ j* x1 b2 L* Y" W: Q/ H0 u  getchar();
6 P& ~6 m3 m& e$ b/ {# o, Y  confirm=getchar();
  if (confirm=='y') break;
7 Q' q. B) g2 K& X0 L( X  else if(confirm=='n') continue;
3 {! s) v( w! }; K; H. T }
while(1) {
  printf("\n请输入销地个数：");
  scanf("%d",&amp;num_b);
4 l: F( C0 R5 V: W/ s1 d8 p* B2 F5 x  for(i=1;i&lt;=num_b;i++) {
) ?/ R" Q" k8 U/ {9 j1 x6 y   printf("B%d销量：",i);
# B% R8 ?. Y# a; w   scanf("%lf",&amp;b);
  }
  for(i=1;i&lt;=num_b;i++) printf("B%d销量：%lg\t",i,b);
) }9 F6 H% M! n6 ]3 Y% s0 Y# ^3 s  printf("\n正确吗？：(y/n)");
& ^5 _5 U) [( r$ a  getchar();
  confirm=getchar();
* c' T: R7 s9 g' }: _$ _5 W: @3 }# l. _  if (confirm=='y') break;
9 r+ o5 c# J- n: T# _9 F7 `  else if(confirm=='n') continue;
}
1 C! B: ^, ^0 S: W' m putchar('\n');
5 l/ s/ @$ j( r, T8 j for(i=1;i&lt;=num_a;i++) {
  for(j=1;j&lt;=num_b;j++) {
5 _2 z' E/ x- {; G8 N* \3 d' m, |   printf("A%d到B%d运价：",i,j);
" K* g0 c5 H- }# ^: M3 x  R; l4 o   scanf("%lf",&amp;ab[j]);
; \8 e5 w  w; e. q& {, O  k  }
4 \' H4 y- O& c* }+ V  for(j=1;j&lt;=num_b;j++) printf("A%d到B%d：%lg\t",i,j,ab[j]);
6 Z. D& k2 R" w$ {$ V. T  printf("\n正确吗？：(y/n)");
. l, Q% T4 y. ^5 g# e' N  getchar();
  confirm=getchar();
  if(confirm=='n') i--;
5 y4 }9 a$ o5 T1 f  putchar('\n');
3 q1 c: X$ K9 M1 N3 X }
//处理产销不平衡的情况
( i4 f5 t9 D* O$ i+ b) R; h sum_a=sum_b=0;
5 k+ r. A" Z! y* F1 j7 b: r" m 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);
if(sum_a==sum_b) printf("\t产销平衡。");
else if(sum_a&gt;sum_b) {
; H3 L2 l* i: Q" l+ p$ j  printf("\t供大于求，增加假想销地B%d。\n",++num_b);
  b[num_b]=sum_a-sum_b;
, w' S% U1 \& i* d% }  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;
$ V6 q- G0 l2 h. x  for(i=1;i&lt;=num_b;i++) ab[num_a]=0;
! T: O! {; \# _& z, T# b$ J }
$ @9 ?7 W' g+ n* D8 E1 C8 K# O' N# m //求解前的准备
9 o4 L: g& B  v9 Y" ~, S) r" W for(i=1;i&lt;=num_a;i++)
6 _9 \; l$ z5 n# k; D- i8 T  for(j=1;j&lt;=num_b;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];
( n9 L1 N# x8 }5 M1 k //回显问题
printf("\n\n原问题为：\n\n");
   printf("产量：\n ");
+ A3 I1 G( w  M: M* V  z  P for(i=1;i&lt;=num_a;i++) printf("A%d:%lg\t",i,a);
+ i$ @  O$ P" j, }$ b) W. U, T printf("\n运量：\n ");
for(i=1;i&lt;=num_b;i++) printf("B%d:%lg\t",i,b);
printf("\n运价为：\n");
/ T- e2 @' a7 U$ Y2 O! y4 o; Y for(i=1;i&lt;=num_a;i++) {
7 r+ r$ r* b& F) s2 [  putchar(' ');
  for(j=1;j&lt;=num_b;j++)
   printf("A%d-&gt;B%d:%lg\t",i,j,ab[j]);
0 n, I2 K' k- H* J$ A  putchar('\n');
}
}</P>
<>double dabs(double d) {
if(d&gt;=0) return d;
else return -d;
}</P>
) k# s! y1 n3 e: M/ z2 ^7 T<>void findinit() {
# W) N8 d: r* @7 P int i,j,k;
double r_penum[MAX],c_penum[MAX];
2 `% S6 r# D! R3 U! r& ? struct largest {
! A  n+ n2 v% Z3 v) o8 c+ `: f! M- W  char rc;
  int num;
3 {4 q8 N! P7 T$ Q5 a  double value;
" S6 ^  e; a# m- L };
struct largest lar1,lar2;
2 t+ C0 F7 E) J+ P# q% c int r=0,c=0;
double a1,a2,b1,b2,temp;</P>
<> for(i=1;i&lt;=num_a;i++) {
  temp=temp_ab[1];
  for(j=1;j&lt;=num_b;j++)
  o4 z/ k9 l' k; X   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
  a1=a2=temp;
  for(j=1;j&lt;=num_b;j++)
   if(temp_ab[j]&lt;=a1) {
3 R6 L/ F) u% F- B    a2=a1;
0 z2 d! P) V9 l3 w1 S    a1=temp_ab[j];
6 a8 t! c3 y9 d/ X  Y   }
7 z. Y% j% ^9 e  c   else if(temp_ab[j]&lt;=a2) a2=temp_ab[j];
- s0 h) R" x  j  r_penum=dabs(a1-a2);
}</P>
<> for(i=1;i&lt;=num_b;i++) {
: M1 v# i3 Q; b, ^3 w" N  temp=temp_ab[1];
4 ~" @% c0 z+ k' P& e. `  for(j=1;j&lt;=num_a;j++)
   if(temp_ab[j]&gt;temp) temp=temp_ab[j];
  J, T* T) f4 L" r& ]# M  b1=b2=temp;
  for(j=1;j&lt;=num_a;j++)  
" f8 {' \! w+ p5 @   if(temp_ab[j]&lt;=b1) {
1 H5 O& k6 U" a  Y6 a1 g2 j    b2=b1;
8 Y  V( @$ h1 W    b1=temp_ab[j];
   }
9 {! I7 ^; O* k   else if(temp_ab[j]&lt;=b2) b2=temp_ab[j];
7 p; ]  @  j3 v3 Y+ s3 F* z! [  c_penum=dabs(b1-b2);
}
/*
, b3 Q1 w6 A4 l 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);
5 e2 F  S9 \* B  ?  n' P */
4 w8 p/ |( e5 J) K  S2 u3 F: p temp=r_penum[1];
6 U, L: _! J( I6 E! J 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>
/ t) W6 F. f: v; g8 N6 |<> //考虑了有两个罚数相等的情况，大于两个相等只取其中两个进行比较
+ ^% }9 y, a0 N, g: `$ Q  q lar1.value=lar2.value=temp;
$ i- B2 N5 ?" S( Y2 X* U8 g$ u lar1.num=lar2.num=1;
/ b4 O' ^3 N- `' E) f, e9 D* C* g& b$ C lar1.rc=lar2.rc='r';
$ U! B% C! o2 d2 k% U for(i=1;i&lt;=num_a;i++)
  if(r_penum&gt;=lar1.value) {
1 p: O" W- o( U; R. l   lar2=lar1;
   lar1.rc='r';
+ }. W/ g3 ]8 A& d# }6 Z   lar1.num=i;
   lar1.value=r_penum;
7 S  G+ [+ K4 J4 I  }
2 S7 D9 C/ \& s0 ]  else if(r_penum&gt;=lar2.value) {
   lar2.rc='r';
9 [+ M- j# H: {1 V  X& O  G2 l   lar2.num=i;
8 i- f1 S3 \, ?+ w3 h( M9 }' o0 Q   lar2.value=r_penum;
  U0 i" m( [8 D* S  }</P>
  L& M: p5 Y% P7 d3 D' F<> for(i=1;i&lt;=num_b;i++)
. O- s( s: X9 C0 a! M" w  if(c_penum&gt;=lar1.value) {
   lar2=lar1;
8 B+ P: ]8 r# v8 W6 E9 n; P$ E   lar1.rc='c';
/ j8 s/ N4 X, g6 B, j   lar1.num=i;
   lar1.value=c_penum;
  }
7 r8 V0 e& J3 N5 _% P. k0 ^  else if(c_penum&gt;=lar2.value) {
   lar2.rc='c';
# n5 {! L6 D' u5 O) I   lar2.num=i;
; y- O, L2 }- }   lar2.value=c_penum;
  }</P>
<> if(lar1.value==lar2.value&amp;&amp;(lar1.num!=lar2.num||lar1.rc!=lar2.rc)) {
4 A4 J% w) E: p$ w. q: |  if(lar1.rc=='r'&amp;&amp;lar2.rc=='r') {
& e; Q# d$ C& _. P% x   temp=temp_ab[lar1.num][1];
$ p- j8 O7 r  ]; X. @* ^: O7 U% D   r=lar1.num;
3 h/ ]5 H' s! V+ E. i; x      c=1;
   for(i=1;i&lt;=num_b;i++) {
0 E( [* d) j' k1 a2 R2 u    if(temp_ab[lar1.num]&lt;temp) {
     temp=temp_ab[lar1.num];
     r=lar1.num;
7 l; F, _, u) Q+ n2 o3 G     c=i;
  |* g. R. m- \1 b    }
    if(temp_ab[lar2.num]&lt;temp) {
$ K6 f" T+ }+ T: w# `% E. U     temp=temp_ab[lar2.num];
' ^; W- i* L1 d! G     r=lar2.num;
     c=i;
; v2 k' x' H% s+ F, ^4 q    }
   }
7 g$ w1 C) j' k* [  }
7 E) Q0 [' R0 s, j9 f: @# s  if(lar1.rc=='c'&amp;&amp;lar2.rc=='c') {
) f7 X5 H3 d) A( ?( z   temp=temp_ab[1][lar1.num];
   r=1;
$ P8 b/ y- H* G5 J! ^      c=lar1.num;
   for(i=1;i&lt;=num_a-1;i++) {
/ {5 w7 _3 N+ D/ p    if(temp_ab[lar1.num]&lt;temp) {
6 \9 T* A# W8 h9 e! G     temp=temp_ab[lar1.num];
     c=lar1.num;
     r=i;
) D2 y* T7 y' n6 t    }
    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
     c=lar2.num;
     r=i;
    }
$ H8 p/ L6 T/ F4 [; N   }
  }
  if(lar1.rc=='r'&amp;&amp;lar2.rc=='c') {
   temp=temp_ab[lar1.num][1];
% T4 a1 s- a/ z   r=lar1.num;
& B$ F" x; N8 n      c=1;
, Q8 [3 L+ z  G; n. z: ~   for(i=1;i&lt;=num_b;i++)
( {1 F( u) Z0 J: e    if(temp_ab[lar1.num]&lt;temp) {
, h7 R. W/ n$ ^$ t     temp=temp_ab[lar1.num];
     r=lar1.num;
; d# E. l. P, a     c=i;
    }
   for(i=1;i&lt;=num_a;i++)
    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
' x/ C* r2 n$ E; j& r     c=lar2.num;
3 U& W+ k; h& x; W& D4 ~     r=i;
    }
  }
) Y6 ~: L$ |" L$ z, m5 Z* I  if(lar1.rc=='c'&amp;&amp;lar2.rc=='r') {
& D( d: G) h! j5 ]! q   temp=temp_ab[1][lar1.num];
4 P$ A8 t4 o+ v" o   r=1;
      c=lar1.num;
. s2 v' N: r% M9 G8 x   for(i=1;i&lt;=num_b;i++)
7 x  T+ I& v" R6 y- C- K$ X    if(temp_ab[lar2.num]&lt;temp) {
     temp=temp_ab[lar2.num];
, ~8 U% d9 l; u" Q0 \5 g! ]6 g/ w% G/ h     r=lar2.num;
     c=i;
: M+ P; X: y+ d    }
7 y: x  p1 H2 t" h   for(i=1;i&lt;=num_a;i++)
    if(temp_ab[lar1.num]&lt;temp) {
9 {, s6 m# }! S9 R5 m6 R5 h     temp=temp_ab[lar1.num];
     c=lar1.num;
" Y; D/ p! o% J6 X9 Q/ F9 ~$ N  E/ Z5 h6 V     r=i;
    }
. z3 c" V' O- e  }
}
) v$ G) i( }$ p4 f else {
  if(lar1.rc=='r') {
6 I) v0 u( M- F2 x! |   r=lar1.num;
% ]/ [$ n5 K6 _   c=1;
* Q2 y# N/ u" j. H% q8 A* u( L   temp=temp_ab[lar1.num][1];
# P: @1 A6 f, @6 s% x" k   for(i=1;i&lt;=num_b;i++)
- m" H( e% x' f/ ~    if(temp_ab[lar1.num]&lt;temp) {
8 \% K. j5 o5 w& H4 q1 ?, h     c=i;
     temp=temp_ab[lar1.num];
    }
2 N) b1 Y( M6 Z  |  }
  else {
   r=1;
5 M+ L, f. b% ]   c=lar1.num;
! Q2 k* u7 a. Y/ p  |. F   temp=temp_ab[1][lar1.num];
   for(i=1;i&lt;=num_a;i++)
! D( b. p1 T4 r( V; S' I    if(temp_ab[lar1.num]&lt;temp) {
     r=i;
     temp=temp_ab[lar1.num];
% u% R0 k' r+ I6 Z. W8 I    }
  }
+ v1 _  A1 U+ R6 c) u) x }
/ m# \; }4 Q( j/ L) A pbase[r][c]=1;
) ]4 Y7 e* l. V# y9 U! F1 c if(temp_a[r]&gt;temp_b[c]) {
( t+ K, W' L0 U  F2 o: Q3 _  base[r][c]=temp_b[c];
  temp_a[r]=temp_a[r]-temp_b[c];
  temp_b[c]=0;
7 b1 ~1 n) ~& @3 C( |9 k  for(i=1;i&lt;=num_a;i++) temp_ab[c]=M;
}
else if(temp_a[r]&lt;temp_b[c]) {
7 ]/ ~, U7 I0 V1 |" a& d1 Y  base[r][c]=temp_a[r];
  temp_b[c]=temp_b[c]-temp_a[r];
8 v" f. Z6 |2 b  temp_a[r]=0;
  for(i=1;i&lt;=num_b;i++) temp_ab[r]=M;
$ s9 y; M+ _% g$ E1 C }
5 C/ ~& s1 z& ^" b 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;
1 I4 j6 p  U3 D5 Z1 v  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;
  q9 E* T" x& O* J% @: {0 Y  for(i=1;i&lt;=num_b;i++) if(temp_b!=0) k=1;
  if(k!=0) {
3 r- n  C: k; Y$ ^& |   k=0;
   for(i=1;i&lt;=num_a;i++) if(pbase[c]!=1) {k=1;break;}
2 y* Z. l" @1 _/ I+ K% I: ~   for(j=1;j&lt;=num_b;j++) if(pbase[r][j]!=1) {k=2;break;}
   if(k==1) pbase[c]=1;
   else if(k==2) pbase[r][j]=1;
  }
}
" B. j# f: x- j  \* N7 g k=0;
for(i=1;i&lt;=num_a;i++) if(temp_a!=0) k=1;
* y$ M& P4 y$ r$ [ for(i=1;i&lt;=num_b;i++) if(temp_b!=0) k=1;
8 U* _* h( B+ B' F/ {  q if(k==0) return;
findinit();
}</P>
/ X: f  ~' [, i3 Y<>void computeuv() {
int i,j,k;
for(i=1;i&lt;=num_a;i++)
  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==1) {
( G- n* y) v& F    if(pu==1) {v[j]=ab[j]-u; pv[j]=1;}
    if(pv[j]==1) {u=ab[j]-v[j]; pu=1;}
1 o' s( a: v. q/ |2 k) ?   }
+ g: X9 X5 f, R# z k=0;
. F$ Z3 G4 J) ?# g) h for(i=1;i&lt;=num_a;i++) if(pu==0) k=1;
; N& ^8 p3 w5 G+ s5 f for(i=1;i&lt;=num_b;i++) if(pv==0) k=1;
/ I4 d& ~% B. U/ k if(k==1) computeuv();
7 K9 C  d' i' X, \9 F/ T! ^$ H}</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++)
; z: `9 x1 j: N0 {1 \+ e% a: i% p   if(pbase[j]==0) {
    base[j]=ab[j]-u-v[j];
. ~6 Y9 Q! D* [' c; |# i7 Z" D( ]    if(base[j]&lt;0) k=1;
7 e, F, T$ a2 N! W9 N; Z    else if(base[j]==0) l=1;
   }
/* for(i=1;i&lt;=num_a;i++){
4 ~, J+ Y5 K( W1 B# R4 {  for(j=1;j&lt;=num_b;j++) printf("base %lg\t",base[j]);
3 r7 {. Z, k/ @4 G7 L+ J  putchar('\n');}
* |2 F& d+ j* H. W: i6 I9 d for(i=1;i&lt;=num_a;i++){
  j' P' P9 L: O: P2 o  for(j=1;j&lt;=num_b;j++) printf("pbase %d\t",pbase[j]);
1 r4 c& T) }2 j1 j; c. }' i1 n  putchar('\n');}
6 l0 W9 _* t- {1 z*/
  W7 U; F6 J. _ if(k==0&amp;&amp;l==0) {status=1; return 1;}
* P; n! I! d8 }5 S- \ else if(k==0&amp;&amp;l!=0) {status=-1; return 1;}
else return 0;
7 t5 j# q0 m8 w- O" O4 F' p9 U}</P>
8 m8 l' U9 C' Q+ Z- [* ~8 ^% m<>int circle(enum direction dir,struct element cir[],int *t) {
% E6 X( Y: l# j. ~6 X int i,j,k;
, B/ \8 O# U& [" a) @2 F /*
9 O2 |6 c7 t# H! f putchar('\n');
for(i=1;i&lt;=*t;i++) printf("%d: r%d c%d\t",i, cir.r,cir.c);
4 S0 n3 G/ W+ I7 G$ x putchar('\n');
*/
if((*t)!=1&amp;&amp;cir[(*t)].r==cir[1].r&amp;&amp;cir[*t].c==cir[1].c) {
  t--;
6 Z$ H! c+ X; U  ]- P  return 1;
}
. p5 g- j# a+ O/ L0 P6 ^ if(dir!=down) {
1 N. _. E; M. T6 `* G  k=0;
- e( b4 ]* q% X) x) F  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;}
  for(j=2;j&lt;=*t;j++) if(i==cir[j].r&amp;&amp;cir[*t].c==cir[j].c) k=0;
# U% d# ]* F& O. C3 n  if(k==1) {
3 U" p1 @8 ^+ j# @, \' f   if(dir==up) cir[*t].value=0;
   else cir[*t].value=1;
   (*t)++;
   cir[*t].r=i;
# L* {: u. f, h5 ]5 v   cir[*t].c=cir[(*t)-1].c;
* n" K' g" ?' J. Z   if(circle(up,cir,t)) return 1;
6 U" l# [- s0 b0 X/ b6 s  }
}
! I1 y3 e) v0 {1 z if(dir!=up) {
5 O8 w8 g* w4 M1 P  S  M  k=0;
9 b2 ~0 i5 f' M5 C- k  for(i=cir[*t].r+1;i&lt;=num_a;i++)
7 r, ?8 G& j, l/ ?4 a, J4 a   if(pbase[cir[*t].c]==1||(i==cir[1].r&amp;&amp;cir[*t].c==cir[1].c)) {k=1; break;}
* K. A- b; w; Z' M  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==down) cir[*t].value=0;
/ C( o' R- y# i5 @6 m   else cir[*t].value=1;
   (*t)++;
   cir[*t].r=i;
   cir[*t].c=cir[(*t)-1].c;
9 N# [9 L0 b4 c   if(circle(down,cir,t)) return 1;
$ ]/ V$ d) L% i6 I  }
}
if(dir!=right) {
  k=0;
5 R1 u8 X( x, E/ t  for(i=cir[*t].c-1;i&gt;=1;i--)
0 k/ Q1 k+ d6 }5 `# ^+ u   if(pbase[cir[*t].r]==1||(cir[*t].r==cir[1].r&amp;&amp;i==cir[1].c)) {k=1; break;}
8 f$ i) R5 }1 y& s* [  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) {
3 o& s7 J( P, A3 l   if(dir==left) cir[*t].value=0;
# X/ p. }9 G0 ]1 S3 A. _   else cir[*t].value=1;
% h- W8 K$ X( c3 n0 i; }   (*t)++;
9 @' Z. D/ }* ]! \0 H8 d# q4 E9 P   cir[*t].r=cir[(*t)-1].r;
0 C( U3 Q& U8 |/ T; @* [2 l   cir[*t].c=i;
   if(circle(left,cir,t)) return 1;
: B, [- i! E! B5 |! y) C0 C" z  }
}
1 I2 i2 m; I' h if(dir!=left) {
  k=0;
& P: Q' O3 |7 W% P  for(i=cir[*t].c+1;i&lt;=num_b;i++)
: j: q- ^: `, v7 M+ S; \( W   if(pbase[cir[*t].r]==1||(cir[*t].r==cir[1].r&amp;&amp;i==cir[1].c)) {k=1; break;}
# D' R9 d% P9 Q5 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) {
   if(dir==right) cir[*t].value=0;
6 z  n( E0 N0 |' O# Q1 Q   else cir[*t].value=1;
* N( o8 n# _* ^) w; ~. T   (*t)++;
   cir[*t].r=cir[(*t)-1].r;
   cir[*t].c=i;
   if(circle(right,cir,t)) return 1;
* Z, B/ C2 j8 G0 A9 R$ R0 Y. t  }
}
(*t)--;
+ J; W1 w! D  T* K0 @( P, \ return 0;
}</P>
9 i, X% E2 R8 q3 K  {<>void improve() {
int i,j,k,t;
struct element base_in,base_out,cir[2*MAX+1];</P>
7 t1 N# I! C, E" P9 w<> for(i=1;i&lt;=num_a;i++) pu=0;
9 e' w. i8 N# [  Q' O3 ~6 W for(i=1;i&lt;=num_b;i++) pv=0;
u[1]=0; pu[1]=1;
+ O7 u) V3 U6 W! o! X0 i! @ computeuv();
" [$ [  A: [- y, J- O8 a% F if(check()) return;
for(i=1;i&lt;=num_a;i++)
3 ?3 T& S; o& }- `  for(j=1;j&lt;=num_b;j++)
   if(pbase[j]==0) break;
base_in.r=i;
base_in.c=j;
base_in.value=base[j];</P>
<> for(i=1;i&lt;=num_a;i++)
  for(j=1;j&lt;=num_b;j++)
+ S) b* ^; j3 r( l' e   if(pbase[j]==0&amp;&amp;base[j]&lt;base_in.value) {
    base_in.r=i;
: k2 I- s: ~' _2 N    base_in.c=j;
# S; e/ e5 x! i( Z" \+ r    base_in.value=base[j];
   }</P>
<> t=1;
/ s1 z+ N, x* b, w cir[t].r=base_in.r;
- q# _& Y3 h! V/ i. T2 D" v cir[t].c=base_in.c;
cir[t].value=1;
9 n! S4 I' a% X6 c' S0 j if(!circle(mid,cir,&amp;t)) {
& @: C: _' x" x  printf("程序出错！按回车结束");
/ S3 J8 @3 e9 |  getchar();
& ^7 O+ Z5 `  u' K4 f  exit(0);
2 e, B, H, N$ n; x/ d& c }
5 k6 W3 P, l  ? t--;
# y$ i9 L) ?5 v, ^2 ]4 M// 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;
base_out.value=base[cir.r][cir.c];
k=1;
2 q; I/ I5 B" ^ 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;
: K8 }) @( h, b( [" M   base_out.value=base[cir.r][cir.c];
   k++;
5 r8 Z! P% S  ^5 t* q. g  }
# Z5 y& J5 @! y* I  else if(cir.value==1) k++;
base[cir[1].r][cir[1].c]=0;
k=1;
5 S  G' i) D, ], O4 d for(i=1;i&lt;=t;i++) {
) R% P2 @) s! \$ r8 r6 V; C# `: d1 p  if(k%2==1&amp;&amp;cir.value==1) {
- U. ?5 h5 ^: @' Q# k) a! v   base[cir.r][cir.c]+=base_out.value;
1 O  s- A+ g+ e( w0 m. @1 _+ Q   k++;
( I) O4 ?, @8 s' g: Q  }
  else if(k%2==0&amp;&amp;cir.value==1) {
1 F$ j3 s4 m/ [3 a$ ?   base[cir.r][cir.c]-=base_out.value;
   k++;
  }
}
0 z0 b% [: F: b pbase[base_out.r][base_out.c]=0;
4 I3 P. M8 ]* @! O, x pbase[base_in.r][base_in.c]=1;</P>
<> improve();
}</P>
6 m! T# H/ n3 h4 {<>void output() {
int i,j;
double sum=0;
printf("\n运量为：\n");
for(i=1;i&lt;=num_a;i++) {
- ^3 b5 j# U& `/ S6 Q* d6 Q" n  putchar(' ');
8 t- A; D6 I  t* J3 `  for(j=1;j&lt;=num_b;j++)
7 e5 ?1 J1 ?4 d6 P8 T! p   if(pbase[j]==1) {
' q, m/ R4 @+ B* {: d, c    printf("A%d-&gt;B%d:%lg\t",i,j,base[j]);
. L% Q8 ^0 G  R9 \; V    sum+=base[j]*ab[j];
   }
   else printf("A%d-&gt;B%d:0\t",i,j);
  putchar('\n');
}
printf("\n最低总运费为：%lg\n",sum);
}
# N/ \5 C6 M- V7 I</P>

zhongguohelin

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

enrique08

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

hzlhm

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

liunengwu

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