把每对钥匙看做一个变量,那两个钥匙看做他的两个状态

每一个开门的要求就是一个条件(xi or xj)

很显然有了2sat的基本要素

2sat是一个判定性问题,而这题求最多能过几个门;

不难想到二分答案,转化为判定性问题可轻松解决

 type node=record
       next,point:longint;
     end;
var edge:array[..] of node;
    v,f:array[..] of boolean;
    other,d1,d2,be,dfn,low,p,st:array[..] of longint;
    mid,l,r,n,m,x,y,ans,len,sum,t,h,i:longint; function min(a,b:longint):longint;
  begin
    if a>b then exit(b) else exit(a);
  end; procedure add(x,y:longint);
  begin
    inc(len);
    edge[len].point:=y;
    edge[len].next:=p[x];
    p[x]:=len;
  end; procedure tarjan(x:longint);
  var i,y:longint;
  begin
    inc(h);
    inc(t);
    st[t]:=x;
    dfn[x]:=h;
    low[x]:=h;
    f[x]:=true;
    v[x]:=true;
    i:=p[x];
    while i<>- do
    begin
      y:=edge[i].point;
      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]);
      i:=edge[i].next;
    end;
    if low[x]=dfn[x] then
    begin
      inc(sum);
      while st[t+]<>x do
      begin
        y:=st[t];
        f[y]:=false;
        be[y]:=sum;
        dec(t);
      end;
    end;
  end; function check(k:longint):boolean;
  var i,x,y:longint;
  begin
    len:=;
    fillchar(p,sizeof(p),);
    fillchar(v,sizeof(v),false);
    fillchar(f,sizeof(f),false);
    fillchar(st,sizeof(st),);
    fillchar(be,sizeof(be),);
    sum:=;
    for i:= to k do
    begin
      x:=d1[i];
      y:=d2[i];
      add(other[x],y);
      add(other[y],x);
    end;
    for i:= to *n- do
      if not v[i] then
      begin
        t:=;
        h:=;
        tarjan(i);
      end;

    for i:= to *n- do
      if be[other[i]]=be[i] then exit(false);
    exit(true);
  end; begin
  readln(n,m);
  while (n<>) and (m<>) do
  begin
    len:=;
    fillchar(p,sizeof(p),);
    for i:= to n do
    begin
      readln(x,y);
      other[x]:=y;
      other[y]:=x;
    end;
    for i:= to m do
      readln(d1[i],d2[i]);
    ans:=;
    l:=;
    r:=m;
    while l<=r do
    begin
      mid:=(l+r) shr ;
      if check(mid) then
      begin
        ans:=mid;
        l:=mid+;
      end
      else r:=mid-;
    end;
    writeln(ans);
    readln(n,m);
  end;
end.
05-08 08:11