poj2723

把每对钥匙看做一个变量，那两个钥匙看做他的两个状态
每一个开门的要求就是一个条件(xi or xj)
很显然有了2sat的基本要素
2sat是一个判定性问题，而这题求最多能过几个门；
不难想到二分答案，转化为判定性问题可轻松解决
  1 type node=record
  2        next,point:longint;
  3      end;
  4 var edge:array[0..200010] of node;
  5     v,f:array[0..2100] of boolean;
  6     other,d1,d2,be,dfn,low,p,st:array[0..2100] of longint;
  7     mid,l,r,n,m,x,y,ans,len,sum,t,h,i:longint;
  8 
  9 function min(a,b:longint):longint;
 10   begin
 11     if a>b then exit(b) else exit(a);
 12   end;
 13 
 14 procedure add(x,y:longint);
 15   begin
 16     inc(len);
 17     edge[len].point:=y;
 18     edge[len].next:=p[x];
 19     p[x]:=len;
 20   end;
 21 
 22 procedure tarjan(x:longint);
 23   var i,y:longint;
 24   begin
 25     inc(h);
 26     inc(t);
 27     st[t]:=x;
 28     dfn[x]:=h;
 29     low[x]:=h;
 30     f[x]:=true;
 31     v[x]:=true;
 32     i:=p[x];
 33     while i<>-1 do
 34     begin
 35       y:=edge[i].point;
 36       if not v[y] then
 37       begin
 38         tarjan(y);
 39         low[x]:=min(low[x],low[y]);
 40       end
 41       else if f[y] then low[x]:=min(low[x],low[y]);
 42       i:=edge[i].next;
 43     end;
 44     if low[x]=dfn[x] then
 45     begin
 46       inc(sum);
 47       while st[t+1]<>x do
 48       begin
 49         y:=st[t];
 50         f[y]:=false;
 51         be[y]:=sum;
 52         dec(t);
 53       end;
 54     end;
 55   end;
 56 
 57 function check(k:longint):boolean;
 58   var i,x,y:longint;
 59   begin
 60     len:=0;
 61     fillchar(p,sizeof(p),255);
 62     fillchar(v,sizeof(v),false);
 63     fillchar(f,sizeof(f),false);
 64     fillchar(st,sizeof(st),255);
 65     fillchar(be,sizeof(be),0);
 66     sum:=0;
 67     for i:=1 to k do
 68     begin
 69       x:=d1[i];
 70       y:=d2[i];
 71       add(other[x],y);
 72       add(other[y],x);
 73     end;
 74     for i:=0 to 2*n-1 do
 75       if not v[i] then
 76       begin
 77         t:=0;
 78         h:=0;
 79         tarjan(i);
 80       end;
 81 、
 82     for i:=0 to 2*n-1 do
 83       if be[other[i]]=be[i] then exit(false);
 84     exit(true);
 85   end;
 86 
 87 begin
 88   readln(n,m);
 89   while (n<>0) and (m<>0) do
 90   begin
 91     len:=0;
 92     fillchar(p,sizeof(p),255);
 93     for i:=1 to n do
 94     begin
 95       readln(x,y);
 96       other[x]:=y;
 97       other[y]:=x;
 98     end;
 99     for i:=1 to m do
100       readln(d1[i],d2[i]);
101     ans:=0;
102     l:=0;
103     r:=m;
104     while l<=r do
105     begin
106       mid:=(l+r) shr 1;
107       if check(mid) then
108       begin
109         ans:=mid;
110         l:=mid+1;
111       end
112       else r:=mid-1;
113     end;
114     writeln(ans);
115     readln(n,m);
116   end;
117 end.
View Code