查看: 4657|回复: 4

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

字体大小: 正常放大

plgatc

4 主题	2 听众	19 积分

升级 14.74%

该用户从未签到

电梯直达

1^#

发表于 2005-5-1 01:13 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

<

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

编程环境：VC++6.0
程序说明：
Vogel法求初始解，位势法检验是否最优，递归搜索闭回路改进解。
*************************************************************************/
#include <stdio.h>
#include <stdlib.h>
<

>#define MAX 100
#define M 999999
<

>int status; //1唯一最优解，-1无穷多最优解
<

>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];
double base[MAX][MAX];
int pbase[MAX][MAX];
struct element {
int r;
int c;
double value;
};
enum direction {mid,up,down,left,right};
<

>void create();
void banner();
double dabs(double d);
void findinit();
void computeuv();
int check();
int circle(enum direction dir,struct element cir[],int *t);
void improve();
void output();
<

>void main() {
banner();
create();
printf("\n按回车确认后开始求解");
getchar();
getchar();
findinit();
improve();
switch(status) {
case 1:
 output();
 puts("\n原问题有唯一最优解。\n");
 puts("\n按回车结束");
 getchar();
 exit(0);
case -1:
 output();
 puts("\n原问题有无穷多最优解。\n");
 puts("\n按回车结束");
 getchar();
 exit(0);
}
}
<

>void banner() {
printf("\t\t****************************************\n");
printf("\t\t 表上作业法解运输问题\n");
printf("\t\t Thunder\n");
printf("\t\t****************************************\n");
printf("\n");
}
<

>void create() {
int i,j;
double sum_a,sum_b;
char confirm;
while(1) {
 printf("请输入产地个数：");
 scanf("%d",&num_a);
 for(i=1;i<=num_a;i++) {
printf("A%d产量：",i);
scanf("%lf",&a);
: r6 n. G0 A- ?9 F7 z }% Q8 r6 ?9 `/ j: }, Z4 r" d
 for(i=1;i<=num_a;i++) printf("A%d产量：%lg\t",i,a);8 c& j' ^% N# E, d/ j- ?
 printf("\n正确吗？：(y/n)");
$ H2 _ ^* W0 A. v) n3 }. Q Y6 N getchar();
; A' Z6 x( O$ p% }6 K3 `6 z confirm=getchar();2 G. e9 F* P+ [. k" I" F" d
 if (confirm=='y') break;
! l* s) m5 K9 J2 r4 ]) E else if(confirm=='n') continue;
0 r7 x3 B5 }3 i* m0 { }
$ N9 O9 j4 X& p6 a: C, m; p: ] while(1) {
3 @- _ j3 F% k6 t printf("\n请输入销地个数：");4 h! }& h( G) v; \
 scanf("%d",&num_b);
- q6 ~' t5 R. Y8 @3 k$ T7 x# @2 @ for(i=1;i<=num_b;i++) {5 q& B8 _ a+ \0 R9 ~
printf("B%d销量：",i);
4 Y2 ?) ?1 i: j) i/ v scanf("%lf",&b);0 q' d4 m$ E5 q% T' B
 }
