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

## 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
for i:=1 to cow do begin
for j:=1 to bar do read(like[i,j]);
end;
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: