1.时限太紧,没有一个大牛0ms(你这个688ms的蒟蒻有什么资格说)
2.空间卡的丧心病狂 交4次,1次AC 1次TLE 2次MLE...
3.让我认识到了指针的替代品的用处,但是OI里面卡指针真是一个丧心病狂的行为.

题目不难,注意以下
1.无解 --> writeln(-1);
2.用指针->MLE,用带内存回收的指针->TLE

个人不喜欢用前向星,用的数组模拟指针,Memory减少1倍 Time减少1倍

顺便提问 
数组模拟指针到底在什么时候有很大提高
以前写平衡树时试过一次,没有任何提高,为什么这次就提高了这么多...

又长又烂的代码
program poj2391;

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

const maxint=longint($3f3f3f3f);

var g,cur,arc:array[1..407] of longint;
    dist:array[0..407,0..407] of int64;
    prev,dlt,d,dc,inf,outf:array[0..407] of longint;
    mem:array[0..700001] of tnode;        //模拟指针
    orign,n,m,st,trm,ans,maxflow,size:longint;
    ltime,l,r,answer:int64;
    flag:boolean;

function min(a,b:longint):longint; begin
if a<b then exit(a) else exit(b);  end;

procedure insarc(u,v,w:longint);
begin
inc(size);
with mem[size] do begin
        n:=v; c:=w;
        next:=g[u];
end;
g[u]:=size;
end;

procedure insnbs(u,v,w:longint);
begin
insarc(u,v,w);
insarc(v,u,0);
mem[g[u]].opp:=g[v];
mem[g[v]].opp:=g[u];
end;

procedure floyd;
var i,j,k:longint;
begin
for k:=1 to n do
        for i:=1 to n do if (i<>k)and(dist[i,k]<>maxint) then
                for j:=1 to n do if (j<>k)and(dist[j,k]<>maxint)and(dist[i,k]+dist[k,j]<dist[i,j]) then
                        dist[i,j]:=dist[i,k]+dist[k,j];
end;

procedure main_init;
var i,j,u,v,w:longint;
begin
readln(n,m); orign:=n;
st:=(n<<1)+1; trm:=(n<<1)+2;
for i:=1 to n do begin
        readln(u,v);
        inc(inf[i],u);
        inc(outf[i+n],v);
        inc(maxflow,u);
end;
fillchar(dist,sizeof(dist),$3f);
for i:=1 to n do begin
        dist[i,trm]:=0; dist[st,i]:=0;
        dist[i,i]:=0;
end;
for i:=1 to m do begin
        readln(u,v,w);
        if w<dist[u,v] then begin
                dist[u,v]:=w;
                dist[v,u]:=w;
        end;
end;
floyd;
end;

procedure init;
var i,j,k:longint;
begin
fillchar(d,sizeof(d),0);
size:=0;
n:=orign;
fillchar(g,sizeof(g),0);
for i:=1 to n do if inf[i]>0 then
        insnbs(st,i,inf[i]);
for i:=n+1 to n+n do if outf[i]>0 then
        insnbs(i,trm,outf[i]);
for i:=1 to n do
        for j:=1 to n do
                if dist[i,j]<=ltime then
                        insnbs(i,j+n,maxint);
end;

procedure isap;
var u,j:longint;
    tmp:longint;
begin
n:=(n<<1+2);
prev[st]:=st; dc[0]:=n;
dlt[st]:=maxint; u:=st;
ans:=0; cur:=g;
while d[st]<n do begin
        while (cur[u]<>0)
          and((d[u]<>d[mem[cur[u]].n]+1)or(mem[cur[u]].c=0)) do
                cur[u]:=mem[cur[u]].next;
        if cur[u]=0 then begin
                dec(dc[d[u]]);
                if dc[d[u]]=0 then break;
                tmp:=g[u]; j:=n;
                while tmp<>0 do begin
                        if (mem[tmp].c>0)and(d[mem[tmp].n]<j) then j:=d[mem[tmp].n];
                        tmp:=mem[tmp].next;
                end;
                d[u]:=j+1;
                inc(dc[d[u]]);
                cur[u]:=g[u];
                u:=prev[u];
        end else begin
                prev[mem[cur[u]].n]:=u;
                dlt[mem[cur[u]].n]:=min(dlt[u],mem[cur[u]].c);
                arc[mem[cur[u]].n]:=cur[u];
                u:=mem[cur[u]].n;
                if u=trm then begin
                        j:=dlt[u]; inc(ans,j);
                        while u<>st do begin
                                dec(mem[arc[u]].c,j);
                                inc(mem[mem[arc[u]].opp].c,j);
                                u:=prev[u];
                        end;
                end;
        end;
end;
end;

begin
main_init;

r:=(int64(1)<<40); l:=0; flag:=false;
while l<r do begin
        ltime:=(r+l)>>1;
        init;
        isap;
        if ans=maxflow then begin
                answer:=ltime;
                r:=ltime;
                flag:=true;
        end else l:=ltime+1;
end;

if flag then writeln(answer) else writeln(-1);
end.

• 附一组数据 (4818) Hoblovski 2013-11-20 14:14:12
  • Re:附一组数据 (16) HZOI_lhy111 2014-04-24 16:52:45