secret.pas

来自「Magio牛的usaco源代码」· PAS 代码 · 共 118 行

{
PROB:secret
LANG:PASCAL
}

program secret;
const
  maxn=200;
  maxp=40000;
type
  edge=record
    v1,v2:byte;
    len:longint;
    flow:shortint;
    next1,next2:word;
  end;
var
  e:array[1..maxp+1]of edge;
  start:array[1..maxn]of word;
  n,p,t,i,j,l,last,maxflow:longint;
procedure qsort(s,t:word);
  var
    p,i,j:word;
    te:edge;
  begin
    if s>=t then exit;
    p:=s+random(t-s+1);
    te:=e[p];e[p]:=e[s];
    i:=s;j:=t;
    repeat
      while (i<j) and (e[j].len>=te.len) do dec(j);
      if i=j then break;e[i]:=e[j];inc(i);
      while (i<j) and (e[i].len<=te.len) do inc(i);
      if i=j then break;e[j]:=e[i];dec(j);
    until i=j;
    e[i]:=te;
    qsort(s,i-1);
    qsort(i+1,t);
  end;
procedure aug;
  var
    q:array[1..maxn]of byte;
    ed:array[1..maxn]of longint;
    f,r,x,y:word;
  begin
    repeat
      fillchar(ed,sizeof(ed),0);
      f:=0;r:=1;q[1]:=1;ed[1]:=1;
      repeat
        inc(f);x:=start[q[f]];
        while x<=last do
          if e[x].v1=q[f] then begin
            y:=e[x].v2;
            if (ed[y]=0) and (e[x].flow<1) then begin
              inc(r);q[r]:=y;ed[y]:=x;if ed[n]>0 then break;
            end;
            x:=e[x].next1;
          end
          else if e[x].v2=q[f] then begin
            y:=e[x].v1;
            if (ed[y]=0) and (e[x].flow>-1) then begin
              inc(r);q[r]:=y;ed[y]:=-x;if ed[n]<0 then break;
            end;
            x:=e[x].next2;
          end;
      until (f=r) or (ed[n]<>0);
      if f=r then exit;
      x:=n;
      repeat
        if ed[x]>0 then begin
          inc(e[ed[x]].flow);
          x:=e[ed[x]].v1;
        end
        else begin
          dec(e[-ed[x]].flow);
          x:=e[-ed[x]].v2;
        end;
      until x=1;
      inc(maxflow);
    until maxflow=t;
  end;
begin
  assign(input,'secret.in');reset(input);
  assign(output,'secret.out');rewrite(output);

  read(n,p,t);
  for i:=1 to p do
    with e[i] do begin
      read(v1,v2,len);
      flow:=0;
    end;
  qsort(1,p);
  e[p+1].len:=maxlongint;

  fillchar(start,sizeof(start),255);
  for i:=p downto 1 do begin
    e[i].next1:=start[e[i].v1];start[e[i].v1]:=i;
    e[i].next2:=start[e[i].v2];start[e[i].v2]:=i;
  end;

  l:=1;maxflow:=0;
  repeat
    last:=(l+p) shr 1;
    aug;
    if maxflow<t then
      l:=last+1
    else begin
      p:=last;
      for i:=1 to p do
        e[i].flow:=0;
      maxflow:=0;
    end;
  until l=p;
  writeln(e[p].len);

  close(input);close(output);
end.