( s8 [( {6 A: p1 k/ E for(i=1;i<=num_b;i++) printf("B%d销量：%lg\t",i,b);6 @- r I5 |6 h e: O
 printf("\n正确吗？：(y/n)");
# C9 b$ t# C2 Y r getchar();8 w6 \; q1 H$ W) g& A
 confirm=getchar();0 L6 c( X2 v/ A9 G1 s7 o
 if (confirm=='y') break;, I; ~) Y3 F5 m4 M
 else if(confirm=='n') continue;) \* R9 U# s6 p. k
}, v; X& P. }) }( Q: t% m
putchar('\n');
, P- g! e0 f1 y+ x1 v; t for(i=1;i<=num_a;i++) { % [- C4 I+ t1 m. h3 h
 for(j=1;j<=num_b;j++) {( n* I& b4 t% |) h* Z& t
printf("A%d到B%d运价：",i,j);
 C' D7 \4 _9 n2 | scanf("%lf",&ab[j]);
0 v: ~1 b' h' T! G. F7 u2 j' `. L3 W }
8 w& j4 Y$ u- b! P; Q8 k for(j=1;j<=num_b;j++) printf("A%d到B%d：%lg\t",i,j,ab[j]);; F8 |' u/ c! M" L5 d6 A
 printf("\n正确吗？：(y/n)");
6 @- [9 g* X7 [1 r getchar();; `1 g8 ?' `8 A
 confirm=getchar();
+ M# h- A' n8 S& Y) H/ Z if(confirm=='n') i--;% e; o* C: Z4 _6 w2 N
 putchar('\n');
6 O" t- v9 M7 C% C3 D& } }
) W" i% w8 s7 P! Q //处理产销不平衡的情况
/ S( e( R& Y8 l w6 W& e sum_a=sum_b=0;
# Y' ^ k# H. F' F5 F# G- a- y/ ] for(i=1;i<=num_a;i++) sum_a+=a;% }% F5 d; Z: Y% _) B
for(i=1;i<=num_b;i++) sum_b+=b;
7 \1 Q# S: h( r( {<> printf("总产量：%lg\t总销量：%lg",sum_a,sum_b);8 P6 k3 A9 V2 M5 Z% p
if(sum_a==sum_b) printf("\t产销平衡。");
: n; L& j+ _0 U: h else if(sum_a>sum_b) {$ x# G4 y4 C+ M, |3 \2 M3 m
 printf("\t供大于求，增加假想销地B%d。\n",++num_b);' I0 Z+ X6 O5 _$ i
 b[num_b]=sum_a-sum_b;
0 O2 t" h% M; |6 A- p) n. ?6 o for(i=1;i<=num_a;i++) ab[num_b]=0;& [; Q, T2 d0 V) Q, k! O
}4 g/ |* D, _/ z9 z+ I" e
else if(sum_a<sum_b){6 Y4 G2 ^3 T8 I+ Y& Y5 s
 printf("\t供不应求，增加假想产地A%d。\n",++num_a);# f9 [2 w9 a3 I/ t4 C: Z" N
 a[num_a]=sum_b-sum_a;
5 H5 m3 w8 `7 n0 y" \+ L for(i=1;i<=num_b;i++) ab[num_a]=0;0 E" i' j8 s2 S; m
}
/ \# _9 s& i3 D5 I! x; o, D4 ^ //求解前的准备
: e& j& f6 }6 }) M; Q for(i=1;i<=num_a;i++)
( G1 U3 {, j: a; m+ ^! @( M( | for(j=1;j<=num_b;j++). ^9 g" {2 @; ~( `8 u
base[j]=pbase[j]=0;/ `! W3 T) S. A/ D# e2 o! U1 I6 C) }
for(i=1;i<=num_a;i++) temp_a=a;
3 W% Z1 b9 d, m; e! f9 t for(i=1;i<=num_b;i++) temp_b=b;
- Q5 L( A d* Y5 @ for(i=1;i<=num_a;i++)" K @: g2 [) b1 c4 [
for(j=1;j<=num_b;j++) temp_ab[j]=ab[j];0 T! c8 F( |* R+ @2 F7 b, O% {
//回显问题1 A( D) d4 r- I8 K. e
printf("\n\n原问题为：\n\n");; h( W; `2 ]$ ]& h( J+ @
printf("产量：\n ");4 R; Y+ T' r f i; R1 s1 ^
for(i=1;i<=num_a;i++) printf("A%d:%lg\t",i,a);3 ]* P& b7 F; R1 l
printf("\n运量：\n ");
" e/ I5 R- p, f* [- i for(i=1;i<=num_b;i++) printf("B%d:%lg\t",i,b);
; q C2 E" k, F8 ]2 Q printf("\n运价为：\n");
$ f0 u! d E9 C8 d8 J for(i=1;i<=num_a;i++) {2 N% c2 [1 Z2 R4 D: ^
 putchar(' ');% B) B) G1 f. ]% y! ?9 U. h
 for(j=1;j<=num_b;j++). A' s6 N x1 S# E
printf("A%d->B%d:%lg\t",i,j,ab[j]);
7 j" e& x h7 B putchar('\n');
. f% q2 u! U& Z' `; H$ R) Y) P }
; u. z9 j$ t5 x3 y% Q; w" e% C}
0 G% M" {# V- T( g3 V% K5 a7 ~<>double dabs(double d) {
# d) w# k: }. g5 D9 e, P2 \ if(d>=0) return d;1 x7 r) b3 I: E) }5 Y. x
else return -d;
% g, B+ R7 g0 F# `7 g+ T5 d' t4 i1 m}( h# `1 K. v' Q4 x$ t
<>void findinit() {/ z1 J* z' b8 G9 F: K
int i,j,k;
; H9 Q3 } Q/ F* {- G0 m8 s double r_penum[MAX],c_penum[MAX];" [$ h9 A2 B& ^: ]/ u5 `* ]
struct largest {
5 u" e; O O2 ]; R char rc;
0 h$ T# p/ k" q int num;6 j* X4 W' l$ {9 D: _5 W7 B
 double value;. Q/ t. d; \3 q3 b7 ~+ y4 W% [; ? e
};, C3 v! a1 t! b& s2 y
struct largest lar1,lar2;
7 O# P+ i! D/ D. w1 W0 \ int r=0,c=0;
8 ~1 n! I5 q0 U( d: }0 ~ double a1,a2,b1,b2,temp;
<> for(i=1;i<=num_a;i++) {
6 {) e5 D) T. j( p' u; c6 a temp=temp_ab[1];
$ a# \7 L# [. R2 |) j+ u3 y# p: p for(j=1;j<=num_b;j++)
; }6 P- U8 N3 H! p# ?" V if(temp_ab[j]>temp) temp=temp_ab[j];/ s; V% ^( U! o! y
 a1=a2=temp;
$ x- ?$ ~6 V5 J( \8 Z9 { for(j=1;j<=num_b;j++)
) |8 p( ^. B% m if(temp_ab[j]<=a1) {
5 ]0 I8 w _" Z( R) o$ D4 J a2=a1;
* S, G1 P) H+ X! p- B# [- Z a1=temp_ab[j];
+ W6 z1 S/ U2 u' I }
7 @6 R$ U2 L( ]* \6 R else if(temp_ab[j]<=a2) a2=temp_ab[j];
/ B3 w9 M8 u0 I. L7 M! L8 O r_penum=dabs(a1-a2);
, H; S4 I6 g* Z }) `% s& v$ M% q
<> for(i=1;i<=num_b;i++) {0 ?! g# b: g( w7 z: h; i
 temp=temp_ab[1];0 ~$ D4 `& Q- N$ ^) T- v8 ?
 for(j=1;j<=num_a;j++) 8 c c9 p5 D. Y1 o' }
if(temp_ab[j]>temp) temp=temp_ab[j];
3 N$ I' l% A5 X2 D, n: N b1=b2=temp;
7 d" [& C M+ q3 U2 H for(j=1;j<=num_a;j++) ) e1 s5 c) ]2 B8 u: ]. V a0 E
if(temp_ab[j]<=b1) {( v; ~' r/ A: T+ r4 w% ^
b2=b1;
% A# U- U# U& F" M" a# O6 _: S b1=temp_ab[j];9 @) d. L3 U8 k: v' O& V$ K; Q
}0 q" q; Z+ e: g/ A% q
else if(temp_ab[j]<=b2) b2=temp_ab[j];/ o5 T4 ?" G/ V! ?
 c_penum=dabs(b1-b2);
& m6 p) G b1 x t' `( A' k6 Q }& H# D2 p8 ]- F# P
/*
1 Q8 E% R/ y/ X' b/ ` G8 S2 ^ for(i=1;i<=num_a;i++) printf("pa%d=%lg ",i,r_penum);& t( b* l& B! j) M# ^2 l
putchar('\n');
* ^$ [* Z& U' @" E# {5 A for(i=1;i<=num_b;i++) printf("pb%d=%lg ",i,c_penum);# P7 f/ l& h f) z* C; m( B
*/
6 m$ u/ {, G* C/ u temp=r_penum[1];
+ |: O4 ~2 _! {1 p for(i=1;i<=num_a;i++) if(r_penum<temp) temp=r_penum;
for(i=1;i<=num_b;i++) if(c_penum<temp) temp=c_penum;
& _0 Y6 Q$ I/ `! x<> //考虑了有两个罚数相等的情况，大于两个相等只取其中两个进行比较
5 j0 @% K6 L2 P lar1.value=lar2.value=temp;
6 K3 U1 ~% h, @ lar1.num=lar2.num=1;# g6 U" J+ z3 }3 T8 l$ E7 s5 o% ]& O
lar1.rc=lar2.rc='r';$ u) M, a% p5 D" p# g, L
for(i=1;i<=num_a;i++)
. V/ m9 P1 y# I6 c1 h8 m& X if(r_penum>=lar1.value) {% `. p8 g$ w' W+ W& m$ V( T+ A$ g% [
lar2=lar1;: Y( w3 f. v5 j# a
lar1.rc='r';$ ?( {9 N( x& j0 `' N5 H$ h3 X
lar1.num=i;
9 `) y) R: J! A; z8 I" i lar1.value=r_penum;
- P& x7 Y# I( [( a }
$ ]( Y* n. }6 K; m) m( H else if(r_penum>=lar2.value) {1 f4 G, A, u9 a }3 o) g( w h( F
lar2.rc='r';, ]! o( j }& u
lar2.num=i;
! } `* J: C' z, |( j7 D4 \1 E lar2.value=r_penum;7 ?- j5 l1 C$ f3 H. X% t) b
 }
9 o7 F( ^& k1 T$ C; G, s- I<> for(i=1;i<=num_b;i++)
6 t, y4 i! M9 M4 O if(c_penum>=lar1.value) {8 c% \) _$ o2 X0 t
lar2=lar1;
1 L' a% x# G& n- I lar1.rc='c';
! a( j5 e# t& w/ {) J lar1.num=i;
( T1 _8 E1 _8 Z( N! m5 l5 t5 ~1 n lar1.value=c_penum;8 y# `& A4 E4 W3 m8 M0 B- Y) ]
 }5 A5 ]1 S4 y; B% [' R1 L4 a
 else if(c_penum>=lar2.value) {
 w/ a: ^2 z+ m: X5 f* }" F lar2.rc='c';! U) d# d) N r" `& X" Z
lar2.num=i;
& ~- R% ?5 d: w. N lar2.value=c_penum;: @) t( O9 M0 [6 q
 }
2 X; ]1 B$ V, B ]! N8 p' ~<> if(lar1.value==lar2.value&&(lar1.num!=lar2.num||lar1.rc!=lar2.rc)) {
# ^, h9 h. j, M5 l if(lar1.rc=='r'&&lar2.rc=='r') {: [! T8 o5 X& \+ F
temp=temp_ab[lar1.num][1];
# o: g2 A# E# k4 X; ]; ? r=lar1.num;
0 g: P! Q7 }6 `) g& l c=1;; f. A" ~; | `& [6 X! f
for(i=1;i<=num_b;i++) {
* C/ q% w4 y5 E8 ]* \ if(temp_ab[lar1.num]<temp) {
9 L) B0 ?! V5 H; ^ temp=temp_ab[lar1.num];, w6 @6 X1 @' o' F
 r=lar1.num;1 T: _: K% ?' X: {( p
 c=i;/ Y T6 ~' a. N! Z
}( ]; j5 W- [1 o/ |
if(temp_ab[lar2.num]<temp) {
( K. {8 N$ }0 R8 u7 z temp=temp_ab[lar2.num];
' S4 k L0 M" T3 | r=lar2.num;
, ^0 B2 `, h& S, |/ F" S c=i;
2 J( d! ]) c- E5 c& b) D }! T7 N& f2 j9 }8 }
}' K @! f" e! ^8 n' r
 }
* K1 N8 Y! d9 F, T if(lar1.rc=='c'&&lar2.rc=='c') {
8 W2 @0 _; D5 l" }/ j# y temp=temp_ab[1][lar1.num];% t w7 x6 _7 _, H6 D2 {! g
r=1;
; X6 r# j5 U* v c=lar1.num;
. X0 Z' P* [. N) l K8 M) E for(i=1;i<=num_a-1;i++) {, u! G' T' F5 r# V3 X `
if(temp_ab[lar1.num]<temp) {
5 H' l) H: M3 c; {6 n: \ temp=temp_ab[lar1.num];1 K/ W# S3 k4 h! f9 n
 c=lar1.num;
7 E" [: X2 N5 J! | r=i;
- J+ B- X. G- ~- @: b" R }
& t/ V. ]# a, \( R! u1 j& [ if(temp_ab[lar2.num]<temp) {3 `6 _; Q! y/ p" w* ^
 temp=temp_ab[lar2.num];7 p: e+ V; P2 x2 L4 [ @: D
 c=lar2.num; n0 S2 j9 b5 y4 B
 r=i;* W, Q2 A2 G3 D- a# H$ C
}
1 B* W4 U/ L& Y* n6 A }
. o' S9 Z$ e, ~, Z2 R3 P& [ }
2 Q2 d* o- x6 k- H7 s/ B* a2 P if(lar1.rc=='r'&&lar2.rc=='c') {
' ]6 c4 \* {8 @! m& I temp=temp_ab[lar1.num][1];
) r( }, n! D: y. n$ Q r=lar1.num;! U4 W( p0 d' D E( s
 c=1;
 O/ p8 a- B2 N3 F* _ for(i=1;i<=num_b;i++)
6 T& m1 s, d( @7 K4 X& T* t if(temp_ab[lar1.num]<temp) {4 \9 T+ \, E/ K
 temp=temp_ab[lar1.num];# I% m- f4 D: V5 W
 r=lar1.num;! I8 }* i( c# n5 C" A
 c=i;
( F' r7 i1 J2 k: P$ E a2 o } v4 A' \. Y. c) K8 x& C. f
for(i=1;i<=num_a;i++)* d0 {) f) ?* e
if(temp_ab[lar2.num]<temp) {
8 J. z) P ?: t; `2 _; u2 |) Y$ a temp=temp_ab[lar2.num];1 S v/ S' P5 }5 c7 w) m
 c=lar2.num;9 \, M* j, `4 @. X+ j; [
 r=i;
 E' `; B3 t) V }0 r* y2 d+ |: u# R! I# Z! @
 }
7 w1 r' W; h' l$ k if(lar1.rc=='c'&&lar2.rc=='r') {
4 x9 z( N# H5 E4 ~# a temp=temp_ab[1][lar1.num];
' y% t' _ r" q8 o& d' ^* ] r=1;
 z \6 B3 B: f3 @" \2 X c=lar1.num;
# J0 s. A" j( r" h+ K3 I) e2 D for(i=1;i<=num_b;i++)
, C/ J1 O! \& B8 Y. x1 h* r if(temp_ab[lar2.num]<temp) {7 [, |. ~, \6 ~; ^2 w' @- k
 temp=temp_ab[lar2.num]; C2 F; Z' A# f4 x+ Y
 r=lar2.num;
; D% l, A3 J, A: h( x c=i;
/ R: p+ k% O+ L5 j; q }) Y, ~; h5 _, _9 O6 a h. ?) y8 |
for(i=1;i<=num_a;i++)9 T9 d1 |- |: v
if(temp_ab[lar1.num]<temp) {
& t: \* G6 `2 }- C' r1 t temp=temp_ab[lar1.num];
3 q' I6 r% J' R% @& F c=lar1.num;$ N6 x1 j0 d, U C g( l
 r=i;
- a2 H% R% s& ]; T9 W }
- K2 \# F0 a$ R" E/ R }7 @3 v( j; N A; v- [1 M. t3 _
}
" ?7 g1 M' Y" z* n' u else {
7 ?( M; z; O& X5 H+ F+ _0 f if(lar1.rc=='r') {+ Z" ]" {6 @6 X9 M# W$ T$ I n
r=lar1.num;' J7 V7 d% y( r* J0 d: E, s
c=1;
+ P% ^2 P+ ]0 t: X0 w' ^ temp=temp_ab[lar1.num][1];
7 `- |$ I/ S4 |5 x! Q% C for(i=1;i<=num_b;i++)
( M5 J; b3 x1 j5 T if(temp_ab[lar1.num]<temp) {# E/ E) [% T; X' F& c9 r
 c=i;
* p* Q( c2 }* P6 J# M, a temp=temp_ab[lar1.num];
6 _% C* T2 E& H" N% X& }+ w }! m$ t/ ~& H2 R' e* n8 ?
 }% @! F( J# a u8 S) j
 else {) P4 x5 e( V( B, m% {% g" K# F0 D
r=1;
' h) G* i" @& j- C3 z c=lar1.num;
 ?& R4 Q$ z' U) J temp=temp_ab[1][lar1.num];
0 V4 h* |0 {6 p for(i=1;i<=num_a;i++) # c A2 @- r$ f/ p- A/ u9 {- h/ K4 `
if(temp_ab[lar1.num]<temp) {: b% r- \( R5 a; D# b' w
 r=i;
( J$ x0 X' c9 C( x# y. M% G; l" | temp=temp_ab[lar1.num];
: R/ U! e2 G8 [: ^/ o5 n/ h }* G4 o z& F9 g8 H% u! @
 }
 }0 ]" `. J2 d6 J+ o }
9 U) g) p8 N. K- w+ h" j pbase[r][c]=1;% |3 g' Q$ t" F- w z+ D7 }. a
if(temp_a[r]>temp_b[c]) {3 \: v1 O* O( Y2 G6 `. _
 base[r][c]=temp_b[c];3 \8 U/ ^! n( @( B
 temp_a[r]=temp_a[r]-temp_b[c];
$ z' e3 e6 Y* F4 ^# q temp_b[c]=0;
 R' @* Z- x" ^7 ]5 Q for(i=1;i<=num_a;i++) temp_ab[c]=M;
7 {6 G* c! f, k2 D1 I }0 z( I( g$ q8 M3 o6 V' |' t
else if(temp_a[r]<temp_b[c]) {' j9 N2 \$ c' ^
 base[r][c]=temp_a[r];
' u1 t- B# H" j; I temp_b[c]=temp_b[c]-temp_a[r];# H# {; _2 U- G5 h" Y
 temp_a[r]=0;
% ]8 V% X5 Z7 q+ Z: d4 V for(i=1;i<=num_b;i++) temp_ab[r]=M;
9 p: q' ?3 H9 _* b }, ?, n8 e. V9 o! u
else if(temp_a[r]==temp_b[c]) {* l8 E# W" V8 P/ }8 ?$ l' Z E
 base[r][c]=temp_a[r];
7 F- J* |3 ^, G% q; Q8 K ~: s' P temp_a[r]=temp_b[c]=0;1 F8 J3 k% |: v0 p8 n$ p
 for(i=1;i<=num_a;i++) temp_ab[c]=M;8 M) T2 d$ S. I5 w
 for(i=1;i<=num_b;i++) temp_ab[r]=M;
0 O* |/ L' Q m \! s k=0;, v* U' o1 A* W/ |( S8 I
 for(i=1;i<=num_a;i++) if(temp_a!=0) k=1;
+ y$ I8 d# S. i# A for(i=1;i<=num_b;i++) if(temp_b!=0) k=1;
' \* H; M0 d9 z! k/ { if(k!=0) {9 d* J Y, C9 e6 U1 ^/ H
k=0;
- @3 H# ?& x! r9 ^; T3 P for(i=1;i<=num_a;i++) if(pbase[c]!=1) {k=1;break;}6 \" {! b" K' m$ b. l
for(j=1;j<=num_b;j++) if(pbase[r][j]!=1) {k=2;break;}
6 U( o z, [% p3 d+ d if(k==1) pbase[c]=1;* @: J d) G+ ~. N: D* w. t
else if(k==2) pbase[r][j]=1;/ s; Z' D2 W: y9 @( P% h
 }
, N8 ?( p2 s4 b: T }
* c0 j1 I; [. [9 m. `& \9 L k=0;* q$ M6 u+ V9 O( {0 O
for(i=1;i<=num_a;i++) if(temp_a!=0) k=1;
" a( ?8 q$ A% y5 r6 w* O4 ^) k for(i=1;i<=num_b;i++) if(temp_b!=0) k=1;* b8 ^$ [4 k3 c& O4 U9 w; O7 ?/ U, x
if(k==0) return;
8 z0 ~ b" W9 M findinit();- x# h4 V* ~) P5 i# x9 I
}% L6 S8 E6 H- O: ?3 \
<>void computeuv() {" b4 O- u; J: G1 ^3 K
int i,j,k;4 `* z/ V1 v3 O$ u& l# i
for(i=1;i<=num_a;i++)$ v* V5 u# G7 `- I. h* S0 U' a6 o
 for(j=1;j<=num_b;j++) $ H J! j- C& h! n" N. ], v5 ~9 t
if(pbase[j]==1) {- y. g6 y6 s5 V# ~% H# g9 F( \
if(pu==1) {v[j]=ab[j]-u; pv[j]=1;}$ F# X5 D8 o% @4 p. j9 I" a$ Z
if(pv[j]==1) {u=ab[j]-v[j]; pu=1;}+ P/ }$ y# w/ k8 @) t a
}# [7 i; X) o2 B3 L. t9 \& N
k=0;5 s, w1 O7 ]* G: w) e/ c
for(i=1;i<=num_a;i++) if(pu==0) k=1;3 t6 Z& R$ M+ g" f! j* L
for(i=1;i<=num_b;i++) if(pv==0) k=1;4 W/ s( N I) i: q' O" X8 D6 _6 k
if(k==1) computeuv();
% u1 n; m, U1 C1 C9 l7 Z. A/ j} S1 N4 O6 u( `+ S$ T$ E" M0 t1 R. b
<>int check() {
. t# s) D' m9 \) ?6 ?( K int i,j,k,l;/ r. s) ^0 ?* n8 z1 I
k=l=0;, h. R) G0 s! k% x* m1 i3 V3 D
for(i=1;i<=num_a;i++)
8 c) n) {, W' B: m% l! I for(j=1;j<=num_b;j++)
6 f0 W F) p9 `" W if(pbase[j]==0) {
4 E7 @9 x( g' r2 q base[j]=ab[j]-u-v[j];
* Y' o, r) E, s$ s! J if(base[j]<0) k=1;
: e0 i6 Z- Q; {. j1 U else if(base[j]==0) l=1;
# P# h; T/ {( ^9 ]: j( Y3 [ }
' M4 C& ?; u {: n$ [/* for(i=1;i<=num_a;i++){3 h% ^1 W' g. A
 for(j=1;j<=num_b;j++) printf("base %lg\t",base[j]);
) |; {* E( I3 O1 a putchar('\n');}
( ?; _: x( X' {! X; M& k for(i=1;i<=num_a;i++){& n5 k5 o, Q* r
 for(j=1;j<=num_b;j++) printf("pbase %d\t",pbase[j]);0 F: w* t; q% p/ a; c8 G$ E
 putchar('\n');}1 |3 q2 r3 g) J7 P( x0 w
*/
! V3 x+ J( f0 v I! X if(k==0&&l==0) {status=1; return 1;}
' c6 u2 x: }: J7 k; L else if(k==0&&l!=0) {status=-1; return 1;}2 z8 F+ D, k0 o. c1 I* C# x9 \
else return 0;- J! P7 R% q* C* l; q5 K. x
}. _- `3 u9 L$ [* |- y' g/ r
<>int circle(enum direction dir,struct element cir[],int *t) {( x1 l) c, ]) q4 s8 }2 L
int i,j,k;9 K7 Y5 d' Y8 T& \( ~4 B' {
/*1 X' v. j/ T9 |8 Z
putchar('\n');' |1 {. E$ p6 f( M/ v7 Z5 X" p, ]" T
for(i=1;i<=*t;i++) printf("%d: r%d c%d\t",i, cir.r,cir.c);
6 E3 R0 Q z8 J- R* A putchar('\n');
4 d* J# d8 P9 S0 G* J( k */
6 X% \' S0 O, v( k% v if((*t)!=1&&cir[(*t)].r==cir[1].r&&cir[*t].c==cir[1].c) {! P3 H2 ?/ v% S+ {- \& E- I5 ]
 t--;
0 N3 O0 {, z" A4 c return 1;5 J5 N& j( e; y, A: j' K2 u
}
$ O; v! u0 X! ~; X/ p( Q9 @6 U if(dir!=down) {( X s9 |6 O0 m N4 J9 ^1 t0 ?
 k=0;
, t7 }9 {' F- S2 J0 Z for(i=cir[*t].r-1;i>=1;i--) ) E3 j: Z% |1 ?
if(pbase[cir[*t].c]==1||(i==cir[1].r&&cir[*t].c==cir[1].c)) {k=1; break;}
 ~- D' h+ r# d- K- U for(j=2;j<=*t;j++) if(i==cir[j].r&&cir[*t].c==cir[j].c) k=0;
+ G- U% N& V$ U$ W if(k==1) {$ I0 s" ?2 Z- ~
if(dir==up) cir[*t].value=0;
% q' z7 T) r" b t: s1 B2 q else cir[*t].value=1;
* t \, A+ U/ O r/ i$ M (*t)++;
$ S. x9 z$ _; u6 L cir[*t].r=i;# @: `* _; d# L& Y/ E6 j) o1 A& ]+ `
cir[*t].c=cir[(*t)-1].c;# H# T7 R* s( e9 N! `9 x
if(circle(up,cir,t)) return 1;. G8 C/ b6 ~ v0 U* f# n; q. m
 }. g" ?8 d( Q1 [0 \
}" ~& @0 h7 u1 O: o
if(dir!=up) {
! h, w3 H, n7 ]. ]. F6 j# Y k=0;# O* e" x4 t: V& Z! \
 for(i=cir[*t].r+1;i<=num_a;i++) r/ e1 q" W+ y2 _4 f+ d
if(pbase[cir[*t].c]==1||(i==cir[1].r&&cir[*t].c==cir[1].c)) {k=1; break;}9 C9 A1 \! T5 F8 e! C, m
 for(j=2;j<=*t;j++) if(i==cir[j].r&&cir[*t].c==cir[j].c) k=0;: R8 @: L# t( r0 z! r, t. J! E
 if(k==1) {
8 } `7 x4 M8 H9 o# B if(dir==down) cir[*t].value=0;
# k( m' f1 M+ W: K else cir[*t].value=1;
- v; J) Y- j2 R% U+ s (*t)++;
8 u+ Y9 E X, @ O* |6 W, r cir[*t].r=i;& R, K& b8 Z2 J2 H
cir[*t].c=cir[(*t)-1].c;" X' s; c/ q1 s( R
if(circle(down,cir,t)) return 1;
+ F* u/ }4 [' E A) a5 e$ I8 @/ X5 c }- {" W3 i N6 ?8 t% ]
}
: F" d W' O6 {5 X' K& c( K. A if(dir!=right) {0 U. L3 C3 E' h6 B4 H) l
 k=0;
2 E+ A N9 v7 o for(i=cir[*t].c-1;i>=1;i--) 1 {' p ~' Z9 Y9 X/ y' H7 j
if(pbase[cir[*t].r]==1||(cir[*t].r==cir[1].r&&i==cir[1].c)) {k=1; break;}' D6 B) T& P3 O0 L6 l. x
 for(j=2;j<=*t;j++) if(cir[*t].r==cir[j].r&&i==cir[j].c) k=0;
! f6 \! W2 W' ?4 ?; B$ v: ^ if(k==1) {. H2 B/ B) A( s8 U, T4 v9 L
if(dir==left) cir[*t].value=0;$ C# d& \" n4 ]4 I
else cir[*t].value=1;
1 k' Y/ Z4 g5 k3 w8 J+ ^ (*t)++;1 |2 V+ F. B1 `! ~* q+ g% e* T+ v9 S
cir[*t].r=cir[(*t)-1].r;
( G W( B' H4 J cir[*t].c=i;) ^5 P& T9 ~" u4 m! ~& C
if(circle(left,cir,t)) return 1;
/ `9 R" Y& y0 W4 S }
9 o1 m. T4 T: g% Q, G }
) u# m3 W3 }/ C# F0 l$ D if(dir!=left) {
4 v' b g& k2 q7 a6 r9 G3 @% c k=0;- K( ~% Q7 Q" A9 ~. ~' w
 for(i=cir[*t].c+1;i<=num_b;i++)
4 S6 y9 T6 `, J* [ if(pbase[cir[*t].r]==1||(cir[*t].r==cir[1].r&&i==cir[1].c)) {k=1; break;}2 O" s4 S' b9 V4 ]: `/ x
 for(j=2;j<=*t;j++) if(cir[*t].r==cir[j].r&&i==cir[j].c) k=0;
- s4 y: k6 |) r/ f if(k==1) {
: z* B+ g G! q1 Q# E2 b: N5 V- c if(dir==right) cir[*t].value=0;
% ~" d2 f& R! r0 T else cir[*t].value=1;1 A3 p( L* G' ~! f4 Q' R! @
(*t)++;
' k2 A) b9 X9 W. E+ s$ U. U: [0 ? cir[*t].r=cir[(*t)-1].r;
 ^0 n z6 E6 h1 x0 m l% [ cir[*t].c=i;
# ?% n. r s* B. R if(circle(right,cir,t)) return 1;
4 e' S+ e. V1 `7 M; ?5 p* B- L6 x }; U$ d) i( O4 w1 R6 w
}
5 a& N! ?; P. T2 H. [3 H3 d (*t)--;$ A% v3 [* j* z2 w
return 0;
/ ^. K% Z+ m1 w! P( g+ |$ {}2 ^& }$ u1 ~2 M/ }- [8 \
<>void improve() {
' l6 l H" M$ N2 b! K int i,j,k,t;
6 u6 i- A1 ~- N9 p3 A struct element base_in,base_out,cir[2*MAX+1];
4 D0 V; Z' P" s5 \ Y<> for(i=1;i<=num_a;i++) pu=0;
) X/ X: [& p% P4 c for(i=1;i<=num_b;i++) pv=0;: s* g, j5 a& S% i
u[1]=0; pu[1]=1;( ^2 z* f/ t& g) `' N% ^3 Z
computeuv();
# a3 L+ w3 X3 g# T9 I$ ~ if(check()) return;# c7 R9 i( f" H& f) `
for(i=1;i<=num_a;i++)
0 H8 Z7 ^0 O: }. T6 x$ O4 f' d for(j=1;j<=num_b;j++)
( l e& E4 G4 M9 t q2 m if(pbase[j]==0) break;! p7 e( R8 h9 M' v
base_in.r=i;
 y1 U" f2 i! _ K6 r base_in.c=j;6 z& b0 d" }1 ]
base_in.value=base[j];/ R0 E6 Z" C# _5 u* ~
<> for(i=1;i<=num_a;i++)
8 _1 B& b2 L# M' v' n3 v1 m for(j=1;j<=num_b;j++)
( S3 Y0 H; `% {; J if(pbase[j]==0&&base[j]<base_in.value) {" `. v5 I- z+ c* h
base_in.r=i;- W* ^( v* d1 m2 n r
base_in.c=j;
7 S% a, q) i. v1 i- E0 e base_in.value=base[j];
4 n' ?0 R( A. w+ m4 f/ o* H }. Y- r+ N) Y3 W, p" z* n
<> t=1;
: k( t( _ R/ H cir[t].r=base_in.r;
) a4 x2 ^& N o8 z8 K% N! g cir[t].c=base_in.c;
1 g) s; j( b# ^5 [8 W cir[t].value=1;% n& k' i1 J. N
if(!circle(mid,cir,&t)) {
4 ~( w2 u- t- h' I printf("程序出错！按回车结束");
9 V! c. m; Q) s5 L# ~4 b( w& M6 v getchar();
* S3 |9 X5 `' a+ g exit(0);* o* d6 I2 l9 S4 i5 C7 W
}
: `( W$ L( p& V1 i( y$ S# ~ t--;, @! _ A* X, F+ X
// for(i=1;i<=t;i++) printf("%d:r%d c%d v%lg\t",i,cir.r,cir.c,cir.value);$ F7 i: }4 ]' ^% Q1 ]+ g7 F, H
// putchar('\n');
8 Q4 x; Z$ P1 k<> for(i=2;i<=t;i++) if(cir.value==1) break;
; B5 |, b1 _# X l base_out=cir;
2 G+ K# b3 }$ I' I. V! S5 V- q7 w base_out.value=base[cir.r][cir.c];
- Q0 H( n6 E4 u: Q. G0 B k=1; L; z& W, c+ G/ [7 f- J5 F6 J5 b6 {
for(i=1;i<=t;i++)% V" `8 D( t) z! ~0 b' D
 if(k%2==0&&cir.value==1&&base[cir.r][cir.c]<base_out.value) {
! c: s/ f3 M) s" z base_out=cir;" {+ L' Z9 a: Q' f+ `2 x1 ~
base_out.value=base[cir.r][cir.c];
3 h. i8 |0 I l% ]1 x+ `/ F k++;5 G. n* G8 r) ?) g! b/ f, I; D
 }( }% H; M3 w3 o( J0 S3 ~, u% |. A
 else if(cir.value==1) k++;, w# C l- m o+ e- n4 Z( ]
base[cir[1].r][cir[1].c]=0;
- X, w( f' ?8 I: k6 j. @' w k=1;8 F! k7 u- T7 I9 ]
for(i=1;i<=t;i++) {
- ]6 b% h( V4 w1 S x if(k%2==1&&cir.value==1) {7 p0 e) M* s5 {/ Q; u
base[cir.r][cir.c]+=base_out.value;
( {# S* M" b6 k& C2 T8 _7 t/ C" Z9 W k++;$ l/ {. s3 z: B3 F. ~7 N- a
 }
1 o* o. V" r# U o6 y else if(k%2==0&&cir.value==1) {
' i8 V6 @ ?) P+ g, h2 Q$ H base[cir.r][cir.c]-=base_out.value;5 h3 H o& @0 g# J
k++;0 h L- I; L- J6 o+ v0 A
 }
5 E: c& }' |$ ? }
' s* f/ J" ~8 D0 _ z* @0 A pbase[base_out.r][base_out.c]=0; B% t9 d% h5 I8 m* q& ]! g- C
pbase[base_in.r][base_in.c]=1; J6 ~) [: ^0 \* ~
<> improve();1 h: c! J1 I3 f$ I \9 `
}+ h+ Q* B; a* g @% R) E
<>void output() {
$ B/ O+ I _$ q& Z- E6 q int i,j;/ U" p. G% l l" }# w5 c
double sum=0;1 m' l, _0 R; U: z# C$ w+ ~
printf("\n运量为：\n");
( }' {/ t# ~6 q ~3 O for(i=1;i<=num_a;i++) {, P6 X7 I5 L4 X
 putchar(' ');& z0 d5 r7 r2 s/ F
 for(j=1;j<=num_b;j++)
! o) R2 L; m, \- k, ^ if(pbase[j]==1) {& d6 |8 V& X/ p9 r
printf("A%d->B%d:%lg\t",i,j,base[j]);
4 F6 F) Z2 u) E% g/ L, v sum+=base[j]*ab[j];
+ d5 V8 i: c! e! }1 S8 ^2 s }
- d/ Q) j% G2 t3 R* b" I g else printf("A%d->B%d:0\t",i,j);
9 Z$ Y( i) x0 W5 b putchar('\n');) L6 b7 U8 i$ @, u, F" j
}
5 z6 C6 `; Z( c) b6 f/ I printf("\n最低总运费为：%lg\n",sum);: W( I n# N$ ^, B; z
}, v" ~- f6 |) F2 v2 C