milk6.pas

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

{
ID:maigoak1
PROG:milk6
}

program milk6;
const
  maxn=32;
  maxm=1000;
type
  arc=record
    v1,v2:byte;
    cost,flow:longint;
    cut:boolean;
  end;
var
  fin,fout:text;
  e:array[1..maxm]of arc;
  c:array[1..maxm]of boolean;
  n:byte;
  m,i:integer;
  oldflow,newflow:int64;
function min(a,b:int64):int64;
  begin
    if a<b then min:=a else min:=b;
  end;
function maxflow:int64;
  var
    l:array[1..maxn]of integer;
    d:int64;
    i,j:integer;
    more:boolean;
  begin
    for i:=1 to m do
      e[i].flow:=0;
    repeat
      fillchar(l,sizeof(l),0);
      l[1]:=maxint;
      repeat
        more:=false;
        for i:=1 to m do
          if not e[i].cut then
            if (l[e[i].v1]<>0) and (l[e[i].v2]=0) and (e[i].flow<e[i].cost) then begin
              more:=true;l[e[i].v2]:=i;if l[n]<>0 then break;
            end
            else if (l[e[i].v2]<>0) and (l[e[i].v1]=0) and (e[i].flow>0) then begin
              more:=true;l[e[i].v1]:=-i;if l[n]<>0 then break;
            end;
      until not more or (l[n]<>0);
      if l[n]<>0 then begin
        i:=n;d:=maxlongint;
        repeat
          j:=i;if l[i]>0 then i:=e[l[i]].v1 else i:=e[-l[i]].v2;
          if l[j]>0 then
            d:=min(d,e[l[j]].cost-e[l[j]].flow)
          else
            d:=min(d,e[-l[j]].flow);
        until i=1;
        i:=n;
        repeat
          j:=i;if l[i]>0 then i:=e[l[i]].v1 else i:=e[-l[i]].v2;
          if l[j]>0 then
            inc(e[l[j]].flow,d)
          else
            dec(e[-l[j]].flow,d);
        until i=1;
      end;
    until l[n]=0;
    d:=0;
    for i:=1 to m do
      if e[i].v1=1 then inc(d,e[i].flow);
    maxflow:=d;
  end;
begin
  assign(fin,'milk6.in');
  reset(fin);
  readln(fin,n,m);
  for i:=1 to m do begin
    readln(fin,e[i].v1,e[i].v2,e[i].cost);
    e[i].cost:=e[i].cost*(maxm+1)+1;
    e[i].flow:=0;e[i].cut:=false;
  end;
  close(fin);

  assign(fout,'milk6.out');
  rewrite(fout);
  oldflow:=maxflow;
  writeln(fout,oldflow div (maxm+1),' ',oldflow mod (maxm+1));
  for i:=1 to m do begin
    e[i].cut:=true;
    newflow:=maxflow;
    if oldflow-newflow=e[i].cost then
      oldflow:=newflow
    else
      e[i].cut:=false;
    if oldflow=0 then break;
  end;

  for i:=1 to m do
    if e[i].cut then writeln(fout,i);
  close(fout);
end.