【UOJ179】线性规划（单纯形）

 1 var a:array[0..100,0..100]of double;
 2     idx,idy,q:array[0..100]of longint;
 3     c:array[0..100]of double;
 4     n,m,i,j,op,x,y:longint;
 5     eps,mn:double;
 6 
 7 procedure swap(var x,y:longint);
 8 var t:longint;
 9 begin
10  t:=x; x:=y; y:=t;
11 end;
12 
13 procedure pivot(x,y:longint);
14 var i,j,tot:longint;
15     tmp:double;
16 begin
17  swap(idy[x],idx[y]);
18  tmp:=a[x,y]; a[x,y]:=1/a[x,y];
19  for i:=0 to n do
20   if y<>i then a[x,i]:=a[x,i]/tmp;
21  tot:=0;
22  for i:=0 to n do
23   if (i<>y)and((a[x,i]>eps)or(a[x,i]<-eps)) then
24   begin
25    inc(tot); q[tot]:=i;
26   end;
27  for i:=0 to m do
28  begin
29   if (x=i)or((a[i,y]<eps)and(a[i,y]>-eps)) then continue;
30   for j:=1 to tot do a[i,q[j]]:=a[i,q[j]]-a[x,q[j]]*a[i,y];
31   a[i,y]:=-a[i,y]/tmp;
32  end;
33 end;
34 
35 begin
36  //assign(input,‘uoj179.in‘); reset(input);
37  //assign(output,‘uoj179.out‘); rewrite(output);
38  readln(n,m,op);
39  randomize;
40  eps:=1e-8;
41  for i:=1 to n do read(a[0,i]);
42  for i:=1 to m do
43  begin
44   for j:=1 to n do read(a[i,j]);
45   read(a[i,0]);
46  end;
47  for i:=1 to n do idx[i]:=i;
48  for i:=1 to m do idy[i]:=i+n;
49  while true do
50  begin
51   x:=0; y:=0;
52   for i:=1 to m do
53    if (a[i,0]<-eps)and((x=0)or(random(2)=1)) then x:=i;
54   if x=0 then break;
55   for i:=1 to n do
56    if (a[x,i]<-eps)and((y=0)or(random(2)=1)) then y:=i;
57   if y=0 then
58   begin
59    writeln(‘Infeasible‘);
60   // close(input);
61    //close(output);
62    exit;
63   end;
64   pivot(x,y);
65  end;
66  while true do
67  begin
68   x:=0; y:=0; mn:=1e15;
69   for i:=1 to n do
70    if a[0,i]>eps then begin y:=i; break; end;
71   if y=0 then break;
72   for i:=1 to m do
73    if (a[i,y]>eps)and(a[i,0]/a[i,y]<mn) then
74    begin
75     mn:=a[i,0]/a[i,y]; x:=i;
76    end;
77   if x=0 then
78   begin
79    writeln(‘Unbounded‘);
80  //  close(input);
81  //  close(output);
82    exit;
83   end;
84   pivot(x,y);
85  end;
86  writeln(-a[0,0]:0:8);
87  if op=0 then exit;
88  for i:=1 to m do
89   if idy[i]<=n then c[idy[i]]:=a[i,0];
90  for i:=1 to n do
91  begin
92   write(c[i]:0:8);
93   if i<n then write(‘ ‘);
94  end;
95 
96  //close(input);
97  //close(output);
98 end.