Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

小菜请高手指点~

Posted by xdwudi at 2009-03-24 15:42:47 on Problem 2516
这个是我的代码: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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator