bzoj1797

时间:2023-03-09 17:33:22
bzoj1797

其实我觉得这种题目风格很像今天省选第三轮D1T1

都是在一个算法模型上去探索规律;

首先我们要做一遍最大流毫无疑问

第一问看起来很好想,只要是满流边就可以了?

错,反例不难找到

如:1--->2 flow 4

2--->3 flow 4

3--->1 flow 4

1--->4 flow 4

很有可能我们在找增广路的时候,走了多余的回路(1-2-3-1),导致前3条边也是满流边,但不会出现在最小割方案中

所以我们考虑用tarjan对残留网络缩点;

对于第一问,要求是满流边且起点终点在不同集合

第二问,显然在满足第一问的前提下,起点终点分属源点汇点集合

 const inf=;
type node=record
       from,point,next,flow:longint;
     end; var edge:array[..] of node;
    ans1,ans2:array[..] of longint;
    p,cur,pre,numh,h,low,dfn,be,st:array[..] of longint;
    tot,d,r,x,y,z,i,j,n,m,s,t,len:longint;
    v,f:array[..] of boolean; function min(a,b:longint):longint;
  begin
    if a>b then exit(b) else exit(a);
  end; procedure add(x,y,f:longint);
  begin
    inc(len);
    edge[len].point:=y;
    edge[len].from:=x;
    edge[len].flow:=f;
    edge[len].next:=p[x];
    p[x]:=len;
  end; procedure sap;
  var u,i,j,tmp,neck,q:longint;
  begin
    u:=s;
    numh[]:=n;
    while h[s]<n do
    begin
      if u=t then
      begin
        i:=s;
        neck:=inf;
        while i<>t do
        begin
          j:=cur[i];
          if neck>edge[j].flow then
          begin
            neck:=edge[j].flow;
            q:=i;
          end;
          i:=edge[j].point;
        end;
        i:=s;
        while i<>t do
        begin
          j:=cur[i];
          dec(edge[j].flow,neck);
          inc(edge[j xor ].flow,neck);
          i:=edge[j].point;
        end;
        u:=q;
      end;
      q:=-;
      i:=p[u];
      while i<>- do
      begin
        j:=edge[i].point;
        if (edge[i].flow>) and (h[u]=h[j]+) then
        begin
          q:=i;
          break;
        end;
        i:=edge[i].next;
      end;
      if q<>- then
      begin
        cur[u]:=q;
        pre[j]:=u;
        u:=j;
      end
      else begin
        dec(numh[h[u]]);
        if numh[h[u]]= then exit;
        tmp:=n;
        i:=p[u];
        while i<>- do
        begin
          j:=edge[i].point;
          if edge[i].flow> then tmp:=min(tmp,h[j]);
          i:=edge[i].next;
        end;
        h[u]:=tmp+;
        inc(numh[h[u]]);
        if u<>s then u:=pre[u];
      end;
    end;
  end; procedure tarjan(x:longint);
  var i,y:longint;
  begin
    v[x]:=true;
    f[x]:=true;
    inc(r);
    inc(d);
    st[r]:=x;
    dfn[x]:=d;
    low[x]:=d;
    i:=p[x];
    while i<>- do
    begin
      y:=edge[i].point;
      if edge[i].flow> then
      begin
        if not v[y] then
        begin
          tarjan(y);
          low[x]:=min(low[x],low[y]);
        end
        else if f[y] then
          low[x]:=min(low[x],low[y]);
      end;
      i:=edge[i].next;
    end;
    if low[x]=dfn[x] then
    begin
      inc(tot);
      while st[r+]<>x do
      begin
        y:=st[r];
        f[y]:=false;
        be[y]:=tot;
        dec(r);
      end;
    end;
  end; begin
  readln(n,m,s,t);
  len:=-;
  fillchar(p,sizeof(p),);
  for i:= to m do
  begin
    readln(x,y,z);
    add(x,y,z);
    add(y,x,);
  end;
  sap;
  for i:= to n do
    if not v[i] then
    begin
      r:=;
      d:=;
      tarjan(i);
    end;
  i:=;
  while i<=len do
  begin
    if (edge[i].flow=) then
    begin
      x:=edge[i].from;
      y:=edge[i].point;
      if be[x]<>be[y] then
      begin
        ans1[i div +]:=;
        if (be[x]=be[s]) and (be[y]=be[t]) or (be[x]=be[t]) and (be[y]=be[s]) then
          ans2[i div +]:=;
      end;
    end;
    i:=i+;
  end;
  for i:= to m do
    writeln(ans1[i],' ',ans2[i]);
end.