POJ2723-Get Luffy Out(2-SAT)

时间:2021-11-09 08:07:48

题意:有m扇门,每个门上有两把锁,打开任意一个锁都可以打开这扇门。门要按顺序一个一个打开。

现在有n对不同的钥匙,每对钥匙只能用其中一个,问最多能打开多少门。

题解:对钥匙建图,门是限制条件来建边。每加一扇门就多一个限制条件,直到2-sat不满足为止。当然二分会更快一些。有一个trick就是门上的两把锁相同的情况,也是就这个钥匙是必须用的,建边特殊考虑。

PS:我到底要错多少次才能长记性数组开足够大!!!以后WA了看数组!!TLE了看数组!!RE了看数组!!!

#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std; typedef long long ll; const int N = <<;
const int M = <<; struct Edge {
int from, to, next;
} edge[M];
int head[N];
int cntE;
void addedge(int u, int v) {
edge[cntE].from = u; edge[cntE].to = v; edge[cntE].next = head[u]; head[u] = cntE++;
} int dfn[N], low[N], idx;
int stk[N], top;
int in[N];
int kind[N], cnt; void tarjan(int u)
{
dfn[u] = low[u] = ++idx;
in[u] = true;
stk[++top] = u;
for (int i = head[u]; i != -; i = edge[i].next) {
int v = edge[i].to;
if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
else if (in[v]) low[u] = min(low[u], dfn[v]);
}
if (low[u] == dfn[u]) {
++cnt;
while () {
int v = stk[top--]; kind[v] = cnt; in[v] = false;
if (v == u) break;
}
}
} bool sat(int n) // 序号从0开始
{
for (int i = ; i < *n; ++i) if (!dfn[i]) tarjan(i);
for (int i = ; i < *n; i += ) {
if (kind[i] == kind[i^]) return false;
}
return true;
} void init() {
memset(dfn, , sizeof dfn);
memset(in, false, sizeof in);
idx = top = cnt = ;
}
int key[M];
int a[N], b[N];
int main()
{
int n, m;
int u, v;
while (~scanf("%d%d", &n, &m) && n) {
cntE = ; memset(head, -, sizeof head);
for (int i = ; i < n; ++i) {
scanf("%d%d", &u, &v);
key[u] = *i; key[v] = *i+;
} for (int i = ; i < m; ++i) {
scanf("%d%d", a+i, b+i);
}
for (int i = ; i < m; ++i) {
if (a[i] == b[i]) addedge(key[ a[i] ]^, key[ a[i] ]);
else {
addedge(key[ a[i] ]^, key[ b[i] ]);
addedge(key[ b[i] ]^, key[ a[i] ]);
}
init();
if (!sat(n)) {
printf("%d\n", i);
break;
}
if (i == m-) {
printf("%d\n", m);
}
}
} return ;
} /**
3 3
1 2 3 4 5 6
3 3 2 2 4 4 3 3
0 1 2 3 4 5
0 2 1 1 3 3 **/

POJ2723-Get Luffy Out(2-SAT)的更多相关文章

  1. 学习笔记(two sat)

    关于two sat算法 两篇很好的论文由对称性解2-SAT问题(伍昱), 赵爽 2-sat解法浅析(pdf). 一些题目的题解 poj 3207 poj 3678 poj 3683 poj 3648 ...

  2. POJ 3678 Katu Puzzle(2 - SAT) - from lanshui&lowbar;Yang

    Description Katu Puzzle is presented as a directed graph G(V, E) with each edge e(a, b) labeled by a ...

  3. Katu Puzzle POJ - 3678 (2 - sat)

    有N个变量X1X1~XNXN,每个变量的可能取值为0或1. 给定M个算式,每个算式形如 XaopXb=cXaopXb=c,其中 a,b 是变量编号,c 是数字0或1,op 是 and,or,xor 三 ...

  4. LA 3211 飞机调度(2—SAT)

    https://vjudge.net/problem/UVALive-3211 题意: 有n架飞机需要着陆,每架飞机都可以选择“早着陆”和“晚着陆”两种方式之一,且必须选择一种,第i架飞机的早着陆时间 ...

  5. spring定时任务详解(&commat;Scheduled注解)( 转 李秀才的博客 )

    在springMVC里使用spring的定时任务非常的简单,如下: (一)在xml里加入task的命名空间 xmlns:task="http://www.springframework.or ...

  6. MongoDB 聚合管道(Aggregation Pipeline)

    管道概念 POSIX多线程的使用方式中, 有一种很重要的方式-----流水线(亦称为"管道")方式,"数据元素"流串行地被一组线程按顺序执行.它的使用架构可参考 ...

  7. mysql触发器,答题记录表同步教学跟踪(用户列表)

    aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAABVQAAAOOCAIAAABgEw4AAAAgAElEQVR4nOy92VcT27r/zX+xLtflvt

  8. Linux版Matlab R2015b的bug——脚本运行的陷阱(未解决)

    0 系统+软件版本 系统:CentOS 6.7 x64, 内核 2.6.32-573.el6.x86_64软件:Matlab R2015b(包括威锋网和东北大学ipv6下载的资源,都测试过) 1 脚本 ...

  9. Quartz&period;net(调度框架) 使用Mysql作为存储

    最近公司的做的项目中涉及到配置任务地址然后按照配置去目标地址提取相关的数据,所以今天上午在Internet上查看有关定时任务(调度任务)的相关信息,筛选半天然后查找到Quartz.net. Quart ...

  10. mysql 函数编程大全(持续更新)

    insert ignore insert ignore表示,如果中已经存在相同的记录,则忽略当前新数据 如果您使用一个例如“SET col_name = col_name + 1”的赋值,则对位于右侧 ...

随机推荐

  1. COGS439&period; &lbrack;网络流24题&rsqb; 软件补丁

    [问题描述] 对于一个软件公司来说,在发行一个新软件之后,可以说已经完成了工作.但是实际上,许多软件公司在发行一个新产品之后,还经常发送补丁程序,修改原产品中的错误(当然,有些补丁是要收费的). 如某 ...

  2. android studio 使用问题 解决方法

    1. Error:Execution failed for task ':app:transformClassesWithDexForDebug'. > com.android.build.ap ...

  3. Eclipse下Android开发的问题:Failed to install AndroidPhone&period;apk on device &&num;39&semi;emulator-5554&&num;39&semi;&colon; timeout 解决办法

    在window->preferences->Android->DDMS->ADB connection time out (ms): 将这个值设置的大一些,默认为5000,我设 ...

  4. ie6 iframe src&equals;&quot&semi;javascript&colon;&quot&semi; 报安全警报问题

    <iframe id="shuaka_iframe" class="embed-page-iframe" data-src="https://w ...

  5. 关于sql 资源竞争死锁现象

    问题:System.Exception: 事务(进程 ID 321)与另一个进程被死锁在 锁 | 通信缓冲区 资源上,并且已被选作死锁牺牲品.请重新运行该事务 死锁最深层的原因就是一个:资源竞争 表现 ...

  6. Windows 下如何安装配置Snort视频教程

    Windows 下如何安装配置Snort视频教程: 第一步: http://www.tudou.com/programs/view/UUbIQCng360/ 第二部: http://www.tudou ...

  7. AWS ec2 vpn 搭建(20161014更新http&colon;&sol;&sol;dl&period;fedoraproject&period;org&sol;pub&sol;epel&sol;7&sol;x86&lowbar;64&sol;e&sol;epel-release-7-8&period;noarch&period;rpm)

    1.原来的SoftEther VPN Server在pc端不可用了,没找到原因,因此有搜索到了一个新方法,转自http://blog.csdn.net/henryng1994/article/deta ...

  8. ROS&lowbar;Kinetic&lowbar;16 ubuntu中安装使用Matlab和ROS

    ROS_Kinetic_16 ubuntu(16.04)中安装使用Matlab(2015b)和ROS(kinetic) 参考网址:http://cn.mathworks.com/hardware-su ...

  9. python learn note1

    1.python 的缩进 习惯了java,c++之类的宽容,初学python,被它摆了道下马威,写if else,竟然必须要我正确用缩进格式,原来在python里不能用括号来表示语句块,也不能用开始/ ...

  10. wx&colon;Textctrl

    import wx class Mywin(wx.Frame): def __init__(self, parent, title): super(Mywin, self).__init__(pare ...