查看: 4570|回复: 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);9 g/ c) t* ~! ?: k, y
 }
: K& t+ I+ |9 X" Z for(i=1;i<=num_a;i++) printf("A%d产量：%lg\t",i,a);
8 J Q$ {* ~1 X8 j8 ^: c- Y* X printf("\n正确吗？：(y/n)");0 g+ K$ e( x5 ]6 G
 getchar();9 Q$ {8 @0 o" @5 q8 c0 d( b" d
 confirm=getchar();% f) z! R! O3 h$ L* K
 if (confirm=='y') break;
7 y6 E5 D1 K, A else if(confirm=='n') continue;+ n [3 V' `* j" r
}4 {1 M! U2 W" i) m8 A0 v% w! D) F
while(1) {
' o4 R8 Z5 N3 R! p6 }: F$ s printf("\n请输入销地个数：");
% W5 X! c- P# T0 z scanf("%d",&num_b);3 w3 Z. Q# Y" H1 i6 z
 for(i=1;i<=num_b;i++) {8 J' t( A3 g# j% i7 v( h3 j
printf("B%d销量：",i);
: {- m S6 k. \: ` scanf("%lf",&b);
& u+ h# X5 a1 @5 k: z }$ Y$ f( P0 U# y, X Y6 S/ W( B
 for(i=1;i<=num_b;i++) printf("B%d销量：%lg\t",i,b);( Q. g9 j! o9 w( `1 \$ B+ `
 printf("\n正确吗？：(y/n)");
3 H; [# c/ x" |: m4 i, s getchar();
0 c' }/ r9 i9 L confirm=getchar();
) A0 c$ } H- y' w2 D$ x& z4 t if (confirm=='y') break;
6 c0 h9 V( @& n' B. U) {7 w else if(confirm=='n') continue;
 O6 [; ~; M+ T8 G7 M6 j# Q: g }- u4 c" Z" E# v. u& N6 `( `
putchar('\n');/ O3 l: z7 P4 V8 Y$ w
for(i=1;i<=num_a;i++) {
! p1 ~( E5 N0 ] for(j=1;j<=num_b;j++) {
- m. x% J9 M9 f2 l printf("A%d到B%d运价：",i,j);
& C" M) P. l/ c r) o% u scanf("%lf",&ab[j]);
' l/ _4 H% i" v: Y }
1 k- F" {5 r( b" j1 S g, `) b for(j=1;j<=num_b;j++) printf("A%d到B%d：%lg\t",i,j,ab[j]);
+ Y2 J! |2 |! I' W printf("\n正确吗？：(y/n)");5 s2 Z5 ^8 W ^; u/ S9 U' C
 getchar();- t7 s$ z2 c* G6 X" S7 v5 M: H" [
 confirm=getchar();
5 v2 u X" H8 X& T5 g: Z: I if(confirm=='n') i--;
- P# m0 U9 b& F putchar('\n');
& E# u! V: j+ `( R0 n! R5 Y, ` }
' w: m* a) c+ S+ u( W1 T5 _ //处理产销不平衡的情况$ F- ?5 y0 T) c+ ^0 w
sum_a=sum_b=0;
3 Y1 N' O6 K c- K, P for(i=1;i<=num_a;i++) sum_a+=a;
. a) @! v0 L5 d$ E j for(i=1;i<=num_b;i++) sum_b+=b;
9 R5 R4 `3 o6 B" N5 A; c( `; x$ D7 p<> printf("总产量：%lg\t总销量：%lg",sum_a,sum_b);. P* m( j$ ~8 |' G9 k' J( k6 }4 B
if(sum_a==sum_b) printf("\t产销平衡。");6 @0 g! c5 t( K# g1 X
else if(sum_a>sum_b) {! U$ w( f. Q: _8 h
 printf("\t供大于求，增加假想销地B%d。\n",++num_b);: H7 [6 J* E' }* C3 s' D; @
 b[num_b]=sum_a-sum_b;# w3 i* @& v, m: N
 for(i=1;i<=num_a;i++) ab[num_b]=0;
: B) a# o/ ]$ c9 ] }
* j+ B$ J, K+ G& |8 O" w else if(sum_a<sum_b){' x+ X5 I2 m, T% Q4 x+ t
 printf("\t供不应求，增加假想产地A%d。\n",++num_a);2 P+ s! S2 [3 y, @3 a8 u7 w7 |( H
 a[num_a]=sum_b-sum_a;
7 d9 E; Z# ]" k7 z8 m1 T% N for(i=1;i<=num_b;i++) ab[num_a]=0;
+ {, x. @% O! e% ]& y( W9 u( j' R }/ W6 ?! v9 e4 a% z, m
//求解前的准备
0 \$ u; h2 }9 J, x2 N$ I' T for(i=1;i<=num_a;i++)
$ \, c* G1 f2 g! k; f2 ~* K2 j) y6 A for(j=1;j<=num_b;j++)7 s3 H% A$ J# S
base[j]=pbase[j]=0;
" q0 m# M& V) r" e( g for(i=1;i<=num_a;i++) temp_a=a;
& a( C9 o& I9 q4 f0 p% h for(i=1;i<=num_b;i++) temp_b=b;
5 h: ~" c9 t" @, j- k0 d for(i=1;i<=num_a;i++). g N3 L& x0 q3 @1 x9 l" x
for(j=1;j<=num_b;j++) temp_ab[j]=ab[j];
3 a5 v$ A. l0 [% u1 ] //回显问题
 A, P g/ C8 Z: L O printf("\n\n原问题为：\n\n");
# I( M" ^5 e7 M- F# I, J+ X+ i printf("产量：\n ");
, W0 `6 z; X7 s for(i=1;i<=num_a;i++) printf("A%d:%lg\t",i,a); C# _* s5 s' d; o
printf("\n运量：\n ");- T8 y% S) H4 A, X6 i2 C
for(i=1;i<=num_b;i++) printf("B%d:%lg\t",i,b);5 u* n- p" F1 _% s5 }0 o& l
printf("\n运价为：\n");
% U5 T7 Z0 m# y t7 | \ for(i=1;i<=num_a;i++) {
5 w5 H o0 f( f [6 d$ C putchar(' ');0 M- i1 b7 j4 W' B
 for(j=1;j<=num_b;j++)
3 s8 y0 g+ g, B printf("A%d->B%d:%lg\t",i,j,ab[j]);) U; ]' b9 z5 y
 putchar('\n');8 c& e6 ^! s& L5 r7 w+ C1 `2 T: G6 F
}
2 p8 Z1 p7 I- e$ Y$ C" s}
' ~& b5 ]7 t! b8 x4 @<>double dabs(double d) {
9 Y) Q& R- H4 B1 P: u+ E4 q% j if(d>=0) return d;: P8 C) W4 c3 b! \4 ^% g
else return -d;
7 `+ p8 N6 l4 P}
$ H# v, c+ W1 R/ q6 z/ y<>void findinit() {* l$ ^2 ^3 u/ j
int i,j,k;* c( I* R- C% f- ~) h( T
double r_penum[MAX],c_penum[MAX];" F* h/ W" g: a; D8 y+ X+ s
struct largest {
2 p; e- B0 f( c8 K char rc;3 K8 H( Y7 c% l- y. h3 A0 J
 int num;
# r' A' k6 |: x, g b double value;
6 S5 J( [/ j/ e9 q' t+ p };
% a# `2 V4 O8 z$ K: f3 s0 r struct largest lar1,lar2;2 X) N6 V; q8 o" \( l! r) {
int r=0,c=0;& Q% p1 X9 K3 D+ o$ ^
double a1,a2,b1,b2,temp;2 D' ^' p6 N$ J3 U8 @$ V* K* k$ {; o
<> for(i=1;i<=num_a;i++) {
7 m# Z* F& D1 d( X" p) p temp=temp_ab[1];" j" C2 L3 ~1 V
 for(j=1;j<=num_b;j++)# d' Q: ], _5 O+ e6 ~
if(temp_ab[j]>temp) temp=temp_ab[j];
2 \* R/ W! ^8 T a( j. L$ j a1=a2=temp;
7 ~, m. j+ s# R, A6 \ for(j=1;j<=num_b;j++)6 \$ r8 f& o2 P; x4 J% N
if(temp_ab[j]<=a1) {; x/ X3 Q1 q h; V
a2=a1;+ W* F* ?& `" v6 G3 u' ~/ u9 a
a1=temp_ab[j];
/ I) a% A9 [% y9 o }* @2 T: S5 u9 _' n2 @
else if(temp_ab[j]<=a2) a2=temp_ab[j];$ k8 p, G' A+ N% s0 M2 i
 r_penum=dabs(a1-a2);
3 K5 _: C: Z4 A: I% U* D }' i# r7 V! f. C5 V9 u# p( I0 V9 |2 A, l
<> for(i=1;i<=num_b;i++) {
$ N! r7 W- E- ]2 ]2 d3 A temp=temp_ab[1];! @& w4 L" ]' P+ [( v
 for(j=1;j<=num_a;j++) 9 O) d# E$ h! I8 y8 u, I
if(temp_ab[j]>temp) temp=temp_ab[j];
! l" Z: U1 k$ t) s* q b1=b2=temp;! S4 U' g- Z9 a1 Q+ b$ w3 w* C
 for(j=1;j<=num_a;j++) , k5 J' e" Z' w |
if(temp_ab[j]<=b1) {! O+ h! R6 `' q' H" n
b2=b1;
0 B( E1 y' x6 C. o' ~5 S8 @ b1=temp_ab[j];- X6 A0 d2 L* P- e
}* {9 A: `/ O8 L9 u V# Y+ ^
else if(temp_ab[j]<=b2) b2=temp_ab[j];) L1 ?$ @* p# [ b! |/ F7 C
 c_penum=dabs(b1-b2);* J6 A! ?: L) e x
}6 W4 D$ a) g4 M4 n" P
/*
 t+ B# C: O8 @( D for(i=1;i<=num_a;i++) printf("pa%d=%lg ",i,r_penum);* d- f! q8 o8 D0 Z8 A$ K) d
putchar('\n');* O- m( l1 B" I8 L# L: c) S
for(i=1;i<=num_b;i++) printf("pb%d=%lg ",i,c_penum);' X$ @7 }3 a. \ b' I( {
*/
" T7 `0 F. J% M+ e; N+ R temp=r_penum[1];
" b g1 z) n. h for(i=1;i<=num_a;i++) if(r_penum<temp) temp=r_penum;+ J6 S% F0 ~+ b3 @, o) O J
for(i=1;i<=num_b;i++) if(c_penum<temp) temp=c_penum;
" F0 y1 |/ f) {4 u3 M<> //考虑了有两个罚数相等的情况，大于两个相等只取其中两个进行比较" T) S: \" o L' d
lar1.value=lar2.value=temp;
! e: u! y! b; S5 G1 V/ @ lar1.num=lar2.num=1;9 L0 k( ]( v( m$ k1 ^( k
lar1.rc=lar2.rc='r';; {7 i5 I6 o, f5 w2 E* A( y
for(i=1;i<=num_a;i++) 6 ?" y( ?: C( i6 j5 r7 T4 y# o
 if(r_penum>=lar1.value) {4 i- R- D$ \% P7 N7 k1 e$ O
lar2=lar1;
$ E( [8 E' W4 c+ u lar1.rc='r';
3 Y! u2 d A5 Z lar1.num=i;# ~, t k" g: G
lar1.value=r_penum;( V0 H, z% f; m
 }" h! S& f) q: n5 [- Y+ {) @2 u
 else if(r_penum>=lar2.value) {
; ]% B5 M4 R4 z+ B b! n( Q lar2.rc='r';( j6 H: [2 C8 B0 N
lar2.num=i;
( L0 `* E8 p& d; z' t3 v: h/ f% Z lar2.value=r_penum; ^% G9 i" {8 ]/ |" ~/ V* k! W
 }4 H2 I" Y. o- [5 h& u3 L
<> for(i=1;i<=num_b;i++)
6 s7 u! u8 f, V$ Z5 r2 H! D if(c_penum>=lar1.value) {
) @7 E+ q& k- [; @/ a/ d lar2=lar1;: k$ }/ i7 u- S5 G5 c
lar1.rc='c';0 z/ T+ X8 }1 U) h, u
lar1.num=i;
0 R* [! T* J0 ]0 ? N lar1.value=c_penum;1 v% a+ x) Y; f/ I- w/ F
 }
2 e! f e3 d" d% M. _( R else if(c_penum>=lar2.value) {
! |- M2 M& l7 j/ C3 A" R lar2.rc='c';
" g g5 c9 M# d) `$ q lar2.num=i;# W* {! R: ~$ W( {, X7 Q+ d
lar2.value=c_penum;
) ^4 c5 v+ s* E2 c- Y4 r; S3 @, k& o }
% k1 j5 P. \6 b- N$ }<> if(lar1.value==lar2.value&&(lar1.num!=lar2.num||lar1.rc!=lar2.rc)) {
: w/ }% i4 O; e G if(lar1.rc=='r'&&lar2.rc=='r') {
! P# S# G9 T% z8 E }8 W8 @8 \ temp=temp_ab[lar1.num][1];
2 |3 |9 X r' Q1 y7 i. S r=lar1.num;
3 \1 r# N' Y' \* F6 ~' D c=1;
) a3 Z0 S+ }* \ U$ { for(i=1;i<=num_b;i++) {
5 ?' V7 Z' p- W% o& X z6 p, E% N if(temp_ab[lar1.num]<temp) {
+ W6 F9 H" `1 L( H# t temp=temp_ab[lar1.num];* w2 l: O. j! t! U
 r=lar1.num;
5 H& {# ~; X! X) q/ Q c=i;5 c0 e2 b& \6 Q k# U! I2 W3 f
}$ s- V! Z* l$ [
if(temp_ab[lar2.num]<temp) {2 i% L8 f+ q% T8 F; k
 temp=temp_ab[lar2.num];
: y3 m" K5 A; S0 B, ` r=lar2.num;
, |, b+ i# a; Q4 _ c=i;
8 ^7 v! `# z" j }# }$ \% y9 u ]: C' w
}& Q F6 ?/ k) G4 v$ Z7 E* w. T
 }, L5 @8 v$ t) V5 H6 U3 u: K
 if(lar1.rc=='c'&&lar2.rc=='c') {
8 I8 e5 [+ r! r9 u4 W& | temp=temp_ab[1][lar1.num];
5 J8 P* ~; G# F# } b- Q( @, d" p r=1;
5 ?7 P+ S3 {( r: \) n% M9 O3 p c=lar1.num;% P+ A/ P) q" P# {' d( Z
for(i=1;i<=num_a-1;i++) {: E d" o4 C+ b5 c! Z! G: L
if(temp_ab[lar1.num]<temp) {
# B4 f8 E4 P5 M5 ] temp=temp_ab[lar1.num];- d! {# p" Y( t7 y4 k, N+ G$ j
 c=lar1.num;
( O, C a+ F* `$ [ r=i;
9 V/ D* H# U+ v3 l; R }" H A) C; k+ e
if(temp_ab[lar2.num]<temp) {
) ^: z0 O2 I. X3 v5 y6 g) `# T% E temp=temp_ab[lar2.num];* k0 o4 ?' `# B" D c/ a! y2 ]; g" |
 c=lar2.num;' [8 m( Q5 Z6 q3 A- w
 r=i;5 T4 z7 Q* Z7 b* `# p
}
% D# v- {3 {5 s I* @- ^ }
+ ?2 A& ~) G" M2 A8 ~5 J0 E* D }
5 C( `: r) t$ D; E9 Q& _ if(lar1.rc=='r'&&lar2.rc=='c') {: O1 O$ l; S, p
temp=temp_ab[lar1.num][1];
4 L+ W( P7 E% X r=lar1.num;
7 ]- Z+ r, C" ~/ X1 q: G: g4 O c=1;
( B& v4 |! k. l) W6 Q5 U# c/ S for(i=1;i<=num_b;i++)
" o6 T+ s6 D# S! }1 ?; M% ~1 U if(temp_ab[lar1.num]<temp) {
- ? n; h' r/ X! U) s) O4 R7 ^5 I temp=temp_ab[lar1.num]; ^! w0 x, [) P$ \
 r=lar1.num;/ Z, _/ g( q& ^" h5 Z7 U
 c=i;2 [; Y% H5 K5 E* X+ D
}) n. U5 I! q0 l; t9 o) E
for(i=1;i<=num_a;i++)
1 y" I! t: T2 l if(temp_ab[lar2.num]<temp) {+ [3 o/ q( `$ t
 temp=temp_ab[lar2.num];, \5 [9 I( i; Q
 c=lar2.num;
 G. S4 [: h7 B! i3 ~ r=i;
3 h+ \, W4 W- F" H }
$ L. H) Z a0 N3 T2 g9 c' v }
# \, A: j5 ]3 ?. a5 i if(lar1.rc=='c'&&lar2.rc=='r') {! K7 c9 j0 A" c1 j c V% Z: Y8 U4 t
temp=temp_ab[1][lar1.num];' j* o# ?+ V& E. r
r=1;3 e2 a0 _0 R( E/ @! q2 i# F; }
 c=lar1.num;) _; ?7 E$ x4 h2 L% w# O
for(i=1;i<=num_b;i++) $ W! H0 h' F' o d4 H
if(temp_ab[lar2.num]<temp) {& n& Z1 \/ Y% {/ O, F: m# a
 temp=temp_ab[lar2.num];7 C: S# v6 h3 B
 r=lar2.num;7 Y7 u9 p4 g- L! k
 c=i;0 d: M, a" L8 h- v: ]
}
6 P! k0 P4 Q1 `4 o2 e for(i=1;i<=num_a;i++)- D5 u4 O" M" b8 Y
if(temp_ab[lar1.num]<temp) {
9 E3 N% l! }0 V% z2 S8 H temp=temp_ab[lar1.num];# B2 r' g6 _- ^
 c=lar1.num;( z+ f v7 J+ W( g8 ?% e
 r=i;
5 U9 [* H7 a3 Y6 R }
0 S0 s! g ]- U4 O" Z }5 [3 w1 t/ y; n+ b0 W3 k
}
; v8 A# O( U0 a/ `. ?) |0 q! W else {/ _8 b1 x9 e" Z4 ^0 J/ D
 if(lar1.rc=='r') {* X: K1 t4 p3 o$ ]8 G+ ?
r=lar1.num;0 O6 F3 V) V3 c! [; M
c=1;/ t; ]! {) i9 q) L C
temp=temp_ab[lar1.num][1];1 V, b4 V) t' g6 _# ~3 ~
for(i=1;i<=num_b;i++) . H$ ^9 Z! Q: Y) w: k& |- y n, S
if(temp_ab[lar1.num]<temp) {
* d% a! d$ n! }( X( S3 ]% k$ J c=i;
* I$ S0 O* k. e temp=temp_ab[lar1.num];& x5 l3 L* p. n
}
- d9 E2 a: h, v2 a. h) y5 A }
1 l/ @$ {9 ?- s3 {0 J* X! ]% J- d else {' T' [4 v4 l* [8 q& |0 q
r=1;
, s' G; C, e1 ] c=lar1.num;6 Q3 }( n" N- k
temp=temp_ab[1][lar1.num];5 F( ]5 r. @. o
for(i=1;i<=num_a;i++)
# r! _. H: A& J; a$ u$ W if(temp_ab[lar1.num]<temp) {
' Y3 X d/ g5 X5 D: R r=i;
( [0 e4 b( _" V# k) L* j temp=temp_ab[lar1.num];
& b6 l$ T% Z0 m$ w$ a }
9 N! D$ j, }6 x& ^0 U; f }) g/ b' m3 A1 Q* u" a5 Y; h3 T
}
1 h6 ]. A$ X% ^( D7 V( W. U" | pbase[r][c]=1;
6 P" n; [" O9 R+ U0 Y" _& w" D if(temp_a[r]>temp_b[c]) {: t. f- A) p8 T% p) a/ ^
 base[r][c]=temp_b[c];
; t m; L( B; A+ L' Q. N5 \4 M temp_a[r]=temp_a[r]-temp_b[c];% \) `% a8 F1 e- L3 M& X
 temp_b[c]=0;
2 E n. y" L- p* \$ ^# n- [ for(i=1;i<=num_a;i++) temp_ab[c]=M;
, A6 b# b& P; z1 M9 V0 `2 p% Y }
: i( `! Z. L1 H# O: h( t! L2 _ else if(temp_a[r]<temp_b[c]) {
+ s B" w! e, X. K0 Q5 o base[r][c]=temp_a[r];
3 P9 f& r0 f# Q, w7 W temp_b[c]=temp_b[c]-temp_a[r];
9 ?5 Q7 ?. Q& m5 J, P; A temp_a[r]=0;. z( N- u, J( \3 R u. U; t6 A& K
 for(i=1;i<=num_b;i++) temp_ab[r]=M;6 o2 R# B8 F; m
}( Q; U h. |7 i: p' p
else if(temp_a[r]==temp_b[c]) {
1 ?" \5 x0 M8 i+ X base[r][c]=temp_a[r];, ]) u% L6 {4 g1 Q# C+ X0 q
 temp_a[r]=temp_b[c]=0;
9 Y# ]8 }4 a6 P5 s) |4 R: N for(i=1;i<=num_a;i++) temp_ab[c]=M;# a! x, e \; ]; s9 s7 t. [
 for(i=1;i<=num_b;i++) temp_ab[r]=M;4 y; N. u8 a1 x4 R# [
 k=0;) M1 \8 e: f" g6 V% f7 E( s
 for(i=1;i<=num_a;i++) if(temp_a!=0) k=1;$ l8 S( t( k- i
 for(i=1;i<=num_b;i++) if(temp_b!=0) k=1;
& a0 k2 p, n5 Z+ E if(k!=0) {
- p) x' j& _5 J# b! @3 @ k=0;
3 r2 R) b) C' X; y for(i=1;i<=num_a;i++) if(pbase[c]!=1) {k=1;break;}
$ ]! u; f8 C. R' m5 v for(j=1;j<=num_b;j++) if(pbase[r][j]!=1) {k=2;break;}# @/ Y1 E) E" @7 \
if(k==1) pbase[c]=1;5 p4 o8 d! q. ~6 [' P% w
else if(k==2) pbase[r][j]=1;* I' c9 s2 {8 l- ^3 ]
 }1 t8 G O0 e0 K3 D7 c% ^0 W
}
3 V- h& }" L @3 {; }9 ] k=0;7 c) h, ?, ~* u, }( @: S. q
for(i=1;i<=num_a;i++) if(temp_a!=0) k=1;0 x' `3 O# C. z8 q5 ?# e/ y
for(i=1;i<=num_b;i++) if(temp_b!=0) k=1;
0 c( e, o1 i! u4 P! O y if(k==0) return;
2 a$ R, U I0 N/ z findinit();4 C8 w5 H4 \( L4 ~* k
}5 M; j( _, ]' i
<>void computeuv() {; c: P' Q, a- t+ J! l0 b
int i,j,k;+ I1 ~/ `# p! @; N( h
for(i=1;i<=num_a;i++)
! f. ~& }1 m E+ w for(j=1;j<=num_b;j++) N# T2 {. A* e/ L9 y
if(pbase[j]==1) {
4 }0 h0 z; U9 ]2 u; O$ g if(pu==1) {v[j]=ab[j]-u; pv[j]=1;}
+ Y# ]9 A. N1 E, L/ @/ U" D0 T6 ~2 W( t if(pv[j]==1) {u=ab[j]-v[j]; pu=1;}
: j, d) a% `& W4 d, v }$ E# p# ^# b: ^: I( A) G( j
k=0;1 M5 o. I* ^+ d2 q2 C/ W
for(i=1;i<=num_a;i++) if(pu==0) k=1;
$ Y5 [) H, B, u5 [1 v; y* c for(i=1;i<=num_b;i++) if(pv==0) k=1;9 ~' i9 I+ x% Q( ~( t! S
if(k==1) computeuv();2 f, M) o6 C0 j4 U. R) e) V6 l
}# p# m0 V5 B# \. ^4 q4 ~
<>int check() {- U3 }: p$ l5 C$ H8 g
int i,j,k,l;
) N+ g: }0 @- _- C- }3 I4 f' O! N* P k=l=0;
8 N. I- w# [+ P! T/ \ for(i=1;i<=num_a;i++)5 q) }& i. L6 A* P" F& N
 for(j=1;j<=num_b;j++) + y# q+ s% X1 S: \( {9 H5 M& Z, [
if(pbase[j]==0) {
% j- n, d; I! ]9 i6 v base[j]=ab[j]-u-v[j];
/ I# f! ~, V0 [2 a8 o if(base[j]<0) k=1;
. P+ R1 l, k b$ S else if(base[j]==0) l=1;
0 [' u, t, @0 q7 ~6 `, y/ D }+ Q# k5 k% S8 c" T' K; J4 U K
/* for(i=1;i<=num_a;i++){
9 ^7 f9 n+ V( q for(j=1;j<=num_b;j++) printf("base %lg\t",base[j]);% [( M4 l+ n- } Y
 putchar('\n');}. \. k$ I- a2 R( Y6 e0 J* A0 |. i
for(i=1;i<=num_a;i++){
. I5 q* u/ e( ^+ }% i4 T) K for(j=1;j<=num_b;j++) printf("pbase %d\t",pbase[j]);/ x- |3 _' r q. J/ N$ Z4 C
 putchar('\n');}' K' e7 j$ K7 W9 k
*/1 M/ @9 Y8 t1 i, d7 t$ }$ e; l6 D
if(k==0&&l==0) {status=1; return 1;}" ^/ B9 v9 \5 [! }8 _+ K
else if(k==0&&l!=0) {status=-1; return 1;}- B; u9 n2 X5 V0 r: Q. Q1 r) [
else return 0;
* @8 |6 A( h7 n6 u# S. B. a0 Z}% d; D2 \" ~0 F7 F. _) x0 u
<>int circle(enum direction dir,struct element cir[],int *t) {
. m1 ?- `/ V( O; Q4 | int i,j,k;
. R# a0 U; N0 z# I; _3 T( k0 `0 B /*
3 _" O7 Q# U- ^. }- _5 l putchar('\n');0 a8 m( N5 k& _' b( v4 Z# U% |
for(i=1;i<=*t;i++) printf("%d: r%d c%d\t",i, cir.r,cir.c);
8 L. k) u/ S {1 S% E putchar('\n');/ q# q9 N- X; r) Y8 h e' t, Y
*/$ W I9 Y3 N D6 F
if((*t)!=1&&cir[(*t)].r==cir[1].r&&cir[*t].c==cir[1].c) {) t2 G& l' Q+ w. a5 p$ g$ _7 S
 t--; % l0 b6 h( l( O Q1 ]+ I' |
 return 1;
7 d# t* F& o7 ]) T4 ^1 z. w/ v }
$ t. Z) m, a/ `( p8 a if(dir!=down) {
, T- x" |- ~; R. e( o$ f k=0;% D9 `) y: z$ B5 o, |
 for(i=cir[*t].r-1;i>=1;i--)
) e1 `. ?* m) V e) {2 O" X" u if(pbase[cir[*t].c]==1||(i==cir[1].r&&cir[*t].c==cir[1].c)) {k=1; break;}- _8 A2 m$ E9 V3 N. p w' B; n
 for(j=2;j<=*t;j++) if(i==cir[j].r&&cir[*t].c==cir[j].c) k=0;
4 m% m E: Y1 F# P6 { if(k==1) {& _, c( O$ ]* f& e. h: O
if(dir==up) cir[*t].value=0;
; k. N8 V: t8 S | else cir[*t].value=1;# ~4 N) b2 C o+ }; }7 N
(*t)++;
0 y* B1 |. F, M) B1 X* @ cir[*t].r=i;
/ o& D# d4 Z; ^( Q U+ `# g/ g cir[*t].c=cir[(*t)-1].c;
: b) K: N2 h! T* d if(circle(up,cir,t)) return 1;
. g) s) o- R/ T% o* R }8 b0 f% F. n8 m' b y7 c+ i
}' S/ _7 A* r# l
if(dir!=up) {
) x! D. z; k' u' Y7 l: l3 P. i" ~ k=0;
, C# @4 F( A% c- o for(i=cir[*t].r+1;i<=num_a;i++)
' P1 }9 j9 s ]9 s if(pbase[cir[*t].c]==1||(i==cir[1].r&&cir[*t].c==cir[1].c)) {k=1; break;}. ?+ s2 l4 w; I+ C
 for(j=2;j<=*t;j++) if(i==cir[j].r&&cir[*t].c==cir[j].c) k=0;9 g% Y; h% G- D% N/ r1 Y: n( D& |/ m
 if(k==1) {
5 J4 j5 B, L+ h if(dir==down) cir[*t].value=0;5 D. ~3 h1 q6 s& F
else cir[*t].value=1;
1 Q# T* T3 u2 }5 A4 b/ n5 {% j. M (*t)++;1 S5 W: S: h* `* N! e0 {5 H% J) k
cir[*t].r=i;
/ w* ]0 e5 Q4 O* i5 j( l. I cir[*t].c=cir[(*t)-1].c;
( |1 z/ E/ X* I- y( _, \ if(circle(down,cir,t)) return 1;
' p. Y3 [8 l) ?2 |! C0 ]% h }
3 `" H+ Z7 ~% u( u# j% N }
' p3 n3 P5 j4 E; n! l4 u if(dir!=right) {$ O- z6 W& X( P( R9 \# D2 L2 }* v6 K
 k=0;+ j- _ h1 E) y6 C* J
 for(i=cir[*t].c-1;i>=1;i--) 5 ~9 K2 y e4 u3 A( x, b& }
if(pbase[cir[*t].r]==1||(cir[*t].r==cir[1].r&&i==cir[1].c)) {k=1; break;}
7 Q! u( D/ `+ s1 E5 e# F" g" ~8 U% V& E for(j=2;j<=*t;j++) if(cir[*t].r==cir[j].r&&i==cir[j].c) k=0;
0 L- r" b. J0 e- t: w8 ] if(k==1) {: V6 _2 Y% ]9 h8 s; s
if(dir==left) cir[*t].value=0;
1 d) r) m$ g1 Z* f0 J else cir[*t].value=1;- w5 x4 L# Q7 i+ @; }( U" ~
(*t)++;+ D, s% @6 z5 G" J% t; W* F# ~$ g
cir[*t].r=cir[(*t)-1].r;& M) I/ R; G4 y4 l
cir[*t].c=i;
# y0 S b3 q( B& V3 P9 g0 K if(circle(left,cir,t)) return 1; g) L7 @) U! ~! y9 ]
 }
# B7 k m' @) X }
0 T* @% T! T/ p: `1 f# s if(dir!=left) {
: |% W1 Z1 @# n) u, }1 G k=0;
) F' x. Q/ h! z for(i=cir[*t].c+1;i<=num_b;i++) 7 r* k" k# B3 w3 s {2 F
if(pbase[cir[*t].r]==1||(cir[*t].r==cir[1].r&&i==cir[1].c)) {k=1; break;}- U9 P9 J( X8 P8 [" R2 c
 for(j=2;j<=*t;j++) if(cir[*t].r==cir[j].r&&i==cir[j].c) k=0;
+ H! Y9 V: D; ]# j% G; X if(k==1) {
3 p t: B6 h: ` m5 U5 q if(dir==right) cir[*t].value=0;7 p& b7 ]7 a9 O! c! n3 E6 B
else cir[*t].value=1;
4 r5 z* q% f0 X% j' K (*t)++;
4 b" y! K) V7 w d; s7 }0 w cir[*t].r=cir[(*t)-1].r;4 x* j- w% i7 Q
cir[*t].c=i;
9 \1 ~$ H( x3 a. \9 Y$ W if(circle(right,cir,t)) return 1;* y- ]& W J+ f q. a6 e
 }
! _. M% n8 a, h2 W$ o: b% r) ? }
: ^* u6 D# {( ~ (*t)--;/ y& D5 W& h' A# i. E& x
return 0;
$ {! h9 \4 Q# r- Y( H8 b}
- s: }& S" L. W0 I<>void improve() {
% {0 Q5 T" V, x$ M- B int i,j,k,t;; q. v: b" l- }. L. `; ^ r9 W
struct element base_in,base_out,cir[2*MAX+1];
$ ^5 e& V) @9 e: T! n# c<> for(i=1;i<=num_a;i++) pu=0;
- W3 r' s8 L6 @/ n# y for(i=1;i<=num_b;i++) pv=0;
; C3 f$ o% p2 f$ R+ n u[1]=0; pu[1]=1;1 p, }- }: Q, D- r6 ^$ z; Q
computeuv();! Z, d6 B( A2 {3 V" ?
if(check()) return;* ], T0 `/ e' t7 F! t
for(i=1;i<=num_a;i++)+ w0 y# t2 ?' a. n! o% l; t3 [
 for(j=1;j<=num_b;j++) - W/ v# ^/ L' j
if(pbase[j]==0) break;
% A* \6 |3 J( W2 t# M- G base_in.r=i;
& ~5 i# o$ A9 }1 Y+ w base_in.c=j;) d! w+ l" }) v9 H$ ~
base_in.value=base[j];
" j% v' Z/ h- `* R m9 E4 R& q<> for(i=1;i<=num_a;i++)
* L3 A$ L: N( T, K2 B# S for(j=1;j<=num_b;j++) . q2 J8 T4 d# K6 `
if(pbase[j]==0&&base[j]<base_in.value) {3 C; s+ |; a T9 \& d$ Z
base_in.r=i;
3 U" u& I |# Z1 l/ V3 g U base_in.c=j;- ~# o5 x9 v$ U
base_in.value=base[j];
9 R0 t( } J9 e( w6 e2 `6 [+ g3 @ }
0 v; C( s. Z% l9 _' }2 s4 b<> t=1;8 ?6 `) G5 W# G u7 D( {! {1 Z
cir[t].r=base_in.r;# u( E Q- ~9 b, K- _0 T
cir[t].c=base_in.c;
) P; H0 `2 g1 \ cir[t].value=1;
! c8 T- O& o' I8 ^0 B if(!circle(mid,cir,&t)) {: @3 \3 A) N& e8 N& i9 c: A- u4 W
 printf("程序出错！按回车结束");: V0 u, Y5 y" Q! |
 getchar();6 ~4 ?- q6 j$ y' i8 G- J
 exit(0);$ O m {; ~6 q; Q
}
9 i8 S) P1 |. n" f t--;. d- p& c" X7 J* [/ U* K* v
// for(i=1;i<=t;i++) printf("%d:r%d c%d v%lg\t",i,cir.r,cir.c,cir.value);
// putchar('\n');
' }. d2 M% U3 j- ?<> for(i=2;i<=t;i++) if(cir.value==1) break;
/ ~7 n8 L. v1 ]. e' Z base_out=cir;
( k% q# k" A0 O1 N. o; d3 r6 f: Z base_out.value=base[cir.r][cir.c];
k=1;8 f) y& o& N" ]: Q
for(i=1;i<=t;i++)
: L j" \7 Q, e8 w g if(k%2==0&&cir.value==1&&base[cir.r][cir.c]<base_out.value) {, \9 Y8 z3 z! c+ G. S, ~% K) I0 Q/ d2 l
base_out=cir;; @/ M$ {8 P# B" Y: l) z! V
base_out.value=base[cir.r][cir.c];
3 ]' O6 i. }. a5 i n, L k++;. ^" K, A6 y% i9 `: f
 }- t* s4 E7 P8 c S2 T: Q
 else if(cir.value==1) k++;
" W3 ]6 X# k% K3 I6 C8 P- d base[cir[1].r][cir[1].c]=0;
 x# E; i7 @6 n1 I2 @2 |" n k=1;$ Z( A3 P# b: |6 o; X
for(i=1;i<=t;i++) {
! y/ f9 k& b* n4 e! {! t& K if(k%2==1&&cir.value==1) {
 Z. W: b8 X. Z) o$ V( J( L base[cir.r][cir.c]+=base_out.value;
( W! q8 d) |" S8 i" K6 ~$ w1 n k++;
( t1 o6 j3 z8 D8 ?4 h }8 n; `) L' e1 I
 else if(k%2==0&&cir.value==1) {
5 B$ X) h3 w- b+ |- c base[cir.r][cir.c]-=base_out.value; P: P7 F' }) C5 h+ ^
k++;
9 ^7 V! _' N/ c# x9 c9 g. H+ z6 O }' @ g$ c* |! {& k& y
}
! K' L4 o2 b- u; N) p! |2 W+ \0 w) j1 w pbase[base_out.r][base_out.c]=0;
9 \0 V( l0 y( x pbase[base_in.r][base_in.c]=1;
. ]& x# x! O7 _/ r' P/ a! G& w6 T<> improve();$ x& I3 ^3 [" s
}* p5 W5 u0 `; g! a; _
<>void output() {
+ n" a7 S* A9 H8 I; |9 w int i,j;
$ e9 ]2 R% E% s3 q" V: u6 l6 h' \ double sum=0;9 ~) h! b6 ]) u1 @' M6 n, Z
printf("\n运量为：\n");" B5 d, ~" m) t
for(i=1;i<=num_a;i++) {1 Q# O: g( c9 Q* Q( M' v
 putchar(' ');/ Q; ]2 @- v' w( C3 @% E6 N0 ~ p
 for(j=1;j<=num_b;j++)3 Y0 {- b0 T8 \" c" D# c
if(pbase[j]==1) {# P0 E2 c% h( f& K9 Y1 m! ^
printf("A%d->B%d:%lg\t",i,j,base[j]);: `7 ~0 `" @% |# a3 k# e
sum+=base[j]*ab[j];
1 L: c4 I/ J x ]6 h3 d% _ }
( n9 m& r2 q' w* t6 D" S else printf("A%d->B%d:0\t",i,j);
8 G4 a" _2 l# H% C putchar('\n');
6 l6 E _3 S$ j q4 b }
4 A. S% E$ W3 ^' T printf("\n最低总运费为：%lg\n",sum);, z; ~1 i) u( P
}
4 _" ?/ f7 b3 x5 A