TTTTTTTTTTTTTTTT POJ 2723 楼层里救朋友 2-SAT+二分
Time Limit: 2000MS | Memory Limit: 65536K | |
Total Submissions: 8211 | Accepted: 3162 |
Description
Behind the large door, there is a nesting prison, which consists of M floors. Each floor except the deepest one has a door leading to the next floor, and there are two locks in each of these doors. Ratish can pass through a door if he opens either of the two locks in it. There are 2N different types of locks in all. The same type of locks may appear in different doors, and a door may have two locks of the same type. There is only one key that can unlock one type of lock, so there are 2N keys for all the 2N types of locks. These 2N keys were divided into N pairs, and once one key in a pair is used, the other key will disappear and never show up again.
Later, Ratish found N pairs of keys under the rock and a piece of paper recording exactly what kinds of locks are in the M doors. But Ratish doesn't know which floor Luffy is held, so he has to open as many doors as possible. Can you help him to choose N keys to open the maximum number of doors?
Input
Output
Sample Input
3 6
0 3
1 2
4 5
0 1
0 2
4 1
4 2
3 5
2 2
0 0
Sample Output
4 题意:有m层楼,从一层到m层,要进入每层都要打开位于该层的两道门中的至少一道。门锁有2n种,每个门锁为2n种中的一种,可以重复。有2n把钥匙,分别对应2n种锁,但是钥匙两两一组,共n组,每组只能选一个来开门,被选中的可以多次使用,另一个一次都不能用。问最多能上多少层。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
typedef unsigned long long Ull;
#define MM(a,b) memset(a,b,sizeof(a));
const double eps = 1e-10;
const int inf =0x7f7f7f7f;
const double pi=acos(-1);
const int maxn=100+1000; int n,m,pre[2*maxn],lowlink[2*maxn],dfs_clock,sccno[2*maxn],scc_cnt;
int door[2*maxn][3],key[2*maxn]; vector<int> G[2*maxn];
stack<int> S; void readkey()
{
int u,v;
scanf("%d %d",&u,&v);
key[u]=v;
key[v]=u;
} void readdoor(int i)
{
int u,v;
scanf("%d %d",&u,&v);
door[i][0]=u;
door[i][1]=v;
} void tarjan(int u)
{
pre[u]=lowlink[u]=++dfs_clock;
S.push(u);
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
if(pre[v]==-1)
{
tarjan(v);
lowlink[u]=min(lowlink[u],lowlink[v]);
}
else if(!sccno[v])
lowlink[u]=min(lowlink[u],pre[v]);
} if(lowlink[u]==pre[u])
{
scc_cnt++;
while(1)
{
int x=S.top();S.pop();
sccno[x]=scc_cnt;
if(x==u) break;//找到了当前强连通的起始节点就退出,<br>//不然会破坏其他强连通分量
}
}
} void find_scc()
{
MM(pre,-1);
MM(sccno,0);
MM(lowlink,0);
scc_cnt=dfs_clock=0;
for(int i=0;i<2*n;i++)
if(pre[i]==-1)
tarjan(i);
} bool ok(int mid)
{
for(int i=0;i<2*n;i++)
{G[i].clear();} for(int i=1;i<=mid;i++)
{
int a=door[i][0],b=door[i][1];
G[key[a]].push_back(b);
G[key[b]].push_back(a);
}//建图,预先记录门与钥匙 find_scc();
for(int i=0;i<2*n;i++)
if(sccno[i]==sccno[key[i]])
return false;
return true;
} int main()
{
while(~scanf("%d %d",&n,&m)&&(n||m))
{
MM(key,0);MM(door,0);
for(int i=1;i<=n;i++)
readkey();
for(int i=1;i<=m;i++)
readdoor(i); int l=0,r=m+1;
while(r-l>1)
{
int mid=(l+r)>>1;
if(ok(mid)) l=mid;
else r=mid;
}
printf("%d\n",l);
}
return 0;
}
分析:经典题型,建图不再是以前的那种一个点对应两个(0,1)状态,而是一组数对应两个状态(只能取其中两个中的一个)
建图核心思路:对于确切的层数,对于一组数,设其中一个为x,则对应的另一个为f[x],如果一个门对应的数值为x,y两个,那么可以确定的是如果选f[x]的话,为了打开这门,必须选y,同理选f[y]的话,必须选x;
建图即可;再二分查找即可,tarjan求强连通复杂度(n+m)
易错点:
1,数组要开两倍,因为输入的n是组数;
最新文章
- (转)构建自己的AngularJS,第一部分:Scope和Digest
- SQL Server 2012故障转移的looksalive check和is alive check
- Arduino101学习笔记(八)&mdash;&mdash; 函数库
- Android API Guides 学习笔记---Application Fundamentals(一)
- 一个日期Js文件。 2013年10月12日 星期六 癸巳年九月初八
- 菜鸟学习 git
- Linux命令记录。
- Java读写Excel之POI超入门
- javascript走马灯的效果(文档标题文字滚动)
- vue安装babel依赖报错
- CentOS安装node.js-8.11.1+替换淘宝NPM镜像
- AITP
- 链表(list)使用注意
- [转]jvm调优-命令大全(jps jstat jmap jhat jstack jinfo)
- 构造方法、 This关键字 、static、封装
- Iterator源码解读
- Codeforces 918D - MADMAX
- 全面兼容的Iframe 与父页面交互操作
- Linux内存高,触发oom-killer问题解决
- markdown在list或者引用之后怎么去重新令其一段