| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
小菜请高手指点~这个是我的代码:TLE到死~
program POJ_2516;
type
matrix=array[1..50,1..50] of longint;
var
lx,ly,link:array[1..150] of longint;
map:array[1..150,1..150] of longint;
have,want:array[1..50,1..50] of longint;
a:array[1..50] of matrix;
va,vb:array[1..150] of boolean;
nx,ny,i,j,k,t,ans,m,n,sum1,sum2,p,q,temp,l1,l2:longint;
flag:boolean;
function find(x:integer):boolean;
var
i:longint;
begin
va[x]:=true;
for i:=1 to ny do
if not vb[i] and (lx[x]+ly[i]=map[x,i]) then
begin
vb[i]:=true;
if (link[i]=-1) or find(link[i]) then
begin
link[i]:=x;
exit(true);
end;
end;
exit(false);
end;
procedure calc;
var
i,j,t,min:longint;
begin
for i:=1 to nx do
begin
lx[i]:=-maxlongint;
for j:=1 to ny do
if lx[i]<map[i,j] then
lx[i]:=map[i,j];
end;
for i:=1 to ny do
link[i]:=-1;
for i:=1 to nx do
while true do
begin
fillchar(va,sizeof(va),0);
fillchar(vb,sizeof(vb),0);
if find(i) then break;
min:=maxlongint;
for j:=1 to nx do
if va[j] then
for t:=1 to ny do
if not vb[t] and (min>lx[j]+ly[t]-map[j,t]) then
min:=lx[j]+ly[t]-map[j,t];
for j:=1 to nx do if va[j] then dec(lx[j]);
for j:=1 to ny do if vb[j] then dec(ly[j]);
end;
end;
begin
assign(input,'a.in');
assign(output,'a.out');
reset(input); rewrite(output);
while true do
begin
read(n,m,k);
ans:=0;
if (m+n+k=0) then break;
for i:=1 to n do
for j:=1 to k do
read(want[i,j]);
for i:=1 to m do
for j:=1 to k do
read(have[i,j]);
for t:=1 to k do
for i:=1 to n do
for j:=1 to m do
read(a[t,i,j]);
flag:=false;
for t:=1 to k do
begin
sum1:=0; sum2:=0;
for i:=1 to n do
inc(sum1,want[i,t]);
for i:=1 to m do
inc(sum2,have[i,t]);
if sum1>sum2 then
begin flag:=true; break; end;
end;
if flag then begin writeln(-1); continue; end;
for t:=1 to k do
begin
nx:=0;
l1:=0; l2:=0;
fillchar(map,sizeof(map),0);
for i:=1 to n do
begin
ny:=0;
l1:=want[i,t];
flag:=false;
for j:=1 to m do
begin
l2:=have[j,t];
for p:=1 to l1 do
for q:=1 to l2 do
begin
flag:=true;
map[nx+p,ny+q]:=-a[t,i,j];
end;
if l2>0 then ny:=ny+l2;
end;
if flag then nx:=nx+l1;
end;
calc;
temp:=0;
for i:=1 to ny do
inc(temp,map[link[i],i]);
ans:=ans-temp;
end;
writeln(ans);
end;
close(input); close(output);
end.
请高手指点~~
P.S. 第一个点就是错的,因为故意打一个错解还是TLE,但在自己机器上是秒杀~
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator