telecow.pas

Magio牛的usaco源代码

{
ID:maigoak1
PROG:telecow
}

program telecow;
const
  maxn=100;
  maxm=600;
var
  fin,fout:text;
  adj:array[1..maxn,1..maxn]of boolean;
  tr,tc:array[1..maxn]of boolean;
  n,c1,c2,x,y,newflow,oldflow,j:byte;
  m,i:integer;
function maxflow:byte;
  var
    inpath:array[1..maxn]of boolean;
    q,pre:array[1..maxn]of byte;
    front,rear:byte;
  function try:boolean;
    var
      v:array[1..maxn]of boolean;
      i:byte;
    begin
      try:=true;
      v:=inpath;
      front:=0;rear:=1;q[1]:=c1;
      repeat
        inc(front);
        for i:=1 to n do
          if not v[i] and adj[q[front],i] then begin
            v[i]:=true;
            inc(rear);q[rear]:=i;pre[rear]:=front;
            if i=c2 then exit;
          end;
      until front=rear;
      try:=false;
    end;
  begin
    maxflow:=0;
    fillchar(inpath,sizeof(inpath),0);
    inpath[c1]:=true;
    while try do begin
      inc(maxflow);
      repeat
        rear:=pre[rear];
        if rear=1 then break;
        inpath[q[rear]]:=true;
      until false;
    end;
  end;
begin
  assign(fin,'telecow.in');
  reset(fin);
  readln(fin,n,m,c1,c2);
  for i:=1 to m do begin
    readln(fin,x,y);
    adj[x,y]:=true;adj[y,x]:=true;
  end;
  close(fin);

  assign(fout,'telecow.out');
  rewrite(fout);
  oldflow:=maxflow;
  writeln(fout,oldflow);
  for i:=1 to n do begin
    if (i=c1) or (i=c2) then continue;
    for j:=1 to n do begin
      tr[j]:=adj[i,j];tc[j]:=adj[j,i];
      adj[i,j]:=false;adj[j,i]:=false;
    end;
    newflow:=maxflow;
    if newflow<oldflow then begin
      write(fout,i);
      if newflow=0 then begin
        writeln(fout);
        close(fout);
        halt;
      end
      else begin
        write(fout,' ');
        oldflow:=newflow;
      end;
    end
    else
      for j:=1 to n do begin
        adj[i,j]:=tr[j];adj[j,i]:=tc[j];
      end;
  end;
end.