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
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

Re:数据太弱,TLE的检查自己的算法吧

Posted by Hoblovski at 2014-04-08 14:13:02 on Problem 3189
In Reply To:数据太弱,TLE的检查自己的算法吧 Posted by:Hoblovski at 2014-04-08 14:12:49
program poj3189;

type tnode=record
        n,c,next:longint;
     end;

const maxn=1517;
      maxm=100017;
      maxint=longint($3f3f3f3f);

var g,d,dc,cur,arc,dlt,pre,cap:array[0..maxn] of longint;
    like:array[1..1017,1..27] of longint;
    mem:array[1..maxm] of tnode;
    n,m,memsize,st,trm,cow,bar:longint;

function min(i,j:longint):longint; begin
if i<j then exit(i) else exit(j);  end;

procedure insnbs(u,v,ic:longint);
begin
inc(memsize); with mem[memsize] do begin
        n:=v; c:=ic; next:=g[u];
end; g[u]:=memsize;
inc(memsize); with mem[memsize] do begin
        n:=u; c:=0; next:=g[v];
end; g[v]:=memsize;
end;

function isap:longint;
var u,w,t1:longint;
begin
fillchar(d,sizeof(d),0); fillchar(dc,sizeof(dc),0);
pre[st]:=st; dlt[st]:=maxint; dc[0]:=n;
u:=st; isap:=0; cur:=g;
while d[st]<n do begin
        while (cur[u]<>0)and((mem[cur[u]].c=0)or(d[u]<>d[mem[cur[u]].n]+1)) do
                cur[u]:=mem[cur[u]].next;
        if cur[u]=0 then begin
                dec(dc[d[u]]); if dc[d[u]]=0 then break;
                w:=n; t1:=g[u]; while t1<>0 do begin
                        if (mem[t1].c>0)and(d[mem[t1].n]<w) then w:=d[mem[t1].n];
                        t1:=mem[t1].next;
                end; d[u]:=w+1; inc(dc[d[u]]); cur[u]:=g[u]; u:=pre[u];
        end else begin
                pre[mem[cur[u]].n]:=u;
                arc[mem[cur[u]].n]:=cur[u];
                dlt[mem[cur[u]].n]:=min(dlt[u],mem[cur[u]].c);
                u:=mem[cur[u]].n; if u=trm then begin
                        w:=dlt[trm]; inc(isap,w);
                        while u<>st do begin
                                dec(mem[arc[u]].c,w);
                                inc(mem[arc[u] xor 1].c,w);
                                u:=pre[u];
                        end;
                end;
        end;
end;
end;

procedure makegraph(pol,por:longint);
var i,j:longint;
begin
fillchar(g,sizeof(g),0); memsize:=1;
for i:=1 to cow do insnbs(st,i,1);
for i:=1 to bar do insnbs(cow+i,trm,cap[i]);
for i:=1 to cow do
        for j:=pol to por do
                insnbs(i,cow+like[i,j],1);
end;

procedure init;
var i,j,k:longint;
begin
readln(cow,bar);
for i:=1 to cow do begin
        for j:=1 to bar do read(like[i,j]);
        readln;
end;
for i:=1 to bar do read(cap[i]); readln;
end;

function ans:longint;
var l,r,mid,i,j,k:longint;
    flag:boolean;
begin
l:=0; r:=bar; st:=cow+bar+1; trm:=st+1; n:=trm;
while l<>r do begin
        mid:=(l+r)>>1; flag:=false;
        for i:=1 to bar-mid+1 do begin
                makegraph(i,i+mid-1);
                if isap=cow then begin
                        flag:=true; break;
                end;
        end; if flag then r:=mid else l:=mid+1;
end; exit(l);
end;

begin
init;
writeln(ans);
end.

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