LOJ2723 Get Luffy Out

题目大意：给你n对钥匙，每对钥匙只可以用其中的任意一个，钥匙有编号，且不重复。有m个大门，每个门上有两个锁，每个锁对应一个编号的钥匙，只要打开两个锁中的一个就可以打开门。问用这n对钥匙最多可以打开多少大门（门有顺序）？

——————————————————————————————————————————————

每一个大门要打开，要么用A钥匙，要么用B钥匙，这是明现的2-SAT问题。

同一对钥匙，用了A钥匙就一定不能用B钥匙。

对于最多可以打开多少门，因为门有顺序，所以要二分答案。

——————————————————————————————————————————————

1 #include
2 #include
3 #include
4 #include
5 using namespace std;
6 const int maxn=1050;
7 const int maxm=2100;
8 int n,m;
9 int keys[maxn<<1],doors[maxm][2]; 10 struct edge 11 { 12 int u,v,nxt; 13 }e[maxm<<1]; 14 int head[maxn<<1],js; 15 void addage(int u,int v) 16 { 17 e[++js].u=u;e[js].v=v; 18 e[js].nxt=head[u];head[u]=js; 19 } 20 int low[maxm<<1],dfn[maxm<<1],cnt,st[maxm<<1],top,lt[maxm<<1],lts; 21 void tarjan(int u) 22 { 23 low[u]=dfn[u]=++cnt; 24 st[++top]=u; 25 for(int i=head[u];i;i=e[i].nxt) 26 { 27 int v=e[i].v; 28 if(!dfn[v]) 29 { 30 tarjan(v); 31 low[u]=min(low[u],low[v]); 32 } 33 else if(!lt[v]) low[u]=min(low[u],dfn[v]); 34 } 35 if(low[u]==dfn[u]) 36 { 37 lt[u]=++lts; 38 while(st[top]!=u)lt[st[top--]]=lts; 39 --top; 40 } 41 } 42 bool pd(int x) 43 { 44 memset(head,0,sizeof head); 45 js=0; 46 for(int a,b,i=0;i>1;
84 if(pd(mid))ans=mid,l=mid+1;
85 else r=mid-1;
86 }
87 printf("%d\n",ans);
88 }
89 return 0;
90 }