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