LOJ2723 Get Luffy Out
题目大意: 给你 n 对钥匙, 每对钥匙只可以用其中的任意一个, 钥匙有编号, 且不重复. 有 m 个大门, 每个门上有两个锁, 每个锁对应一个编号的钥匙, 只要打开两个锁中的一个就可以打开门. 问用这 n 对钥匙最多可以打开多少大门 (门有顺序)?
----------------------------------------------
每一个大门要打开, 要么用 A 钥匙, 要么用 B 钥匙, 这是明现的 2-SAT 问题.
同一对钥匙, 用了 A 钥匙就一定不能用 B 钥匙.
对于最多可以打开多少门, 因为门有顺序, 所以要二分答案.
----------------------------------------------
- #include<cstdio>
- #include<iostream>
- #include<algorithm>
- #include<cstring>
- using namespace std;
- const int maxn=1050;
- const int maxm=2100;
- int n,m;
- int keys[maxn<<1],doors[maxm][2];
- struct edge
- {
- int u,v,nxt;
- }e[maxm<<1];
- int head[maxn<<1],JS;
- void addage(int u,int v)
- {
- e[++JS].u=u;e[JS].v=v;
- e[JS].nxt=head[u];head[u]=JS;
- }
- int low[maxm<<1],dfn[maxm<<1],cnt,st[maxm<<1],top,lt[maxm<<1],lts;
- void tarjan(int u)
- {
- low[u]=dfn[u]=++cnt;
- st[++top]=u;
- for(int i=head[u];i;i=e[i].nxt)
- {
- int v=e[i].v;
- if(!dfn[v])
- {
- tarjan(v);
- low[u]=min(low[u],low[v]);
- }
- else if(!lt[v]) low[u]=min(low[u],dfn[v]);
- }
- if(low[u]==dfn[u])
- {
- lt[u]=++lts;
- while(st[top]!=u)lt[st[top--]]=lts;
- --top;
- }
- }
- bool pd(int x)
- {
- memset(head,0,sizeof head);
- JS=0;
- for(int a,b,i=0;i<x;++i)
- {
- a=doors[i][0],b=doors[i][1];
- if(a==b)addage(keys[a]^1,keys[a]);
- else
- {
- addage(keys[a]^1,keys[b]);
- addage(keys[b]^1,keys[a]);
- }
- }
- memset(low,0,sizeof low);
- memset(dfn,0,sizeof dfn);
- cnt=0;
- memset(lt,0,sizeof lt);
- lts=0;
- top=0;
- for(int i=2;i<n*2+2;++i)
- if(!dfn[i])tarjan(i);
- for(int i=1;i<n+1;++i)
- if(lt[i<<1]==lt[(i<<1)^1])return 0;
- return 1;
- }
- int main()
- {
- while(scanf("%d%d",&n,&m),n+m)
- {
- for(int a,b,i=1;i<=n;++i)
- {
- scanf("%d%d",&a,&b);
- keys[a]=i<<1;
- keys[b]=(i<<1)^1;
- }
- for(int i=0;i<m;++i)
- scanf("%d%d",&doors[i][0],&doors[i][1]);
- int l=0,r=m,ans=0;
- while(l<=r)
- {
- int mid=(l+r)>>1;
- if(pd(mid))ans=mid,l=mid+1;
- else r=mid-1;
- }
- printf("%d\n",ans);
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3073182.html