题意:

【UOJ179】线性规划(单纯形)-LMLPHP

思路:单纯形模板

【UOJ179】线性规划(单纯形)-LMLPHP

【UOJ179】线性规划(单纯形)-LMLPHP

 var a:array[..,..]of double;
idx,idy,q:array[..]of longint;
c:array[..]of double;
n,m,i,j,op,x,y:longint;
eps,mn:double; procedure swap(var x,y:longint);
var t:longint;
begin
t:=x; x:=y; y:=t;
end; procedure pivot(x,y:longint);
var i,j,tot:longint;
tmp:double;
begin
swap(idy[x],idx[y]);
tmp:=a[x,y]; a[x,y]:=/a[x,y];
for i:= to n do
if y<>i then a[x,i]:=a[x,i]/tmp;
tot:=;
for i:= to n do
if (i<>y)and((a[x,i]>eps)or(a[x,i]<-eps)) then
begin
inc(tot); q[tot]:=i;
end;
for i:= to m do
begin
if (x=i)or((a[i,y]<eps)and(a[i,y]>-eps)) then continue;
for j:= to tot do a[i,q[j]]:=a[i,q[j]]-a[x,q[j]]*a[i,y];
a[i,y]:=-a[i,y]/tmp;
end;
end; begin
//assign(input,'uoj179.in'); reset(input);
//assign(output,'uoj179.out'); rewrite(output);
readln(n,m,op);
randomize;
eps:=1e-8;
for i:= to n do read(a[,i]);
for i:= to m do
begin
for j:= to n do read(a[i,j]);
read(a[i,]);
end;
for i:= to n do idx[i]:=i;
for i:= to m do idy[i]:=i+n;
while true do
begin
x:=; y:=;
for i:= to m do
if (a[i,]<-eps)and((x=)or(random()=)) then x:=i;
if x= then break;
for i:= to n do
if (a[x,i]<-eps)and((y=)or(random()=)) then y:=i;
if y= then
begin
writeln('Infeasible');
// close(input);
//close(output);
exit;
end;
pivot(x,y);
end;
while true do
begin
x:=; y:=; mn:=1e15;
for i:= to n do
if a[,i]>eps then begin y:=i; break; end;
if y= then break;
for i:= to m do
if (a[i,y]>eps)and(a[i,]/a[i,y]<mn) then
begin
mn:=a[i,]/a[i,y]; x:=i;
end;
if x= then
begin
writeln('Unbounded');
// close(input);
// close(output);
exit;
end;
pivot(x,y);
end;
writeln(-a[,]::);
if op= then exit;
for i:= to m do
if idy[i]<=n then c[idy[i]]:=a[i,];
for i:= to n do
begin
write(c[i]::);
if i<n then write(' ');
end; //close(input);
//close(output);
end.
05-19 20:03